(57)【特許請求の範囲】
【請求項１】
コンピュータ処理により、解析対象であるプログラム又はその一部のプログラムにおけるポインタを解析する方法であって、前記コンピュータが、
コンパイラによって、コンパイル対象のメソッドを対象として、前記プログラムに対するフロー・インセンシティブな１つのポイント・ツー・グラフをメモリ内に作成するステップであって、前記ポイント・ツー・グラフは、変数を、又は、変数と、メソッド及びオブジェクトの少なくとも１つとをノードとして、当該変数と前記変数が指すオブジェクトとの関係をエッジとするグラフであり、当該作成するステップは、
（ａ）アクセス箇所を検出したいオブジェクトが特定されることに応じて、当該特定されたオブジェクトを生成するメソッド（以下、最初のメソッドという）を対象として、フロー・インセンシティブな第１のポイント・ツー・グラフを作成するステップと、
（ｂ）前記作成された第１のポイント・ツー・グラフを使用して、前記アクセス箇所を検出したいオブジェクトが前記最初のメソッドの呼び出し元の少なくとも１のメソッド（以下、第１の呼び出し元のメソッドという）に又は前記最初のメソッドから呼び出される側の少なくとも１のメソッド（以下、第１の呼び出される側のメソッドという）にエスケープするかどうかを検出するステップであって、前記第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）前記第１の呼び出し元のメソッドから又は前記第１の呼び出される側のメソッドから到達可能であること且つ（２）前記第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第１のロード・ノードを前記第１のポイント・ツー・グラフ中に用意して、当該第１のポイント・ツー・グラフを更新することを含み、前記第１のロード・ノードが、前記更新された第１のポイント・ツー・グラフ中において前記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、前記検出するステップと
を含む、前記作成するステップと、
前記アクセス箇所を検出したいオブジェクトが前記第１の呼び出し元のメソッド又は前記第１の呼び出される側のメソッドにエスケープしないことに応じて、ステップ（ｂ）において前記第１のロード・ノードが用意されている場合には前記更新された第１のポイント・ツー・グラフを又は前記ステップ（ｂ）において前記第１のロード・ノードが用意されていない場合には前記ステップ（ａ）において作成された前記第１のポイント・ツー・グラフを辿って、前記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出するステップ
を実行することを含む、前記方法。
【請求項２】
前記作成するステップが、
（ｃ）前記アクセス箇所を検出したいオブジェクトが前記第１の呼び出し元のメソッド又は前記第１の呼び出される側のメソッドにエスケープすることに応じて、前記第１の呼び出し元のメソッド又は前記第１の呼び出される側のメソッドを対象として、フロー・インセンシティブな第２のポイント・ツー・グラフを作成し、前記ステップ（ｂ）において前記第１のロード・ノードが用意されている場合には前記更新された第１のポイント・ツー・グラフに又は前記ステップ（ｂ）において前記第１のロード・ノードが用意されていない場合には前記ステップ（ａ）において作成された前記第１のポイント・ツー・グラフに前記第２のポイント・ツー・グラフをマージするステップと、
（ｄ）前記マージされた第１のポイント・ツー・グラフを使用して、前記アクセス箇所を検出したいオブジェクトがこれまでのステップにおいて解析されたメソッドの呼び出し元のメソッドのうちまだ解析されていないメソッド（以下、第２の呼び出し元のメソッドという）に又は前記これまでのステップにおいて解析されたメソッドから呼び出される側のメソッドのうちまだ解析されていないメソッド（以下、第２の呼び出される側のメソッドという）にエスケープするかどうかを検出するステップであって、前記マージされた第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）前記第２の呼び出し元のメソッドから又は前記第２の呼び出される側のメソッドから到達可能であること且つ（２）前記マージされた第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第２のロード・ノードを前記マージされた第１のポイント・ツー・グラフ中に用意して、当該マージされた第１のポイント・ツー・グラフを更新することを含み、前記第２のロード・ノードが、前記更新されたマージされた第１のポイント・ツー・グラフ中において前記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、前記検出するステップと、
（ｅ）前記アクセス箇所を検出したいオブジェクトがエスケープしなくなるまで、又は、前記最初のメソッド以外の解析対象のメソッドが所定のしきい値に達するまで、前記ステップ（ｃ）及び（ｄ）を繰り返すステップと
を含み、
前記方法は、
前記検出するステップの代わりに、前記ステップ（ｅ）において最終的に得られたポイント・ツー・グラフを辿って、前記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出するステップを含む、請求項１に記載の方法。
【請求項３】
前記ステップ（ｄ）の前記これまでのステップにおいて解析されたメソッドが、前記最初のメソッド、前記第１の呼び出し元のメソッド、又は前記第１の呼び出される側のメソッドである、請求項２に記載の方法。
【請求項４】
前記第２の呼び出し元のメソッド又は前記第２の呼び出される側のメソッドが、前記第１の呼び出し元のメソッドの呼び出し元のメソッド、又は前記第１の呼び出し元のメソッドから呼び出される側のメソッド、前記最初のメソッドから呼び出される側の他のメソッド、若しくは前記第１の呼び出される側のメソッドから呼び出される側のメソッドである、請求項２に記載の方法。
【請求項５】
前記ステップ（ｂ）のエスケープするかどうかの検出において、前記アクセス箇所を検出したいオブジェクトが、（１）変数であるプライベート・フィールドを介して前記第１の呼び出し元のメソッド又は前記第１の呼び出される側のメソッドから到達可能であること且つ（２）前記プライベート・フィールドの全ての読み出し箇所で読み出されるオブジェクトのアクセス箇所が解析済みであることを条件に、前記アクセス箇所を検出したいオブジェクトがエスケープしないとみなされる、請求項１に記載の方法。
【請求項６】
前記ステップ（ｄ）のエスケープするかどうかの検出において、前記アクセス箇所を検出したいオブジェクトが、（１）変数であるプライベート・フィールドを介して前記第２の呼び出し元のメソッド又は前記第２の呼び出される側のメソッドから到達可能であること且つ（２）前記プライベート・フィールドの全ての読み出し箇所で読み出されるオブジェクトのアクセス箇所が解析済みであることを条件に、前記アクセス箇所を検出したいオブジェクトがエスケープしないとみなされる、請求項２に記載の方法。
【請求項７】
前記ステップ（ａ）又は（ｂ）において、少なくとも１つの変数が指しうるオブジェクト全てを統合することをさらに含む、請求項１に記載の方法。
【請求項８】
前記ステップ（ｃ）又は（ｄ）において、少なくとも１つの変数が指しうるオブジェクト全てを統合することをさらに含む、請求項２に記載の方法。
【請求項９】
前記ステップ（ａ）において、所定の回数以上実行されるプログラムのみを解析対象とする、請求項１に記載の方法。
【請求項１０】
前記ステップ（ｃ）において、所定の回数以上実行されるプログラムのみを解析対象とする、請求項２に記載の方法。
【請求項１１】
前記所定のしきい値が、解析したメソッドの合計サイズ、上記解析に要した時間、又は上記解析に必要なメモリ量の所定の値である、請求項２に記載の方法。
【請求項１２】
コンピュータ処理により、当該コンピュータが請求項１〜１１のいずれか一項に記載の方法により検出されたアクセス箇所を使用してコードの最適化を行う方法。
【請求項１３】
前記コードの最適化が、最後である可能性のあるアクセス・ポイントでキャッシュ・フラッシュ命令を挿入すること、アクセスされないようであるオブジェクトを圧縮された形式でメモリに割り当てること、オブジェクト中のフィールドを再配置すること、及びオブジェクトを遅延的に（lazily）メモリに割り当てることの少なくとも１つを含む、請求項１２に記載の方法。
【請求項１４】
コンピュータ処理により、解析対象であるプログラム又はその一部のプログラムにおけるポインタを解析する方法であって、前記コンピュータが、
コンパイラによって、コンパイル対象のメソッドを対象として、前記プログラムに対するフロー・インセンシティブな１つのポイント・ツー・グラフをメモリ内に作成するステップであって、前記ポイント・ツー・グラフは、変数を、又は、変数と、メソッド及びオブジェクトの少なくとも１つとをノードとして、当該変数と前記変数が指すオブジェクトとの関係をエッジとするグラフであり、当該作成するステップは、
（ａ）アクセス箇所を検出したいオブジェクトが特定されることに応じて、当該特定されたオブジェクトを生成するメソッド（以下、最初のメソッドという）を対象として、フロー・インセンシティブな第１のポイント・ツー・グラフを作成するステップと、
（ｂ）前記作成された第１のポイント・ツー・グラフを使用して、前記アクセス箇所を検出したいオブジェクトが前記最初のメソッドの呼び出し元の少なくとも１のメソッド（以下、第１の呼び出し元のメソッドという）に又は前記最初のメソッドから呼び出される側の少なくとも１のメソッド（以下、第１の呼び出される側のメソッドという）にエスケープするかどうかを検出するステップであって、前記第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）前記第１の呼び出し元のメソッドから又は前記第１の呼び出される側のメソッドから到達可能であること且つ（２）前記第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第１のロード・ノードを前記第１のポイント・ツー・グラフ中に用意して、当該第１のポイント・ツー・グラフを更新することを含み、前記第１のロード・ノードが、前記更新された第１のポイント・ツー・グラフ中において前記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、前記検出するステップと、
（ｃ）前記アクセス箇所を検出したいオブジェクトが前記第１の呼び出し元のメソッド又は前記第１の呼び出される側のメソッドにエスケープすることに応じて、前記第１の呼び出し元のメソッド又は前記第１の呼び出される側のメソッドを対象として、フロー・インセンシティブな第２のポイント・ツー・グラフを作成し、前記ステップ（ｂ）において前記第１のロード・ノードが用意されている場合には前記更新された第１のポイント・ツー・グラフに又は前記ステップ（ｂ）において前記第１のロード・ノードが用意されていない場合には前記ステップ（ａ）において作成された前記第１のポイント・ツー・グラフに前記第２のポイント・ツー・グラフをマージするステップと、
（ｄ）前記マージされた第１のポイント・ツー・グラフを使用して、前記アクセス箇所を検出したいオブジェクトがこれまでのステップにおいて解析されたメソッドの呼び出し元のメソッドのうちまだ解析されていないメソッド（以下、第２の呼び出し元のメソッドという）に又は前記これまでのステップにおいて解析されたメソッドから呼び出される側のメソッドのうちまだ解析されていないメソッド（以下、第２の呼び出される側のメソッドという）にエスケープするかどうかを検出するステップであって、前記マージされた第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）前記第２の呼び出し元のメソッドから又は前記第２の呼び出される側のメソッドから到達可能であること且つ（２）前記マージされた第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第２のロード・ノードを前記マージされた第１のポイント・ツー・グラフ中に用意して、当該マージされた第１のポイント・ツー・グラフを更新することを含み、前記第２のロード・ノードが、前記更新された前記マージされた第１のポイント・ツー・グラフ中において前記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、前記検出するステップと、
（ｅ）前記アクセス箇所を検出したいオブジェクトがエスケープしなくなるまで、又は、前記最初のメソッド以外の解析対象のメソッドが所定のしきい値に達するまで、前記ステップ（ｃ）及び（ｄ）を繰り返すステップと
を含む、前記作成するステップと、
前記ステップ（ｅ）において最終的に得られたポイント・ツー・グラフを辿って、前記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出するステップと
を含む、前記方法。 
【請求項１５】
解析対象であるプログラム又はその一部のプログラムにおけるポインタを解析するコンピュータであって、
コンパイラによって、コンパイル対象のメソッドを対象として、前記プログラムに対するフロー・インセンシティブな１つのポイント・ツー・グラフをメモリ内に作成するグラフ作成部であって、前記ポイント・ツー・グラフは、変数を、又は、変数と、メソッド及びオブジェクトの少なくとも１つとをノードとして、当該変数と前記変数が指すオブジェクトとの関係をエッジとするグラフであり、
（ａ）アクセス箇所を検出したいオブジェクトが特定されることに応じて、当該特定されたオブジェクトを生成するメソッド（以下、最初のメソッドという）を対象として、フロー・インセンシティブな第１のポイント・ツー・グラフを作成すること、及び
（ｂ）前記作成された第１のポイント・ツー・グラフを使用して、前記アクセス箇所を検出したいオブジェクトが前記最初のメソッドの呼び出し元の少なくとも１のメソッド（以下、第１の呼び出し元のメソッドという）に又は前記最初のメソッドから呼び出される側の少なくとも１のメソッド（以下、第１の呼び出される側のメソッドという）にエスケープするかどうかを検出することであって、前記第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）前記第１の呼び出し元のメソッドから又は前記第１の呼び出される側のメソッドから到達可能であること且つ（２）前記第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第１のロード・ノードを前記第１のポイント・ツー・グラフ中に用意して、当該第１のポイント・ツー・グラフを更新することを含み、前記第１のロード・ノードが、前記更新された第１のポイント・ツー・グラフ中において前記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、前記検出すること
を実行する、前記グラフ作成部と、
前記アクセス箇所を検出したいオブジェクトが前記第１の呼び出し元のメソッド又は前記第１の呼び出される側のメソッドにエスケープしないことに応じて、前記第１のロード・ノードが用意されている場合には前記更新された第１のポイント・ツー・グラフを又は前記第１のロード・ノードが用意されていない場合には前記第１のポイント・ツー・グラフを辿って、前記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出する検出部と
を備えている、前記コンピュータ。
【請求項１６】
前記作成部が、
（ｃ）前記アクセス箇所を検出したいオブジェクトが前記第１の呼び出し元のメソッド又は前記第１の呼び出される側のメソッドにエスケープすることに応じて、前記第１の呼び出し元のメソッド又は前記第１の呼び出される側のメソッドを対象として、フロー・インセンシティブな第２のポイント・ツー・グラフを作成し、前記第１のロード・ノードが用意されている場合には前記更新された第１のポイント・ツー・グラフに又は前記第１のロード・ノードが用意されていない場合には前記第１のポイント・ツー・グラフに前記第２のポイント・ツー・グラフをマージすること、
（ｄ）前記マージされた第１のポイント・ツー・グラフを使用して、前記アクセス箇所を検出したいオブジェクトがこれまでのステップにおいて解析されたメソッドの呼び出し元のメソッドのうちまだ解析されていないメソッド（以下、第２の呼び出し元のメソッドという）に又は前記これまでのステップにおいて解析されたメソッドから呼び出される側のメソッドのうちまだ解析されていないメソッド（以下、第２の呼び出される側のメソッドという）にエスケープするかどうかを検出することであって、前記マージされた第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）前記第２の呼び出し元のメソッドから又は前記第２の呼び出される側のメソッドから到達可能であること且つ（２）前記マージされた第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第２のロード・ノードを前記マージされた第１のポイント・ツー・グラフ中に用意して、当該マージされた第１のポイント・ツー・グラフを更新することを含み、前記第２のロード・ノードが、前記更新された前記マージされた第１のポイント・ツー・グラフ中において前記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、前記検出すること、及び
（ｅ）前記アクセス箇所を検出したいオブジェクトがエスケープしなくなるまで、又は、前記最初のメソッド以外の解析対象のメソッドが所定のしきい値に達するまで、前記（ｃ）及び（ｄ）を繰り返すこと
をさらに実行し、
前記検出部は、
前記（ｅ）において最終的に得られたポイント・ツー・グラフを辿って、前記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出することを実行する、
請求項１５に記載のコンピュータ。
【請求項１７】
前記（ｂ）のエスケープするかどうかの検出において、前記アクセス箇所を検出したいオブジェクトが、（１）変数であるプライベート・フィールドを介して前記第１の呼び出し元のメソッド又は前記第１の呼び出される側のメソッドから到達可能であること且つ（２）前記プライベート・フィールドの全ての読み出し箇所で読み出されるオブジェクトのアクセス箇所が解析済みであることを条件に、前記アクセス箇所を検出したいオブジェクトがエスケープしないとみなされる、請求項１５に記載のコンピュータ。
【請求項１８】
前記（ｄ）のエスケープするかどうかの検出において、前記アクセス箇所を検出したいオブジェクトが、（１）変数であるプライベート・フィールドを介して前記第２の呼び出し元のメソッド又は前記第２の呼び出される側のメソッドから到達可能であること且つ（２）前記プライベート・フィールドの全ての読み出し箇所で読み出されるオブジェクトのアクセス箇所が解析済みであることを条件に、前記アクセス箇所を検出したいオブジェクトがエスケープしないとみなされる、請求項１６に記載のコンピュータ。
【請求項１９】
前記検出部によって検出されたアクセス箇所を使用してコードの最適化を行う最適化部をさらに備えている、請求項１５〜１８のいずれか一項に記載のコンピュータ。
【請求項２０】
コンピュータに、請求項１〜１４のいずれか一項に記載の方法の各ステップを実行させる、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ポインタを解析する技法に関し、特にはアクセス箇所を検出したいオブジェクトのアクセス箇所を検出する技法に関する。
【背景技術】
【０００２】
オブジェクト指向プログラム、例えばＪａｖａ（商標）プログラムは、多数のオブジェクトをメモリのヒープ領域に動的に割り付けて、当該オブジェクトをアクセスする。これは、オブジェクトのアクセスによりＣＰＵキャッシュ・ミスの増加、及びメモリ・バンド幅の制限をもたらす。そこで、オブジェクト指向プログラムの実行中におけるＣＰＵキャッシュ及びメモリ・バンド幅の使用を最適化するために、オブジェクト指向プログラムが割り付けられたオブジェクトをどこで且つどのようにしてアクセスするかを理解することは開発者及びコンパイラの最適化処理において重要である。そこで、オブジェクトのアクセス箇所を検出する方法がこれまでに開発されてきている。
【０００３】
下記非特許文献１は、エスケープ解析を記載する（「Abstract」、及び「7.1 Escape Analysis」）。
【０００４】
下記非特許文献２は、ポインタ解析は、フロー・センシティブ又はフロー・インセンシティブのいずれかでありうることを記載する（「Abstract」）。
【０００５】
下記非特許文献３は、フィールド解析を記載する（「Abstract」）。フィールド解析は、オブジェクトのフィールドをおそらくアクセスしうるコードをスキャニングすることによって当該フィールドの有用な特性を決定する（１頁、右欄第４段落１〜３行）。例えば、Ｊａｖａ（商標）におけるプライベート・フィールドは、ローカル・クラスにおけるメソッドによってのみアクセスされうる（１頁、右欄第４段落３〜５行）。
【０００６】
下記非特許文献４は、インスタンス・フィールドについて、我々はフィールド可視修飾子に従いコードを検査すること、例えばプライベート・フィールドについて、我々は、含有クラスのコードのみを検査することを記載する（第１０７頁「3.3.1 Assigning Null」、右欄３〜５行）。
【０００７】
下記特許文献１は、「エイリアス解析」（段落０１４０）、及び「エイリアス解析は、制御フローを考慮するかしないかに依存していっそう正確にもなるしあまり正確でもなくなる。考慮するならばそれはフロー・センシティブと呼ばれ、考慮しなければそれはフロー・インセンシティブと呼ばれる。フロー・センシティブなエイリアス解析によれば、どのブロック内でパスに沿って２つのオブジェクトがエイリアスとなっているかを検出できる。これはいっそう精密であるため、いっそう複雑であり、計算がいっそう煩雑である。通常はフロー・インセンシティブな情報で十分である。この観点が図１４に示されており、この場合、フロー・インセンシティブな解析によってｐがｂのエイリアスであることはわかるけれども、フロー・センシティブな解析であれば、ブロックＢ２でのみｐがｂのエイリアスであることがわかる。」（段落０１４２）ことを記載する。
【０００８】
下記特許文献２は、プログラム変換装置が、信号処理手続きを記述したソースプログラムからハードウェアを制御するための命令コードを生成する際に、そのソースプログラムの信号処理手続きを事前に解析し、そのソースプログラム中のアドレスポインタレジスタの使用頻度の履歴をとるシミュレーション手段を備え、前記シミュレーション手段により得られた前記ソースプログラム中のアドレスポインタレジスタの使用頻度の履歴を基に、使用頻度の多いアドレスポインタレジスタを使用するレジスタ使用命令を、前記バンクグループデコーダに対応するアドレスポインタレジスタの使用命令に変更することを記載する（請求項５）。
【０００９】
下記特許文献３は、結合ビュー参照式コンパイル方式が、複数のデータ定義を結合し新たな結合ビュー定義を所持するプログラミング言語処理系において、ソースコードの構文を解析する手段と、解析した構文の型情報を解析し型情報テーブルを生成する手段と、前記型情報テーブルを参照し参照コードを生成する手段と、展開コードを出力する手段と、を備えていることを記載する（請求項１）。
【００１０】
下記特許文献４は、コンパイラ装置が、対象プログラムを実行することにより、前記対象プログラムに含まれる少なくとも一部の命令のそれぞれについて、当該命令の実行頻度を計測する実行頻度情報計測部を更に備え、前記命令群選択部は、検出された前記最適化除外命令の前記実行頻度情報計測部による前記実行頻度が予め定めた第１頻度より高い場合に、当該最適化除外命令を前記最適化対象命令群として選択し、更に、検出された前記最適化対象命令の前記実行頻度情報計測部による前記実行頻度が前記第１頻度より低い値に予め定めた第２頻度より低い場合に、当該最適化対象命令を前記最適化除外命令として選択することを記載する（請求項９）。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特表２００５−５３５０５５号公報
【特許文献２】特開２００３−１２２６２８号公報
【特許文献３】特開平１０−２１０７８号公報
【特許文献４】特開２００４−３６２２１６号公報
【非特許文献】
【００１２】
【非特許文献１】Frederic Vivien et al., “Incrementalized Pointer and Escape Analysis”,［online］, ACM 089791886/97/05,2001, インターネット〈URL http://people.csail.mit.edu/rinard/paper/pldi01.pdf〉
【非特許文献２】Rebecca Hasti et al., “Using Static Single Assignment Form to Improve Flow-Insensitive Pointer Analysis”, ［online］, ACM 0-89791-987-4/98/0006, 1998, インターネット〈URL http://www.cs.purdue.edu/homes/suresh/590s-Fall2002/papers/hasti98using.pdf〉
【非特許文献３】Sanjay Ghemawat et. Al., “Field Analysis: Getting Useful and Low-cost Interprocedural Information”, ［online］, 2000, インターネット〈URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.8889&rep=rep1&type=pdf〉
【非特許文献４】Ran Shaham et. Al., “Heap profiling for Space-Efficient Java”, ［online］, ACM 1-58113-414-2/01/06, 2001, インターネット〈URL http://www.cs.tau.ac.il/~msagiv/pldi01.pdf〉
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明は、オブジェクトのアクセス分析によって、プログラム、特にオブジェクト指向プログラムが、割り当てられたオブジェクトをどのようにアクセスし且つどこでアクセスするかを解析する技法を提供することを目的とする。特に、本発明は、オブジェクトのアクセス解析を実行時（Just-In-Time，ＪＩＴ）コンパイラで行うための軽量なポインタ解析の技法を提供することを目的とする。また、本発明は、当該解析の結果を使用して、コードの最適化を図ることを目的とする。
【課題を解決するための手段】
【００１４】
本発明は、ポインタを解析する技法を提供する。また、本発明は、当該技法により検出されたアクセス箇所を使用して、コードの最適化を行う技法を提供する。詳細には、当該技法は、ポインタを解析する方法、コンピュータ、コンピュータ・プログラム、及びコンピュータ・プログラム製品を提供する。
【００１５】
本発明の上記ポインタを解析する方法は、以下の通りである。当該方法の１つの実施態様は、
コンパイラによって、コンパイル対象のメソッドを対象として、上記プログラムに対するフロー・インセンシティブな１つのポイント・ツー・グラフをメモリ内に作成するステップであって、上記ポイント・ツー・グラフは、変数を、又は、変数と、メソッド及びオブジェクトの少なくとも１つとをノードとして、当該変数と前記変数が指すオブジェクトとの関係をエッジとするグラフであり、当該作成するステップは、
（ａ）アクセス箇所を検出したいオブジェクトが特定されることに応じて、当該特定されたオブジェクトを生成するメソッド（以下、最初のメソッドともいう）を対象として、フロー・インセンシティブな第１のポイント・ツー・グラフを作成するステップと、
（ｂ）上記作成された第１のポイント・ツー・グラフを使用して、上記アクセス箇所を検出したいオブジェクトが上記最初のメソッドの呼び出し元の少なくとも１のメソッド（以下、第１の呼び出し元のメソッドともいう）に又は上記最初のメソッドから呼び出される側の少なくとも１のメソッド（以下、第１の呼び出される側のメソッドともいう）にエスケープするかどうかを検出するステップであって、上記第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）上記第１の呼び出し元のメソッドから又は上記第１の呼び出される側のメソッドから到達可能であること且つ（２）上記第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第１のロード・ノードを上記第１のポイント・ツー・グラフ中に用意して、当該第１のポイント・ツー・グラフを更新することを含み、上記第１のロード・ノードが、上記更新された第１のポイント・ツー・グラフ中において上記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、上記検出するステップと  を含む、上記作成するステップと、
上記アクセス箇所を検出したいオブジェクトが上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドにエスケープしないことに応じて、ステップ（ｂ）において上記第１のロード・ノードが用意されている場合には上記更新された第１のポイント・ツー・グラフを又は上記ステップ（ｂ）において上記第１のロード・ノードが用意されていない場合には上記ステップ（ａ）において作成された上記第１のポイント・ツー・グラフを辿って、上記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出するステップ
を実行することを含む。
【００１６】
本発明の１つの実施態様において、上記作成するステップは、
（ｃ）上記アクセス箇所を検出したいオブジェクトが上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドにエスケープすることに応じて、上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドを対象として、フロー・インセンシティブな第２のポイント・ツー・グラフを作成し、上記ステップ（ｂ）において上記第１のロード・ノードが用意されている場合には上記更新された第１のポイント・ツー・グラフに又は上記ステップ（ｂ）において上記第１のロード・ノードが用意されていない場合には上記ステップ（ａ）において作成された上記第１のポイント・ツー・グラフに上記第２のポイント・ツー・グラフをマージするステップと、
（ｄ）上記マージされた第１のポイント・ツー・グラフを使用して、上記アクセス箇所を検出したいオブジェクトがこれまでのステップにおいて解析されたメソッドの呼び出し元のメソッドのうちまだ解析されていないメソッド（以下、第２の呼び出し元のメソッドともいう）に又は上記これまでのステップにおいて解析されたメソッドから呼び出される側のメソッドのうちまだ解析されていないメソッド（以下、第２の呼び出される側のメソッドともいう）にエスケープするかどうかを検出するステップであって、上記マージされた第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）上記第２の呼び出し元のメソッドから又は上記第２の呼び出される側のメソッドから到達可能であること且つ（２）上記マージされた第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第２のロード・ノードを上記マージされた第１のポイント・ツー・グラフ中に用意して、当該マージされた第１のポイント・ツー・グラフを更新することを含み、上記第２のロード・ノードが、上記更新されたマージされた第１のポイント・ツー・グラフ中において上記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、上記検出するステップと、
（ｅ）上記アクセス箇所を検出したいオブジェクトがエスケープしなくなるまで、又は、上記最初のメソッド以外の解析対象のメソッドが所定のしきい値に達するまで、上記ステップ（ｃ）及び（ｄ）を繰り返すステップと
を含みうる。また、本発明の１つの上記実施態様において、係る場合、上記方法は、上記検出するステップの代わりに、上記ステップ（ｅ）において最終的に得られたポイント・ツー・グラフを辿って、上記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出するステップを含みうる。
【００１７】
本発明の１つの実施態様において、上記ステップ（ｄ）の「これまでのステップにおいて解析されたメソッド」が、上記最初のメソッド、上記第１の呼び出し元のメソッド、上記第１の呼び出される側のメソッドである。本発明の１つの実施態様において、特には、上記第２の呼び出し元のメソッド又は上記第２の呼び出される側のメソッドが、上記第１の呼び出し元のメソッドの呼び出し元のメソッド、又は上記第１の呼び出し元のメソッドから呼び出される側のメソッド、上記最初のメソッドから呼び出される側の他のメソッド、若しくは上記第１の呼び出される側のメソッドから呼び出される側のメソッドである。
【００１８】
本発明の１つの実施態様において、上記ステップ（ｂ）のエスケープするかどうかの検出において、上記アクセス箇所を検出したいオブジェクトが、（１）変数であるプライベート・フィールドを介して上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドから到達可能であること且つ（２）上記プライベート・フィールドの全ての読み出し箇所で読み出されるオブジェクトのアクセス箇所が解析済みであることを条件に、上記アクセス箇所を検出したいオブジェクトがエスケープしないとみなされる。また、本発明の１つの実施態様において、上記ステップ（ｄ）のエスケープするかどうかの検出において、上記アクセス箇所を検出したいオブジェクトが、（１）変数であるプライベート・フィールドを介して上記第２の呼び出し元のメソッド又は上記第２の呼び出される側のメソッドから到達可能であること且つ（２）上記プライベート・フィールドの全ての読み出し箇所で読み出されるオブジェクトのアクセス箇所が解析済みであることを条件に、上記アクセス箇所を検出したいオブジェクトがエスケープしないとみなされる。
【００１９】
本発明の１つの実施態様において、上記ステップ（ｂ）において、少なくとも１つの変数が共通して指しうるオブジェクトと上記用意された第１のロード・ノードとを統合することをさらに含みうる。本発明の１つの実施態様において、上記ステップ（ｄ）において、少なくとも１つの変数が共通して指しうるオブジェクトと上記用意された第２のロード・ノードとを統合することをさらに含みうる。
【００２０】
本発明の１つの実施態様において、上記ステップ（ａ）において、所定の回数以上実行されるプログラムのみを解析対象としうる。本発明の１つの実施態様において、上記ステップ（ｃ）において、所定の回数以上実行されるプログラムのみを解析対象としうる。
【００２１】
また、本発明の上記ポインタを解析する方法は、以下の通りである。当該方法の１つの実施態様は、
コンパイラによって、コンパイル対象のメソッドを対象として、上記プログラムに対するフロー・インセンシティブな１つのポイント・ツー・グラフをメモリ内に作成するステップであって、上記ポイント・ツー・グラフは、変数を、又は、変数と、メソッド及びオブジェクトの少なくとも１つとをノードとして、当該変数と前記変数が指すオブジェクトとの関係をエッジとするグラフであり、当該作成するステップは、
（ａ）アクセス箇所を検出したいオブジェクトが特定されることに応じて、当該特定されたオブジェクトを生成するメソッド（最初のメソッド）を対象として、フロー・インセンシティブな第１のポイント・ツー・グラフを作成するステップと、
（ｂ）上記作成された第１のポイント・ツー・グラフを使用して、上記アクセス箇所を検出したいオブジェクトが上記最初のメソッドの呼び出し元の少なくとも１のメソッド（第１の呼び出し元のメソッド）に又は上記最初のメソッドから呼び出される側の少なくとも１のメソッド（第１の呼び出される側のメソッド）にエスケープするかどうかを検出するステップであって、上記第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）上記第１の呼び出し元のメソッドから又は上記第１の呼び出される側のメソッドから到達可能であること且つ（２）上記第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第１のロード・ノードを上記第１のポイント・ツー・グラフ中に用意して、当該第１のポイント・ツー・グラフを更新することを含み、上記第１のロード・ノードが、上記更新された第１のポイント・ツー・グラフ中において上記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、上記検出するステップと、
（ｃ）上記アクセス箇所を検出したいオブジェクトが上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドにエスケープすることに応じて、上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドを対象として、フロー・インセンシティブな第２のポイント・ツー・グラフを作成し、上記ステップ（ｂ）において上記第１のロード・ノードが用意されている場合には上記更新された第１のポイント・ツー・グラフに又は上記ステップ（ｂ）において上記第１のロード・ノードが用意されていない場合には上記ステップ（ａ）において作成された上記第１のポイント・ツー・グラフに上記第２のポイント・ツー・グラフをマージするステップと、
（ｄ）上記マージされた第１のポイント・ツー・グラフを使用して、上記アクセス箇所を検出したいオブジェクトがこれまでのステップにおいて解析されたメソッドの呼び出し元のメソッドのうちまだ解析されていないメソッド（第２の呼び出し元のメソッド）に又は上記これまでのステップにおいて解析されたメソッドから呼び出される側のメソッドのうちまだ解析されていないメソッド（第２の呼び出される側のメソッド）にエスケープするかどうかを検出するステップであって、上記マージされた第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）上記第２の呼び出し元のメソッドから又は上記第２の呼び出される側のメソッドから到達可能であること且つ（２）上記マージされた第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第２のロード・ノードを上記マージされた第１のポイント・ツー・グラフ中に用意して、当該マージされた第１のポイント・ツー・グラフを更新することを含み、上記第２のロード・ノードが、上記更新された上記マージされた第１のポイント・ツー・グラフ中において上記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、上記検出するステップと、
（ｅ）上記アクセス箇所を検出したいオブジェクトがエスケープしなくなるまで、又は、上記最初のメソッド以外の解析対象のメソッドが所定のしきい値に達するまで、上記ステップ（ｃ）及び（ｄ）を繰り返すステップと
を含む、上記作成するステップと、
上記ステップ（ｅ）において最終的に得られたポイント・ツー・グラフを辿って、上記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出するステップと
を含む。
【００２２】
また、本発明は、コンピュータに、上記ポインタを解析する方法の各ステップを実行させるコンピュータ・プログラムを提供する。
【００２３】
また、本発明の上記ポインタを解析するコンピュータは、以下の通りである。当該コンピュータは、
コンパイラによって、コンパイル対象のメソッドを対象として、上記プログラムに対するフロー・インセンシティブな１つのポイント・ツー・グラフをメモリ内に作成するグラフ作成部であって、上記ポイント・ツー・グラフは、変数を、又は、変数と、メソッド及びオブジェクトの少なくとも１つとをノードとして、当該変数と前記変数が指すオブジェクトとの関係をエッジとするグラフであり、
（ａ）アクセス箇所を検出したいオブジェクトが特定されることに応じて、当該特定されたオブジェクトを生成するメソッド（最初のメソッド）を対象として、フロー・インセンシティブな第１のポイント・ツー・グラフを作成すること、
（ｂ）上記作成された第１のポイント・ツー・グラフを使用して、上記アクセス箇所を検出したいオブジェクトが上記最初のメソッドの呼び出し元の少なくとも１のメソッド（第１の呼び出し元のメソッド）に又は上記最初のメソッドから呼び出される側の少なくとも１のメソッド（第１の呼び出される側のメソッド）にエスケープするかどうかを検出することであって、上記第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）上記第１の呼び出し元のメソッドから又は上記第１の呼び出される側のメソッドから到達可能であること且つ（２）上記第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第１のロード・ノードを上記第１のポイント・ツー・グラフ中に用意して、当該第１のポイント・ツー・グラフを更新することを含み、上記第１のロード・ノードが、上記更新された第１のポイント・ツー・グラフ中において上記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、上記検出すること
を実行する、上記グラフ作成部と、
上記アクセス箇所を検出したいオブジェクトが上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドにエスケープしないことに応じて、上記第１のロード・ノードが用意されている場合には上記更新された第１のポイント・ツー・グラフを又は上記第１のロード・ノードが用意されていない場合には上記第１のポイント・ツー・グラフを辿って、上記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出する検出部と
を備えている。
【００２４】
また、本発明の上記１つの実施態様において、上記作成部が、
（ｃ）上記アクセス箇所を検出したいオブジェクトが上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドにエスケープすることに応じて、上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドを対象として、フロー・インセンシティブな第２のポイント・ツー・グラフを作成し、上記第１のロード・ノードが用意されている場合には上記更新された第１のポイント・ツー・グラフに又は上記第１のロード・ノードが用意されていない場合には上記第１のポイント・ツー・グラフに上記第２のポイント・ツー・グラフをマージすること、
（ｄ）上記マージされた第１のポイント・ツー・グラフを使用して、上記アクセス箇所を検出したいオブジェクトがこれまでのステップにおいて解析されたメソッドの呼び出し元のメソッドのうちまだ解析されていないメソッド（第２の呼び出し元のメソッド）に又は前記これまでのステップにおいて解析されたメソッドから呼び出される側のメソッドのうちまだ解析されていないメソッド（第２の呼び出される側のメソッド）にエスケープするかどうかを検出することであって、上記マージされた第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）上記第２の呼び出し元のメソッドから又は上記第２の呼び出される側のメソッドから到達可能であること且つ（２）上記マージされた第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第２のロード・ノードを上記マージされた第１のポイント・ツー・グラフ中に用意して、当該マージされた第１のポイント・ツー・グラフを更新することを含み、上記第２のロード・ノードが、上記更新された上記マージされた第１のポイント・ツー・グラフ中において上記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、上記検出すること、及び
（ｅ）上記アクセス箇所を検出したいオブジェクトがエスケープしなくなるまで、又は、上記最初のメソッド以外の解析対象のメソッドが所定のしきい値に達するまで、上記（ｃ）及び（ｄ）を繰り返すこと
をさらに実行しうる。また、上記検出部は上記（ｅ）において最終的に得られたポイント・ツー・グラフを辿って、上記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出することを実行しうる。
【００２５】
また、本発明の上記１つの実施態様において、上記コンピュータは、上記検出部によって検出されたアクセス箇所を使用してコードの最適化を行う最適化部をさらに備えている。
【発明の効果】
【００２６】
本発明の実施態様に従うと、フロー・インセンティブ技法に従い得られたポイント・ツー・グラフ中に、エスケープ・オブジェクトのポインタ・フィールドからロードされるオブジェクトを示すためのロード・ノードが、当該ポイント・ツー・グラフ中の少なくとも１つのオブジェクトのフィールドが所定の条件下でのみ用意される。よって、ロード・ノードの生成を抑制することができる。従って、解析時間及び必要なメモリ量の低減を図ることが可能である。
【図面の簡単な説明】
【００２７】
【図１】ポインタ解析を説明するための図である。
【図２Ａ】オブジェクトをポイント・ツー・グラフ（point-to graph）で表現する例を示す。
【図２Ｂ】オブジェクトをポイント・ツー・グラフで表現する例を示す。
【図３】プログラムをフロー・センシティブ（flow-sensitive）技法（制御流を考慮した技法）で解析して、当該解析結果をポイント・ツー・グラフで表現する例を示す。
【図４】プログラムをフロー・インセンシティブ（flow-insensitive）技法（制御流を無視した技法）で解析して、当該解析結果をポイント・ツー・グラフで表現する例を示す。
【図５Ａ】プログラムをフロー・インセンシティブ技法のうちのインクルージョン・ベースド（inclusion-based）技法（包含関係に基づいた技法）で解析して、当該解析結果をポイント・ツー・グラフで表現する例を示す。
【図５Ｂ】図５Ａのインクルージョン・ベースド技法による解析のフローをポイント・ツー・グラフで表現した図である。
【図６Ａ】プログラムをフロー・インセンシティブ技法のうちのユニフィケーション・ベースド（unification-based）技法（単一化に基づいた技法）で解析して、当該解析結果をポイント・ツー・グラフで表現する例を示す。
【図６Ｂ】図６Ａのユニフィケーション・ベースド技法による解析のフローをポイント・ツー・グラフで表現した図である。
【図７Ａ】インクルージョン・ベースド技法による解析処理が遅い理由を、ポイント・ツー・グラフを使用して説明した図である。
【図７Ｂ】ユニフィケーション・ベースド技法による解析処理が速い理由を、ポイント・ツー・グラフを使用して説明した図である。
【図８】メソッド境界を越えるポインタ解析（メソッド間ポインタ解析）のうち、ホール・プログラム（whole-program）技法（プログラム全体を対象とする技法）による解析の結果をポイント・ツー・グラフで表現した図である。
【図９Ａ】メソッド境界を越えるポインタ解析（メソッド間ポインタ解析）のうち、インクリメンタライズド（incrementalized）技法（漸増化された技法）による解析のフローをポイント・ツー・グラフで表現した図である。
【図９Ｂ】メソッド境界を越えるポインタ解析（メソッド間ポインタ解析）のうち、インクリメンタライズド技法による解析のフローをポイント・ツー・グラフで表現した図である。
【図９Ｃ】メソッド境界を越えるポインタ解析（メソッド間ポインタ解析）のうち、インクリメンタライズド技法による解析のフローをポイント・ツー・グラフで表現した図である。
【図１０Ａ】インクリメンタライズド技法における「Ｌｏａｄ」ノードの導入をポイント・ツー・グラフで示した図である。
【図１０Ｂ】インクリメンタライズド技法における「Ｌｏａｄ」ノードの導入をポイント・ツー・グラフで示した図である。
【図１１Ａ】インクリメンタライズド技法による解析によって（上段）、又は、当該インクリメンタライズド技法による解析にさらにフロー・インセンシティブ技法のうちのユニフィケーション・ベースド技法による解析を組み合わせた技法による解析によって（下段）、ポイント・ツー・グラフを作成することを示す図である。
【図１１Ｂ】本発明の実施態様に従い、ユニフィケーション・ベースド技法による解析とインクリメンタライズド技法による解析とを組み合わせ、さらに不要なロード・ノードの抑制をする技法による解析によって（下段）、ポイント・ツー・グラフを作成することを示す図である。
【図１１Ｃ】図１１Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１１Ｄ】図１１Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１１Ｅ】図１１Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１１Ｆ】図１１Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフを使用して、アクセス箇所を検出したいオブジェクトのアクセス箇所を検出することを説明する図である。
【図１１Ｇ】図１１Ｂに示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１１Ｈ】図１１Ｂに示すポインタ解析により得られるポイント・ツー・グラフを使用して、アクセス箇所を検出したいオブジェクトのアクセス箇所を検出することを説明する図である。
【図１２Ａ】インクリメンタライズド技法による解析によって（上段）、又は、本発明の実施態様に従い、頻繁に実行されるプログラム領域のみを解析することを説明する図である。
【図１２Ｂ】図１２Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１２Ｃ】図１２Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１２Ｄ】図１２Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１２Ｅ】図１２Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１２Ｆ】図１２Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフをさらにスニッフする必要があるかどうかを検出することを説明する図である。
【図１３Ａ】プライベート・フィールドを考慮しないで解析することを説明する図である。
【図１３Ｂ】本発明の実施態様に従い、プライベート・フィールドを考慮して解析することを説明する図である。
【図１３Ｃ】本発明の実施態様に従い、プライベート・フィールドを考慮して解析することを説明する図である。
【図１４Ａ】図１３Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１４Ｂ】図１３Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１４Ｃ】図１３Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１４Ｄ】図１３Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフ（１３２２）の生成の詳細を示す図である。
【図１４Ｅ】図１３Ａの下段に示すポインタ解析において、さらにポインタ解析が必要であることを説明する図である。
【図１４Ｆ】図１３Ａの上段及び下段に示すポインタ解析では、グラフがさらに大きくなることを示す図である。
【図１４Ｇ】図１３Ａの上段及び下段に示すポインタ解析では、グラフがさらに大きくなることを示す図である。
【図１４Ｈ】図１３Ｂの上段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１４Ｉ】図１３Ｂの下段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。
【図１５Ａ】本発明の実施形態におけるコンピュータ・ハードウェアの基本的なブロック図を示す。
【図１５Ｂ】図１５Ａに示すコンピュータ・ハードウェアの機能を有し、本発明の実施態様に従うシステムの機能ブロック図を示す。
【図１６】本発明の実施態様に従う、ポインタを解析する方法のフローチャートである。
【図１７Ａ】図１６のフローチャートにおいて、フロー・インセンシティブなポイント・ツー・グラフを作成するステップ（１６０３及び１６０７）の詳細なフローチャートである。
【図１７Ｂ】図１６のフローチャートにおいて、フロー・インセンシティブなポイント・ツー・グラフを作成するステップ（１６０３及び１６０７）の詳細なフローチャートである。
【図１７Ｃ】図１７Ｂのステップ１７０７において行われるグラフの生成の例を説明するためのグラフである。
【図１７Ｄ】図１７Ｂのステップ１７１１において行われるグラフの生成の例を説明するためのグラフである。
【図１７Ｅ】図１７Ｂのステップ１７１３において行われるグラフの生成の例を説明するためのグラフである。
【図１８Ａ】図１６のフローチャートにおいて、フロー・インセンシティブなポイント・ツー・グラフを使用して、アクセス箇所を検出したいオブジェクトが、呼び出し元のメソッドに、又は、呼び出される側のメソッドにエスケープするかどうかを検出するステップ（１６０４）の詳細なフローチャートである。
【図１８Ｂ】図１６のフローチャートにおいて、フロー・インセンシティブなポイント・ツー・グラフを使用して、アクセス箇所を検出したいオブジェクトが、呼び出し元のメソッドに、又は、呼び出される側のメソッドにエスケープするかどうかを検出するステップ（１６０４）の詳細なフローチャートである。
【図１９】本発明の実施態様に従うポインタ解析において使用されるメモリ使用量の削減効果の実験結果を示す図である。
【図２０】ポインタ解析の結果を使用して、エイリアス解析を行い、コードの最適化を行う例を示す図である。
【図２１】ポインタ解析の結果を使用して、オブジェクトのアクセス解析を行い、コードの最適化を行う例を示す図である。
【図２２】ポインタ解析の結果を使用して、オブジェクトの圧縮を行い、コードの最適化を行う例を示す図である。
【図２３】ポインタ解析の結果を使用して、頻繁にアクセスされるフィールドの再配置を行い、コードの最適化を行う例を示す図である。
【図２４Ａ】ポインタ解析の結果を使用して、オブジェクトを遅延的に生成し、コードの最適化を行う例を示す図である。
【図２４Ｂ】ポインタ解析の結果を使用して、オブジェクトを遅延的に生成するコードの例を示す図である。
【発明を実施するための形態】
【００２８】
本発明の実施形態を、以下に図面に従って説明する。以下の図を通して、特に断らない限り、同一の符号は同一の対象を指す。本発明の実施形態は、本発明の好適な態様を説明するためのものであり、本発明の範囲をここで示すものに限定する意図はないことを理解されたい。
【００２９】
以下では、本発明の基礎となる技術の理解を容易にするために下記技術（項目１〜８）を説明した後に、本発明の実施態様を引き続き説明する。
１．ポインタ解析（図１）
２．ポイント・ツー・グラフ（図２Ａ〜図２Ｂ）
３．フロー・センシティブ技法（図３）
４．フロー・インセンシティブ技法（図４）
５．フロー・インセンシティブ技法のうちのインクルージョン・ベースド技法（図５Ａ〜図５Ｂ、及び図７Ａ）
６．フロー・インセンシティブ技法のうちのユニフィケーション・ベースド技法（図６Ａ〜図６Ｂ、及び図７Ｂ）
７．ホール・プログラム技法（図８）
８．インクリメンタライズド技法（図９Ａ〜図９Ｃ、及び図１０Ａ〜図１０Ｂ）
【００３０】
図１は、ポインタ解析を説明するための図である。
ポインタ解析とは、プログラム中の変数がどのオブジェクトを指すかを当該プログラムの実行前に調べるための、コンパイラによる解析手法をいう。
【００３１】
図１のコード（１０１）は、プログラムの例を示す。本発明の実施態様において、プログラムは、オブジェクト指向言語を包含する。オブジェクト指向言語は、例えば、Ｊａｖａ（商標）、Ｊａｖａ（商標）Ｓｃｒｉｐｔ、Ｃ、Ｃ＋＋、Ｃ♯、Ｐｙｔｈｏｎ、Ｒｕｂｙ、Ｈａｓｋｅｌｌ、Ｇｏ、Ｍｏｄｕｌａ−３及びＳｃｒｉｐｔ（ＰＨＰ、Ｐｙｈｔｏｎ、Ｒｕｂｙ又はＰｅｒｌ）を包含する。
【００３２】
「オブジェクト」は、プログラム上の抽象化された手続きの対象を具体化したものであり、プログラム中に記述されるオブジェクトの割り付け場所から生成されるオブジェクトである。「オブジェクト」は、プログラムの実行時に、メモリ内、例えばヒープ領域内に割り付けられる。「オブジェクト」は、例えばクラスから生成される。「オブジェクト」は、メモリ領域上に割り付けられる。「オブジェクト」は、プログラムの実行が、例えば中断又は完了した場合であっても、メモリのヒープ領域に存在しうる。ヒープ領域は、プログラムに使用されるヒープ領域全体ではなく、当該ヒープ領域全体の一部であって、オブジェクトが割り付けられる領域である。ヒープ領域は、例えば、ＧＣの対象となるヒープ領域である。
【００３３】
「オブジェクト」は、典型的には、ヘッダ及び少なくとも１のフィールドを含む。ヘッダは、オブジェクト内に埋め込まれた、オブジェクト自体の情報を保持する部分であり、例えばオブジェクトのサイズ及び種類の情報を含む。フィールドは、オブジェクトの利用者がアクセス可能な部分であり、例えばポインタと非ポインタの２種類のデータを有する。ポインタとは、メモリ領域上のある場所を参照する値であり、多くの言語処理系では，オブジェクトへのポインタはオブジェクトの先頭アドレスを参照する。非ポインタは、プログラミングにおいて、値そのものを利用するものであり、数値、文字、及び／又は真偽値を包含する。
【００３４】
ポインタ解析において、当該解析に入力されるデータは、プログラム又は当該プログラムの一部である。また、当該解析から出力されるデータは、変数集合Ｖからオブジェクト集合Ｎへの対応関係である。当該出力は、多くの場合、ポイント・ツー・グラフで表現される。
【００３５】
図１は、コード（１０１）をポインタ解析することによって（１０２）、ポイント・ツー・グラフ（１０３）が生成されることを示す。
ポイント・ツー・グラフは、変数を、又は、変数と、メソッド及びオブジェクトの少なくとも１つとをノードとして、当該変数と前記変数が指すオブジェクトとの関係をエッジとするグラフである。すなわち、ポイント・ツー・グラフは、（１）変数のみ、（２）変数及びメソッド、（３）変数及びオブジェクト、並びに（４）変数、メソッド及びオブジェクトをノードとしうる。ポイント・ツー・グラフは、図１に示されているように、例えば、変数ノード、メソッド・ノード、オブジェクト・ノード、並びにポイント・ツー関係及びその他の関係で表現される（凡例（１２１）を参照）。
ポイント・ツー・グラフの変数は、プログラム中のローカル変数（例えば、１１１、１１２、１１５及び１１８）、オブジェクトのフィールド変数（例えば、１１４及び１１７）、又はその他の特殊な変数である。ポイント・ツー・グラフは、特殊な変数として、例えば、「ａｒｇ」、及び「ｒｅｔｕｒｎ」を有する（下記図９Ａ〜図９Ｃを参照）。図１に示すポイント・ツー・グラフ（１０３）は、プログラム中のローカル変数として「ｘ」（１１１）及び「ｙ」（１１２）、並びに「ａ」（１１５）及び「ｂ」（１１８）を有し、並びに、オブジェクトのフィールド変数として「ｄａｔａ」（１１４）及び「ｎｅｘｔ」（１１７）を有する。
オブジェクトは、上記に説明したとおりである。
ポイント・ツー関係は、上記変数がどのオブジェクトを指すかという関係である。
その他の関係は、オブジェクトがどのフィールド変数を持つか、並びに、メソッドがどのオブジェクトを引数に持つか、メソッドがどの変数を返り値に持つか、メソッド呼び出しがどの変数を引数に持つか、メソッド呼び出しがどのオブジェクトを返り値に持つか、という関係である。
【００３６】
図２Ａは、オブジェクトをポイント・ツー・グラフで表現する例を示す。
図２Ａは、プログラム・コード（２０１）をポインタ解析（２０２）した場合に作成されるポイント・ツー・グラフ（２０３）を示す。ポイント・ツー・グラフ（２０３）は図２Ａに示されているようにポイント・ツー関係とその他の関係とを全て表現したものであり、この表現を作成することはポインタ解析においてコード（２０１）を実際に実行しているのとほとんど同じである。コンパイラでのポインタ解析において、ポイント・ツー・グラフ（２０３）で表現されているような詳細な情報は必要ない。そのために、図２に示されているようなポイント・ツー・グラフ（２０３）を作成することは、当該解析時間及び必要なメモリが無駄である。
【００３７】
図２Ｂは、オブジェクトをポイント・ツー・グラフで表現する例を示す。
図２Ｂは、プログラム・コード（２１１）をポインタ解析（２１２）した場合に作成されるポイント・ツー・グラフ（２１３）を示す。ポイント・ツー・グラフ（２１３）は、同じ箇所に割り付けられたオブジェクトが一つに抽象化して表現できることを示す。プログラム・コード（２１１）をポインタ解析（２１２）すると、３行目の命令で割り付けられたＤａｔａオブジェクトは、ポイント・ツー・グラフ（２１３）において「３：Ｄａｔａ」と表現されているように、全部まとめて扱われてしまう。この表現方法は、図２Ａの表現方法に比べて、解析の精度は落ちるが、当該解析時間及び必要なメモリが減る。
【００３８】
図３は、プログラムをフロー・センシティブ技法で解析して、当該解析結果をポイント・ツー・グラフで表現する例を示す。
フロー・センシティブ解析とは、解析対象とするプログラムの箇所毎に、別々のポイント・ツー・グラフを作成する技法である。
図３は、プログラム・コード（３０１）をフロー・センシティブ技法に従いポインタ解析（３０２）した場合に作成される４つのポイント・ツー・グラフ（３０３、３０４、３０５、３０６）を示す。ポイント・ツー・グラフ（３０３）は、１行目の命令を解析することで作成されたものである。ポイント・ツー・グラフ（３０４）は、２行目の命令を解析することで作成されたものである。ポイント・ツー・グラフ（３０５）は、３行目の命令を解析することで作成されたものである。ポイント・ツー・グラフ（３０６）は、４行目の命令を解析することで作成されたものである。フロー・センシティブ解析では、４つのグラフを作成するために、当該解析時間及び必要なメモリが下記に述べるフロー・インセンシティブ解析よりも多い。
【００３９】
図４は、プログラムをフロー・インセンシティブ技法で解析して、当該解析結果をポイント・ツー・グラフで表現する例を示す。
フロー・インセンシティブ解析とは、解析対象とするプログラム全体で、一つのポイント・ツー・グラフを作成する技法である。
図４は、プログラム・コード（４０１）をフロー・インセンシティブ技法に従いポインタ解析（４０２）した場合に作成される１つのポイント・ツー・グラフ（４０３）を示す。フロー・インセンシティブ技法にも種類があるので、ポイント・ツー・グラフ（４０３）はその一例である。本例は、フロー・インセンシティブ技法のうち、下記図５Ａ〜図５Ｂにおいて説明するインクルージョン・ベースド技法で解析した結果である。本例で示されるポイント・ツー・グラフ（４０３）において、「１：Ｄａｔａ」の「ｎｅｘｔ」フィールドが「１：Ｄａｔａ」を指している（４０４）。「１：Ｄａｔａ」の「ｎｅｘｔ」フィールドが「１：Ｄａｔａ」を指すことは実際のコード（４０１）の実行中にはないが、本フロー・インセンシティブ技法による解析ではその精度が低いために、ポイント・ツー・グラフ（４０３）で示されるような解析結果となる。
【００４０】
フロー・インセンシティブ技法は、大きく分けると、インクルージョン・ベースド技法及びユニフィケーション・ベースド技法の２つがある。インクルージョン・ベースド技法を図５Ａ及び図５Ｂにおいて説明する。ユニフィケーション・ベースド技法を図６Ａ及び図６Ｂにおいて説明する。
【００４１】
図５Ａは、プログラムをフロー・インセンシティブ技法のうちのインクルージョン・ベースド技法で解析して、当該解析結果をポイント・ツー・グラフで表現する例を示す。
インクルージョン・ベースド技法は、ポインタのコピーを表すグラフを作り、そして当該グラフ上でポイント・ツー関係が収束するまでポインタを伝播させる方法である。インクルージョン・ベースド技法による解析は、解析精度は高いが、当該解析時間及び必要なメモリが多いという特徴を有する。
【００４２】
図５Ａは、プログラム・コード（５０１）をインクルージョン・ベースド技法に従いポインタ解析（５０２）した場合に作成されるポイント・ツー・グラフ（５０３）を示す。
【００４３】
図５Ｂは、図５Ａのインクルージョン・ベースド技法による解析のフローをポイント・ツー・グラフで表現した図である。
インクルージョン・ベースド技法に従いポイント・ツー・グラフ（５０３）を作成するアルゴリズムは、大きく分けて下記の２つを含む。
１：解析対象のプログラムの各行の命令を読み込んで、ポインタ・コピーを表すグラフを作成する。
２：以下のルールを繰り返し適用することで、上記１で作成されたグラフ上でポイント・ツー関係が収束するまでポインタを伝播させて、ポイント・ツー・グラフを作成する。
ルール１：コピー関係の矢印の元の変数から指されるオブジェクトは、当該矢印の先の変数からも指される（伝播）。
ルール２：ロード・ストア関係の矢印の元の変数の指すオブジェクトのフィールドと、当該矢印の先の変数との間にコピー関係を作る。
【００４４】
以下、上記アルゴリズム１及び２に従いインクルージョン・ベースド技法を説明する。
なお、凡例（５２１）のうち、コピー関係は、矢印の元の変数から当該矢印の先の変数へポインタがコピーされることを表す。また、凡例（５２１）のうち、ロード・ストア関係は、矢印の元の変数の指すオブジェクトのフィールドと矢印の先の変数との間のロード又はストア関係を表す。ロード・ストア関係は、ポイント・ツー・グラフにおいて、ロード又はストア先がエッジとして表現されうる。図５Ｂのフロー例では、ストア関係のみを示している。
グラフ（５１１）は、プログラム・コード（５０１）の１行目の命令を解析した結果として表現されるグラフである。
グラフ（５１２）は、２行目の命令を解析した結果として表現されるグラフである。
グラフ（５１３）は、変数「ａ」から変数「ｂ」へのストア関係があることを解析した結果として表現されるグラフである。グラフ（５１３）において、ストア関係は、変数「ａ」から変数「ｂ」へのエッジで表現されている。
グラフ（５１４）は、変数「ａ」から変数「ｂ」にコピー関係があることを解析した結果として表現されるグラフである。
グラフ（５１５）は、グラフ（５１４）において変数「ａ」が「１：Ｄａｔａ」を指しているので、当該変数「ａ」とコピー関係にあり且つ当該コピー関係の矢印の先の変数「ｂ」も「１：Ｄａｔａ」を指すようにした結果として表現されるグラフである（ルール１）。
グラフ（５１６）は、変数「ａ」から変数「ｂ」へのストア関係があることに応じて、グラフ（５１５）において、変数「ｂ」から、変数「ａ」が指す「１：Ｄａｔａ」の「ｎｅｘｔ」フィールドへのコピー関係を作った結果として表現されるグラフである（ルール２）。
グラフ（５１７）は、グラフ（５１６）において変数「ｂ」が「１：Ｄａｔａ」及び「２：Ｄａｔａ」を指しているので、当該変数「ｂ」とコピー関係にあり且つ当該コピー関係の矢印の先の「ｎｅｘｔ」フィールドも「１：Ｄａｔａ」及び「２：Ｄａｔａ」を指すようにした結果として表現されるグラフである（ルール１）。
グラフ（５１７）から、これ以上伝播させるポインタがないことがわかる。従って、グラフ（５１７）が、プログラム・コード（５０１）をインクルージョン・ベースド技法に従いポインタ解析（５０２）した場合に作成されるポイント・ツー・グラフである。ポイント・ツー・グラフ（５１７）は、図５Ａのポイント・ツー・グラフ（５０３）と同じである。ポイント・ツー・グラフ（５１７）中のコピー関係及びロード・ストア関係はポインタ解析の途中で必要になるだけであり、ポインタ解析の結果を表現する上では不要であるためである。
【００４５】
図６Ａは、プログラムをフロー・インセンシティブ技法のうちのユニフィケーション・ベースド技法で解析して、当該解析結果をポイント・ツー・グラフで表現する例を示す。
ユニフィケーション・ベースド技法は、ある変数が指す先のオブジェクトを全て統合（ユニファイ）してしまう方法である。ユニフィケーション・ベースド技法による解析は、解析精度は低いが、解析対象であるプログラムを１回スキャンするだけであることから、ほぼ線形時間で解析が終わる。従って、ユニフィケーション・ベースド技法による解析は、当該解析時間が速く且つ必要なメモリが少なくて済むという特徴を有する。
【００４６】
図６Ａは、プログラム・コード（６０１）をユニフィケーション・ベースド技法に従いポインタ解析（６０２）した場合に作成されるポイント・ツー・グラフ（６０３）を示す。ポイント・ツー・グラフ（６０３）において、変数「ａ」が「２：Ｄａｔａ」を指している（６０４）。変数「ａ」が「２：Ｄａｔａ」を指すことは実際のコード（６０１）の実行中にはないが、本ユニフィケーション・ベースド技法による解析ではその精度が低いために、ポイント・ツー・グラフ（６０３）で示されるような解析結果となる。また、ポイント・ツー・グラフ（６０３）において、「２：Ｄａｔａ」の「ｎｅｘｔ」フィールドが「１：Ｄａｔａ」及び「２：Ｄａｔａ」を指している（夫々、６０５及び６０６）。「２：Ｄａｔａ」の「ｎｅｘｔ」フィールドが「１：Ｄａｔａ」及び「２：Ｄａｔａ」を指すことは本来ないが、本ユニフィケーション・ベースド技法による解析ではその精度が低いために、ポイント・ツー・グラフ（６０３）で示されるような解析結果となる。以上のように、ユニフィケーション・ベースド技法による解析は、インクルージョン・ベースド技法による解析に比べて更に不正確である。しかしながら、ユニフィケーション・ベースド技法による解析のアルゴリズムは高速である。なぜならば、ユニフィケーション・ベースド技法による解析では、解析対象のプログラムの各行の命令を読み込んで、各変数が指す先のオブジェクトを全て統合するからである（６０３、並びに図６Ｂの６１４及び６１５を参照）。
【００４７】
図６Ｂは、図６Ａのユニフィケーション・ベースド技法による解析のフローをポイント・ツー・グラフで表現した図である。
以下、ユニフィケーション・ベースド技法を説明する。
グラフ（６１１）は、プログラム・コード（６０１）の１行目の命令を解析した結果として表現されるグラフである。
グラフ（６１２）は、２行目の命令を解析した結果として表現されるグラフである。
グラフ（６１３）は、３行目の命令を解析した結果として表現されるグラフである。
グラフ（６１４）は、４行目の命令を解析した結果として表現されるグラフである。４行目の命令は「ｂ＝ａ」というコピー文であるために、変数「ｂ」は「１：Ｄａｔａ」及び「２：Ｄａｔａ」のいずれかを指す可能性がある。そのために、グラフ（６１４）では、変数「ｂ」が「１：Ｄａｔａ」と「２：Ｄａｔａ」との両方を指すように、「１：Ｄａｔａ」と「２：Ｄａｔａ」とを統合した結果として表現される。従って、グラフ（６１４）では、「１：Ｄａｔａ」と「２：Ｄａｔａ」とが完全に同一視される。
グラフ（６１５）は、４行目の命令を解析した結果として表現されるグラフであり、グラフ（６１４）と意味的には完全に同一のグラフである。すなわち、グラフ（６１４）とグラフ（６１５）の違いは、単に、開発者向けの記法の違いである。変数「ａ」及び変数「ｂ」、並びに「１：Ｄａｔａ」の「ｎｅｘｔ」フィールド及び「２：Ｄａｔａ」の「ｎｅｘｔ」フィールドが、「１：Ｄａｔａ」及び「２：Ｄａｔａ」を指している。従って、「１：Ｄａｔａ」及び「２：Ｄａｔａ」のいずれも、「１：Ｄａｔａ」の「ｎｅｘｔ」フィールド及び「２：Ｄａｔａ」の「ｎｅｘｔ」フィールドの２つの「ｎｅｘｔ」フィールドを持つとみなされる。その結果、ユニフィケーション・ベースド技法による解析は高速ではあるが、インクルージョン・ベースド技法による解析に比べて更に不正確である。
【００４８】
図７Ａは、インクルージョン・ベースド技法による解析処理が遅い理由を、ポイント・ツー・グラフを使用して説明した図である。
グラフ（７１１〜７１４）は、プログラム・コード（７０１）をインクルージョン・ベースド技法によりポインタ解析する際に生成されるグラフである。
グラフ（７１１）は、コード（７０１）の１〜９行目の命令を読み込んで生成されるグラフである。
グラフ（７１２）及びグラフ（７１３）は、グラフ（７１１）においてコピー関係に沿ってポインタを１つ１つ伝播させる様子を示す。
グラフ（７１４）は、コピー関係に沿ってポインタを１つ１つ伝播させた結果として表現されるグラフである。
以上のように、インクルージョン・ベースド技法では、グラフ上でポイント・ツー関係が収束するまでポインタを一つ一つ伝播させるので、その解析の処理速度は遅い。
【００４９】
図７Ｂは、ユニフィケーション・ベースド技法による解析処理が速い理由を、ポイント・ツー・グラフを使用して説明した図である。
グラフ（７２１〜７２３）は、プログラム・コード（７０１）をユニフィケーション・ベースド技法によりポインタ解析する際に生成されるグラフである。
グラフ（７２１）は、コード（７０１）の１〜９行目の命令を読み込んで生成されるグラフである。「Ｂｏｔｔｏｍ１」ノードは、「どのオブジェクトも指していない」ということを表す特殊なノードである。変数「ａ」、「ｂ」、「ｃ」及び「ｄ」は、コード（７０１）の７行目までスキャンした時点では、どのオブジェクトも指していない。しかし、それら変数は、共通のオブジェクトを指すことがわかっている。従って、変数「ａ」、「ｂ」、「ｃ」及び「ｄ」が１つの共通の「Ｂｏｔｔｏｍ１」ノードを指すようにする。
グラフ（７２２）は、８行目の命令を読み込んで生成されるグラフである。ある変数（この場合、変数「ａ」）が指すオブジェクト（この場合、「８：Ｄａｔａ」）は全て統合されるので、「８：Ｄａｔａ」は「Ｂｏｔｔｏｍ１」と統合される（図中の点線で示されている）。その結果、変数「ｂ」、「ｃ」及び「ｄ」が統合されたオブジェクト中の「Ｂｏｔｔｏｍ１」を指しているので、当該統合されたオブジェクト中の「８：Ｄａｔａ」をも指すことになる。
グラフ（７２３）は、９行目の命令を読み込んで生成されるグラフである。ある変数（この場合、変数「ａ」）が指すオブジェクト（この場合、「９：Ｄａｔａ」）は全て統合されるので、「９：Ｄａｔａ」は、統合されたオブジェクトである「Ｂｏｔｔｏｍ１」及び「８：Ｄａｔａ」と統合される。その結果、変数「ｂ」、「ｃ」及び「ｄ」が統合されたオブジェクト中の「Ｂｏｔｔｏｍ１」を指しているので、当該統合されたオブジェクト中の「９：Ｄａｔａ」をも指すことになる。
以上のように、ユニフィケーション・ベースド技法では、ポインタを伝播させることなくプログラム中の文の数によらず定数時間で統合することで高速な解析が実現される。すなわち、ユニフィケーション・ベースド技法では、ユニオン・ファインド（union-find）構造を用いるので、高速な解析が実現される。
【００５０】
図８及び図９Ａ〜図９Ｃでは、メソッド境界を越えるポインタ解析（メソッド間ポインタ解析）について説明する。
ポインタ解析では、メソッド（手続き）の境界を越えて解析しないと、正確なポインタ解析結果が得られないことが多い。例えば、図８のプログラム・コード（８０１）において、２行目で割り付けられたＤａｔａオブジェクト（「２：Ｄａｔａ」）がどこでアクセスされるのかを知りたいとする。すなわち、２行目で割り付けられたＤａｔａオブジェクトがアクセス箇所を検出したいオブジェクトである。しかしながら、「ｍｅｔｈｏｄ１」から呼び出される「ｍｅｔｈｏｄ２」及び「ｍｅｔｈｏｄ１」の呼び出し元のメソッドを調べないと、２行目で割り付けられたＤａｔａオブジェクト（「２：Ｄａｔａ」）がどこでアクセスされるのかはわからない。そこで、メソッド境界を越えるポインタ解析（メソッド間ポインタ解析）を行う必要がある。
メソッド境界を越えるポインタ解析には、大きく分けて次の２つがある。すなわち、ホール・プログラム技法による解析、及びインクリメンタライズド技法による解析である。
ホール・プログラム技法による解析は、解析対象のプログラム中の全てのメソッドをメモリに読み込んで解析する技法である。図８において、その詳細を説明する。
インクリメンタライズド技法による解析は、解析対象のプログラムにおいて、求めたい情報を得るために必要なメソッドのみを順次解析対象として加えていく技法である。
【００５１】
図８は、メソッド境界を越えるポインタ解析（メソッド間ポインタ解析）のうち、ホール・プログラム技法による解析の結果をポイント・ツー・グラフで表現した図である。
プログラム・コード（８０１）において、先に述べたように、２行目で割り付けられたＤａｔａオブジェクト（「２：Ｄａｔａ」）がどこでアクセスされるのかを知りたいとする。そのために、ホール・プログラム技法では、コンピュータは、コード（８０１）中の全てのメソッド「ｍｅｔｈｏｄ１」、「ｍｅｔｈｏｄ２」、「ｍｅｔｈｏｄ３」及び「ｍａｉｎ」の４つの全てのメソッドをメモリに読み込んでポインタ解析し（８０２）、ポイント・ツー・グラフを作成する。その結果がポイント・ツー・グラフ（８０３）である。なお、ホール・プログラム技法による解析では、メソッドを表すノードはポイント・ツー・グラフ中に不要であるので、その記載をしていない。
ポイント・ツー・グラフ（８０３）では、「２：Ｄａｔａ」のアクセス箇所を知るためには本来不要な、１１行目の命令で割り付けられたＤａｔａオブジェクト（「１１：Ｄａｔａ」）についても解析されている。
【００５２】
図９Ａ、図９Ｂ及び図９Ｃは、メソッド境界を越えるポインタ解析（メソッド間ポインタ解析）のうち、インクリメンタライズド技法による解析のフローをポイント・ツー・グラフで表現した図である。
プログラム・コード（９０１、９０１ａ、９０１ｂ及び９０１ｃ）は、図８のプログラム・コード（８０１）と同じである。
【００５３】
（図９Ａの上段）
プログラム・コード（９０１）において、図８で説明したホール・プログラム技法の場合と同様に、２行目で割り付けられたＤａｔａオブジェクト（「２：Ｄａｔａ」）がどこでアクセスされるのかを知りたいとする。
【００５４】
（図９Ａ下段）
そのために、インクリメンタライズド技法では、コンピュータは、コード（９０１ａ）中の２行目の命令を含む「ｍｅｔｈｏｄ１」を最初の解析対象としてメモリに読み込んでポインタ解析し（９１１）、部分的なポイント・ツー・グラフを作成する。その結果が、ポイント・ツー・グラフ（９１２）である。ポイント・ツー・グラフ（９１２）中には、特別なノードである「ｒｅｔｕｒｎ」ノード及び「ａｒｇ１」ノードが用意されている（９１３）。「ｒｅｔｕｒｎ」ノードはメソッド返り値のための特別なノードであり、及び「ａｒｇ１」ノードはメソッド呼び出しの引数のための特別なノードである。ポイント・ツー・グラフ（９１２）中、「４：ｍｅｔｈｏｄ２」は、コード（９０１ａ）の４行目の呼び出しであることを意味する。ポイント・ツー・グラフ（９１２）から、「２：Ｄａｔａ」は、「ｍｅｔｈｏｄ２」呼び出しの引数であり、且つ「ｍｅｔｈｏｄ１」の返り値であることがわかる。「２：Ｄａｔａ」が「ｍｅｔｈｏｄ２」呼び出しの引数であることを、「２：Ｄａｔａ」は「ｍｅｔｈｏｄ２」に「エスケープする」という。また、「２：Ｄａｔａ」が「ｍｅｔｈｏｄ１」の返り値であることを、「２：Ｄａｔａ」は「ｍｅｔｈｏｄ１」の呼び出し元に「エスケープする」という。
【００５５】
（図９Ｂの上段）
コンピュータは、「２：Ｄａｔａ」が「ｍｅｔｈｏｄ２」に「エスケープする」ことに応じて、「ｍｅｔｈｏｄ２」をメモリに読み込んで、ポイント・ツー・グラフを生成する。その結果が、ポイント・ツー・グラフ（９２２）である。
【００５６】
（図９Ｂの下段）
コンピュータは、図９Ａの下段に示すポイント・ツー・グラフ（９１２）に図９Ｂの上段に示すポイント・ツー・グラフ（９２２）をマージして（９３１）、ポイント・ツー・グラフ（９１２）を更新し、ポイント・ツー・グラフ（９３２）を生成する。なお、最初の解析対象である「ｍｅｔｈｏｄ１」以外のメソッドをメモリに読み込んで解析することを、スニッフ（sniff）と呼ぶ。
【００５７】
（図９Ｃの上段）
コンピュータは、「２：Ｄａｔａ」は「ｍｅｔｈｏｄ１」の呼び出し元に「エスケープする」ことに応じて、「ｍａｉｎ」をメモリに読み込んで、ポイント・ツー・グラフを生成する。その結果が、ポイント・ツー・グラフ（９４２）である。
【００５８】
（図９Ｃの下段）
コンピュータは、図９Ｂの下段に示すポイント・ツー・グラフ（９３２）に図９Ｃの上段に示すポイント・ツー・グラフ（９４２）をマージして（９５１）、ポイント・ツー・グラフ（９３２）を更新し、ポイント・ツー・グラフ（９５２）を生成する。
【００５９】
「２：Ｄａｔａ」は、「ｍｅｔｈｏｄ２」及び「ｍｅｔｈｏｄ１」、並びに「ｍａｉｎ」以外のメソッドにはエスケープしないので解析を終了する。なお、「２：Ｄａｔａ」は「ｍｅｔｈｏｄ３」にはエスケープしないので、「ｍｅｔｈｏｄ３」を解析する必要はない。
【００６０】
図８では、メソッド境界を越えるポインタ解析のうち、ホール・プログラム技法を説明し、図９Ａ〜図９Ｂでは、メソッド境界を越えるポインタ解析のうち、インクリメンタライズド技法を説明した。
ホール・プログラム技法による解析は、解析対象のプログラム中の全てのメソッドをメモリに読み込んで解析する技法であるので、インクリメンタライズド技法によるポインタ解析と比べて、解析時間及び必要なメモリが多い点で不利である。しかも、２行目で割り付けられたＤａｔａオブジェクトがどこでアクセスされるのかを知りたい場合、図８のコード（８０１）において「ｍｅｔｈｏｄ３」のポインタ解析は「２：Ｄａｔａ」のアクセス箇所を知るためには本来必要ない。
【００６１】
ただし、ホール・プログラム技法による解析は、下記の場合に有利である。図８のコード（８０１）の１１行目の命令で割り付けられたＤａｔａオブジェクトのアクセス箇所をさらに知りたいとする。すなわち、１１行目で割り付けられたＤａｔａオブジェクトがアクセス箇所を検出したいオブジェクトである。この場合、ホール・プログラム技法による解析では、図８で作成したポイント・ツー・グラフ（８０３）を、そのまま使うことができる。一方、インクリメンタライズド技法による解析では、もし１１行目の命令で割り付けられたＤａｔａオブジェクトのアクセス箇所を知りたい場合、図９Ａ〜図９Ｃで作成したポイント・ツー・グラフ（９５２）をそのままそのまま使うことができないので、「ｍｅｔｈｏｄ２」及び「ｍｅｔｈｏｄ１」、並びに「ｍａｉｎ」を解析する必要があり、従って「ｍｅｔｈｏｄ２」及び「ｍａｉｎ」の解析が二度手間になる。
【００６２】
図１０Ａ及び図１０Ｂは、インクリメンタライズド技法における「Ｌｏａｄ」ノードの導入をポイント・ツー・グラフで示した図である。
インクリメンタライズド技法による解析は、ホール・プログラム技法に比べて、解析時間及び必要なメモリが少ないので有利である。さらに、この解析時間及び必要なメモリを少なくするために、所定の上限を設けておいて、上限内で可能な限り解析するということが可能である。所定の上限は、例えば、スニッフするメソッドの行数の合計に上限を設けることである（以下、「スニッフ制限」という）。この所定の上限を設ける方法は、例えば、ＪＩＴコンパイラなどの解析時間と必要なメモリが重要な場合に用いられる。
【００６３】
図１０Ａ及び図１０Ｂに記載のプログラム・コード（１００１ａ、１００１ｂ及び１００１ｃ）は同じコードである。
【００６４】
（図１０Ａの上段）
コード（１００１ａ）において、５行目で割り付けられたＤａｔａオブジェクト（「５：Ｄａｔａ」）がどこでアクセスされるかを知りたいとする。すなわち、５行目で割り付けられたＤａｔａオブジェクトがアクセス箇所を検出したいオブジェクトである。
実際のコード（１００１ａ）の実行中に、「５：Ｄａｔａ」は、変数「ｂ」が指すオブジェクト経由で「ｍｅｔｈｏｄ１」の呼び出し元と「ｍｅｔｈｏｄ２」にエスケープする。しかしながら、図９Ａ〜図９Ｃで説明したインクリメンタライズド技法による解析のようにコード（１００１ａ）をポインタ解析して（１０１１）、「ｍｅｔｈｏｄ１」のポイント・ツー・グラフを生成すると、図１０Ａの上段に示すポイント・ツー・グラフ（１０１２）になる。ポイント・ツー・グラフ（１０１２）は、「ｍｅｔｈｏｄ１」を解析したが、「ｍｅｔｈｏｄ２」をまだスニッフしていない段階のポイント・ツー・グラフである。ポイント・ツー・グラフ（１０１２）では、変数「ｂ」はどのオブジェクトも指していない。従って、「５：Ｄａｔａ」は、どこにもエスケープしないとみなされる。
【００６５】
（図１０Ａの下段）
そこで、コード（１００１ｂ）の４行目で、「２：Ｄａｔａ」の「ｎｅｘｔ」フィールドから変数「ｂ」にロードされる未知な（unknown）オブジェクトを表すノードとして、「Ｌｏａｄ」ノード（「４：（Ｌｏａｄ）」）を用意する。「Ｌｏａｄ」ノード（ロード・ノードともいう）は、代理の役目を果たすノード（place-holder node）ともいう。ロード・ノードは、エスケープするオブジェクトのポインタ・フィールドから変数にロードされる未知なオブジェクトを表すノードである。「４：（Ｌｏａｄ）」を用意したポイント・ツー・グラフが、図１０Ａの下段に示すポイント・ツー・グラフ（１０２２）である。「Ｌｏａｄ」ノードは、エスケープするオブジェクト（ここでは、「２：Ｄａｔａ」）のフィールドからのロードに対応して作成される。ただし、ロード・ノードを作成することはメモリ消費の増大につながる。
【００６６】
（図１０Ｂ）
「４：（Ｌｏａｄ）」は、この後に「ｍｅｔｈｏｄ２」をスニッフしたときに、コード（１００１ｃ）の１０行目の命令で割り付けられるＤａｔａオブジェクトである「１０：Ｄａｔａ」に置き換えられるようにしうる。「１０：Ｄａｔａ」に置き換えられたポイント・ツー・グラフが、図１０Ｂに示すポイント・ツー・グラフ（１０３２）である。「４：（Ｌｏａｄ）」を「１０：Ｄａｔａ」に必ずしも置き換える必要はない。しかしながら、「４：（Ｌｏａｄ）」はどこで割り当てられたのか分からない未知のオブジェクトであるのに対して、上記のように、「４：（Ｌｏａｄ）」を「１０：Ｄａｔａ」に置き換えることができれば、「５：Ｄａｔａ」は、コード（１００１ｂ）の１０行目で割り当てられたＤａｔａオブジェクト（「１０：Ｄａｔａ」）から指されることが分かる。従って、得られたポイント・ツー・グラフ（１０３２）は、ポイント・ツー・グラフ（１０２２）に比べてより詳しいポイント・ツー関係が分かる。ポイント・ツー・グラフ（１０３２）は、「ｍｅｔｈｏｄ１」及び「ｍｅｔｈｏｄ２」を解析した段階のポイント・ツー・グラフである。
【００６７】
図１１Ａは、インクリメンタライズド技法による解析によって（上段）、又は、当該インクリメンタライズド技法による解析にさらにフロー・インセンシティブ技法のうちのユニフィケーション・ベースド技法による解析を組み合わせた技法による解析によって（下段）、ポイント・ツー・グラフを作成することを示す図である。
【００６８】
（図１１Ａの上段）
プログラム・コード（１１０１）の４行目又は２行目の命令で割り付けられたＤａｔａオブジェクトのアクセス箇所を知りたいとする。すなわち、４行目又は２行目で割り付けられたＤａｔａオブジェクト（「４：Ｄａｔａ」又は「２：Ｄａｔａ」）がアクセス箇所を検出したいオブジェクトである。
プログラム・コード（１１０１）を、図９Ａ〜図９Ｃ、及び図１０Ａ（下段）及び図１０Ｂに示す通常のインクリメンタライズド技法による解析よってポインタ解析すると（１１１１）、図１１Ａの上段に示すポイント・ツー・グラフ（１１１２）が得られる。ポイント・ツー・グラフ（１１１２）の生成の詳細を、下記図１１Ｃ〜図１１Ｄに記載する。ポイント・ツー・グラフ（１１１２）は、「ｍｅｔｈｏｄ１」を解析したが、「ｍｅｔｈｏｄ２」をまだスニッフしていない段階のポイント・ツー・グラフである。当該ポインタ解析では、「２：Ｄａｔａ」が「ｍｅｔｈｏｄ２」にエスケープするので、コード（１１０１）の７行目の命令のロードに応じて、「７：（Ｌｏａｄ）」が生成される。
【００６９】
（図１１Ａの下段）
図１１Ａの上段のインクリメンタライズド技法による解析に、ユニフィケーション・ベースド技法による解析を組み合わせて実装したとする。
図１１Ａの上段のポイント・ツー・グラフ（１１１２）の説明で述べたように、「２：Ｄａｔａ」が「６：ｍｅｔｈｏｄ２」にエスケープするので、コード（１１０１）の７行目の命令のロードに応じて、「７：（Ｌｏａｄ）」が生成される。しかし、ユニフィケーション・ベースド技法による解析（１１２１）では、「７：（Ｌｏａｄ）」と「４：Ｄａｔａ」が統合される。すなわち、ユニフィケーション・ベースド技法による解析（１１２１）では、「７：（Ｌｏａｄ）」と「４：Ｄａｔａ」は統合されて区別されなくなる。その結果として作成されたポイント・ツー・グラフが、図１１Ａの下段に示すポイント・ツー・グラフ（１１２２）である。ポイント・ツー・グラフ（１１２２）の生成の詳細を、下記図１１Ｅに記載する。
【００７０】
（図１１Ｂ）
図１１Ｂは、本発明の実施態様に従い、ユニフィケーション・ベースド技法による解析とインクリメンタライズド技法による解析とを組み合わせ、さらに不要なロード・ノードの抑制をする技法による解析によって、ポイント・ツー・グラフを作成することを示す図である。
【００７１】
図１１Ａの下段のポイント・ツー・グラフ（１１２２）の生成において、インクリメンタライズド技法による解析にユニフィケーション・ベースド技法による解析を組み合わせた技法を用いる。しかしながら、これらのポインタ解析を単に組み合わせるだけでは、不要な「Ｌｏａｄ」ノードが多く作成されてしまうだけである。そこで、本発明の実施態様に従うと、フィールドがボトム状態の場合にのみ、「Ｌｏａｄ」ノードが作成されるようにする。ボトム状態とは、オブジェクトのフィールドが、どのオブジェクトも指していない状態をいう。
【００７２】
図１１Ａの下段のポイント・ツー・グラフ（１１２２）に示されているように「２：Ｄａｔａ」オブジェクトの「ｎｅｘｔ」フィールドは「４：Ｄａｔａ」オブジェクトを既に指している。すなわち、「２：Ｄａｔａ」オブジェクトの「ｎｅｘｔ」フィールドはボトム状態でない。従って、本来は、「Ｌｏａｄ」ノードを新たに作る必要はない。すなわち、「７：（Ｌｏａｄ）」と「４：Ｄａｔａ」との２つを生成する意味はない。そこで、本発明の実施態様に従う方法では、「７：（Ｌｏａｄ）」が用意（又は作成）されないようにする（１１３１）。その結果として作成されたポイント・ツー・グラフが、図１１Ｂに示すポイント・ツー・グラフ（１１３２）である。ポイント・ツー・グラフ（１１３２）の生成の詳細を、下記図１１Ｇに記載する。ポイント・ツー・グラフ（１１３２）は、ポイント・ツー・グラフ（１１２２）と同様に、「ｍｅｔｈｏｄ１」を解析したが、「ｍｅｔｈｏｄ２」をまだスニッフしていない段階のポイント・ツー・グラフである。ポイント・ツー・グラフ（１１３２）は、ポイント・ツー・グラフ（１１２２）と異なり、「７：Ｌｏａｄ」の生成が抑制されている。ただし、コード（１１０１）の７行目の命令が「何のオブジェクトもロードされない」と解釈されることは避けなければならない。しかし、ポイント・ツー・グラフ（１１３２）では、「２：Ｄａｔａ」の「ｎｅｘｔ」フィールドはボトム状態でないので、「何らかのオブジェクトはロードされる」と解釈されるために問題ない。
【００７３】
ロード・ノードを生成することは、上記したように、メモリ消費の増大につながる。ロード・ノードはプレース・ホルダー・ノードである故に、エスケープ・オブジェクトが当該プレース・ホルダー・ノードの役割を果たす他のオブジェクトをポイントする場合には必要がない。そこで、本発明の実施態様に従うと、ポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールド（例えば、図１１Ｂのポイント・ツー・グラフ（１１９３）を参照すると、「ｎｅｘｔ」）が、（１）これまでのステップにおいて解析されたメソッド（例えば、図１１Ｂの「ｍｅｔｈｏｄ１」）の呼び出し元のメソッドのうちまだ解析されていないメソッド（例えば「ｍｅｔｈｏｄ１」の呼び出し元のメソッド、ただし図１１Ｂに記載なし）から又はこれまでのステップにおいて解析されたメソッド（例えば、「ｍｅｔｈｏｄ１」）から呼び出される側のメソッドのうちまだ解析されていないメソッド（例えば、図１１Ｂの「ｍｅｔｈｏｄ２」）から到達可能であること且つ（２）ポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、ロード・ノードがポイント・ツー・グラフ中に用意されるように制限する。このように制限することによって、ロード・ノードを生成することによるメモリ消費の増大を抑制すること、そして解析時間を減少させることが可能になる。 
【００７４】
図１１Ｃ及び図１１Ｄは、図１１Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフ（１１１２）の生成の詳細を示す図である。以下では、経時的に生成されるグラフの順に説明する。ただし、図１１Ｃ及び図１１Ｄに示されているグラフが経時的に生成されるグラフの全てを示すものではない。
グラフ（１１４１）は、コード（１１０１）中の１行目の命令を読み込むステップ（下記図１７Ａのステップ１７０２に対応する）を経て生成されるグラフである。
グラフ（１１４２）は、２行目の命令を読み込むステップ（下記図１７Ｂのステップ１７０７に対応する）を経て生成されるグラフである。
グラフ（１１４３）は、３及び４行目の命令を読み込むステップ（図１７Ｂのステップ１７０７に対応する）を経て生成されるグラフである。
グラフ（１１４４）は、５及び６行目の命令を読み込むステップ（図１７Ｂのステップ１７１３に対応する）を経て生成されるグラフである。
グラフ（１１４５）は、７行目の命令を読み込むステップ（図１７Ｂのステップ１７１１に対応する）を経て生成されるグラフである。
グラフ（１１４６）は、８及び９行目の命令を読み込むステップ（図１７Ｂのステップ１７０８に対応する）を経て生成されるグラフである。
グラフ（１１４７）は、グラフ（１１４６）中の全てのオブジェクト・ノードのエスケープ属性を全て「false」に初期化をするステップ（下記図１８Ａのステップ１８０２に対応する）を経て生成されるグラフである。
グラフ（１１４８）は、グラフ（１１４７）中の引数オブジェクトを表すオブジェクト・ノード及びメソッド呼び出しの返り値オブジェクトを表すオブジェクト・ノードのエスケープ属性を「true」にするステップ（図１８Ａのステップ１８０３に対応する）を経て得られるグラフである。グラフ（１１４７）は、引数オブジェクトを表すオブジェクト・ノード及びメソッド呼び出しの返り値オブジェクトを表すオブジェクト・ノードのいずれも有していないので、グラフ（１１４８）はグラフ（１１４７）と同じである。
グラフ（１１４９）は、グラフ（１１４８）中の変数「ａｒｇ１」から指されるオブジェクト「２：Ｄａｔａ」及び「ｒｅｔｕｒｎ」から指されるオブジェクト「４：Ｄａｔａ」のエスケープ属性を「false」から「true」にする（図１８Ａのステップ１８０４に対応する）を経て得られるグラフである。
グラフ（１１５０）は、グラフ（１１４９）中にロード・ノード「７：（Ｌｏａｄ）」（エスケープ属性のディフォルトは「false」である）を追加するステップ（図１８Ａのステップ１８０５及び１８０６に対応する）を経て得られるグラフである。
グラフ（１１５１）は、グラフ（１１５０）中において、エスケープ属性が「true」であるオブジェクト（「４：Ｄａｔａ」）から指されるオブジェクト（「７：Ｌｏａｄ」）のエスケープ属性を「true」にするステップ（図１８Ａのステップ１８０７及び１８０８に対応する）を経て得られるグラフである。
グラフ（１１５２）が、図１１Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフ（１１１２）である。この段階で、「ｍｅｔｈｏｄ１」に関するポイント・ツー・グラフが完成する。なお、グラフ（１１５２）では、エスケープ属性は通常記載しないので、エスケープ属性が記載されていない。
【００７５】
図１１Ｅは、図１１Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフ（１１２２）の生成の詳細を示す図である。以下では、経時的に生成されるグラフの順に説明する。ただし、図１１Ｅに示されているグラフが経時的に生成されるグラフの全てを示すものではない。
図１１Ｃ及び図１１Ｄのグラフ（１１４１〜１１４８）が、本ポインタ解析によっても生成される。従って、それらの説明は省略する。
グラフ（１１５９）は、図１１Ｄのグラフ（１１４９）と同じである。
グラフ（１１６０）は、ロード・ノード「７：（Ｌｏａｄ）」を追加し、そして「ｍｅｔｈｏｄ１」から指される「ｒｅｔｕｒｎ」が「７：（Ｌｏａｄ）」と「４：Ｄａｔａ」の２つのオブジェクトを指すようになるので、「７：（Ｌｏａｄ）」と「４：Ｄａｔａ」とを統合するステップを経て得られるグラフである。ロード・ノードのエスケープ属性は、ディフォルトで「false」である。
グラフ（１１６１）は、エスケープ属性が「true」であるオブジェクト（「４：Ｄａｔａ」）から指されるオブジェクト（「７：（Ｌｏａｄ）」）のエスケープ属性を「true」にするステップ（図１８のステップ１８０８に対応する）を経て得られるグラフである。
グラフ（１１６２）が、図１１Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフ（１１２２）である。この段階で、「ｍｅｔｈｏｄ１」に関するポイント・ツー・グラフが完成する。なお、グラフ（１１６２）では、エスケープ属性は通常記載しないので、エスケープ属性が記載されていない。
【００７６】
図１１Ｆは、図１１Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフ（１１２２）を使用して、アクセス箇所を検出したいオブジェクトのアクセス箇所を検出することを説明する図である。
ここで、アクセス箇所を知りたいオブジェクトが、例えば「２：Ｄａｔａ」であるとする。グラフ（１１７１）に示されているように、「２：Ｄａｔａ」のエスケープ属性が「true」であるので（図１８Ｂのステップ１８０９を参照）、グラフ（１１７１）の矢印を逆方向に辿り（１１７２）（図１８Ｂのステップ１８１０を参照）、変数「ａｒｇ１」に到達するので、「２：Ｄａｔａ」は「６：ｍｅｔｈｏｄ２」にエスケープすることがわかる（図１８Ｂのステップ１８１３を参照）。
アクセス箇所を知りたいオブジェクトが、例えば「４：Ｄａｔａ」であるとする。グラフ（１１７３）に示されているように、「４：Ｄａｔａ」のエスケープ属性が「true」であるので（図１８Ｂのステップ１８０９を参照）、グラフ（１１７３）の矢印を逆方向に辿り（１１７４及び１１７５）（図１８Ｂのステップ１８１０を参照）、変数「ｒｅｔｕｒｎ」及び変数「ａｒｇ１」に到達するので、「４：Ｄａｔａ」は「ｍｅｔｈｏｄ１」の呼び出し元及び「６：ｍｅｔｈｏｄ２」にエスケープすることがわかる（図１８Ｂのステップ１８１３を参照）。
【００７７】
図１１Ｇは、図１１Ｂに示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。以下では、経時的に生成されるグラフの順に説明する。ただし、図１１Ｇに示されているグラフが経時的に生成されるグラフの全てを示すものではない。
図１１Ｃ及び図１１Ｄのグラフ（１１４１〜１１４９）が、本ポインタ解析によっても生成される。従って、それらの説明は省略する。
グラフ（１１８０）は、グラフ（１１４９）中のエスケープ属性が「true」であるオブジェクト・ノード（「２：Ｄａｔａ」）のフィールド変数ノード（「ｎｅｘｔ」）が、いずれかのオブジェクト・ノード（「４：Ｄａｔａ」）を指しており、且つエスケープ属性が「true」であるオブジェクト・ノード（「２：Ｄａｔａ」）のフィールド変数ノードが、エスケープ属性が「false」であるオブジェクト・ノードを指していないことに応じて（図１８Ａのステップ１８０５の条件が「Yes」であり、且つステップ１８０７の条件が「No」の場合に対応する）作成されるグラフである。グラフ（１１８０）が、図１１Ｂに示すポインタ解析により得られるポイント・ツー・グラフ（１１３２）である。この段階で、「ｍｅｔｈｏｄ１」に関するポイント・ツー・グラフが完成する。なお、グラフ（１１８０）では、エスケープ属性は通常記載しないので、エスケープ属性が記載されていない。
【００７８】
図１１Ｈは、図１１Ｂに示すポインタ解析により得られるポイント・ツー・グラフ（１１３２）を使用して、アクセス箇所を検出したいオブジェクトのアクセス箇所を検出することを説明する図である。
アクセス箇所を知りたいオブジェクトが、例えば「２：Ｄａｔａ」であるとする。グラフ（１１９１）に示されているように、「２：Ｄａｔａ」のエスケープ属性が「true」であるので（図１８Ｂのステップ１８０９を参照）、グラフ（１１９１）の矢印を逆方向に辿り（１１９２）（図１８Ｂのステップ１８１０を参照）、変数「ａｒｇ１」に到達するので、「２：Ｄａｔａ」は「６：ｍｅｔｈｏｄ２」にエスケープすることがわかる（図１８Ｂのステップ１８１３を参照）。
アクセス箇所を知りたいオブジェクトが、例えば「４：Ｄａｔａ」であるとする。グラフ（１１９３）に示されているように、「４：Ｄａｔａ」のエスケープ属性が「true」であるので（図１８Ｂのステップ１８０９を参照）、グラフ（１１９３）の矢印を逆方向に辿り（１１９４及び１１９５）（図１８Ｂのステップ１８１０を参照）、変数「ｒｅｔｕｒｎ」及び変数「ａｒｇ１」に到達するので、「４：Ｄａｔａ」は「ｍｅｔｈｏｄ１」の呼び出し元と「６：ｍｅｔｈｏｄ２」にエスケープすることがわかる（図１８Ｂのステップ１８１３を参照）。
【００７９】
図１２Ａは、インクリメンタライズド技法による解析によって（上段）、又は、本発明の実施態様に従い、頻繁に実行されるプログラム領域のみを解析することを説明する図である。
図１２Ａに記載のプログラム・コード（１２０１ａ及び１２０１ｂ）は同じコードであり、且つ図１１Ａ及び図１１Ｂのプログラム・コード（１１０１）とも同じコードである。
【００８０】
（図１２Ａの上段）
プログラム・コード（１２０１ａ）の２行目の命令で割り付けられたＤａｔａオブジェクトが最後にアクセスされる箇所を知りたいとする。すなわち、２行目で割り付けられたＤａｔａオブジェクト（「２：Ｄａｔａ」）がアクセス箇所を検出したいオブジェクトである。
プログラム・コード（１２０１ａ）を、図９Ａ〜図９Ｃ、及び図１０Ａ（下段）及び図１０Ｂに示す通常のインクリメンタライズド技法によってポインタ解析すると（１２１１）、ポイント・ツー・グラフ（１２１２）が得られる。ポイント・ツー・グラフ（１２１２）の生成の詳細を、下記図１２Ｂ及び図１２Ｃに記載する。ポイント・ツー・グラフ（１２１２）は、「ｍｅｔｈｏｄ１」を解析し、「ｍｅｔｈｏｄ２」をさらにスニッフした段階のポイント・ツー・グラフである。プログラム・コード（１２０１ａ）の「ｍｅｔｈｏｄ１」を解析した結果が、図１１Ａの上段のグラフ（１１１２）又は下段のグラフ（１１２２）である。しかし、「２：Ｄａｔａ」は、「ｍｅｔｈｏｄ２」にエスケープするので、「ｍｅｔｈｏｄ２」をスニッフする必要があり、そのために「ｍｅｔｈｏｄ２」がさらにスニッフされている。ポイント・ツー・グラフ（１２１２）から、「２：Ｄａｔａ」は、コード（１２０１ａ）の４行目、７行目及び１１行目でアクセスされることがわかる。従って、コード（１２０１ａ）の７行目の「a.next」が、２行目の命令で割り付けられたＤａｔａオブジェクトによって最後にアクセスされる箇所であることがわかる。
【００８１】
（図１２Ａの下段）
オブジェクトのアクセス解析では、所定の回数以上（例えば頻繁に）実行されるプログラム領域のみを解析すれば十分であることが多い。ここで、「所定の回数以上実行される」とは解析対象のプログラムにも依存するが、例えば少なくとも１回以上、少なくとも１００回以上、少なくとも４００回以上、若しくは少なくとも１０００回以上、又はそれ以上の回数が実行されることであり、当該回数は、開発者又はプログラムが所定の回数を適宜チューニングして設定しうる。頻繁に実行されるとは、プログラムにも依存するが、例えば少なくとも１００回以上、少なくとも４００回以上、若しくは少なくとも１０００回又はそれ以上の回数が実行されることであり、当該回数は開発者又はプログラムが適宜所定の回数をチューニングして設定しうる。頻繁に実行されるプログラム領域を特定するための既存の方法は、例えば、一定時間毎に、ＣＰＵの命令ポインタの値を取得して、当該命令ポインタの値に対応するカウンタの値をインクリメントし、ある閾値を超えた命令ポインタの値に対応するプログラム領域を頻繁時実行されるプログラム領域とみなす、という技法である。
以下の例においては、メソッド呼び出し回数を基準にプログラム・コード（１２０１ｂ）が頻繁に実行されているかどうかを判断しているとする。プログラム・コード（１２０１ｂ）において、６行目の「ｍｅｔｈｏｄ２」の呼び出しは稀にしか実行されないとする。
【００８２】
プログラム・コード（１２０１ｂ）を本発明の実施態様に従う方法に従いポインタ解析すると（１２２１）、図１２Ａの下段に示すポイント・ツー・グラフ（１２２２）が得られる。ポイント・ツー・グラフ（１２２２）の生成の詳細を、下記図１２Ｄ及び図１２Ｅに記載する。当該ポインタ解析（１２２１）において、６行目の「ｍｅｔｈｏｄ２」の呼び出しは稀にしか実行されないので、「ｍｅｔｈｏｄ２」をスニッフする必要がない。そのために、当該スニッフに要する解析時間及び必要なメモリ量が減る。ポイント・ツー・グラフ（１２２２）から、「２：Ｄａｔａ」は、コード（１２０１ｂ）の４行目及び７行目でアクセスされることがわかる。従って、コード（１２０１ｂ）の７行目の「a.next」が、２行目の命令で割り付けられたＤａｔａオブジェクトによって最後にアクセスされる箇所であることがわかる。この結果は、図１２Ａの上段に示すポイント・ツー・グラフ（１２１２）から得られる結果と同じである。すなわち、ポイント・ツー・グラフ（１２２２）から得られる結果は、「ｍｅｔｈｏｄ２」をスニッフした場合と同じ結果であるので、本発明の実施態様に従い「ｍｅｔｈｏｄ２」をスニッフしない場合でも解析精度が落ちないことを示す。
【００８３】
図１２Ｂ及び図１２Ｃは、図１２Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。以下では、経時的に生成されるグラフの順に説明する。ただし、図１２Ｂ及び図１２Ｃに示されているグラフが経時的に生成されるグラフの全てを示すものではない。また、図１２Ｂ及び図１２Ｃにおいて示すポイント・ツー・グラフ（１２５９）では、「６：ｍｅｔｈｏｄ２」が削除されている点で図１２Ａの上段のポイント・ツー・グラフと異なることに注意されたい。
図１１Ｃ及び図１１Ｄのグラフ（１１４１〜１１５２）が、本ポインタ解析によっても生成される。従って、それらの説明は省略する。なお、グラフ（１１５２）は、「ｍｅｔｈｏｄ１」を解析し終わった段階のグラフである。アクセス箇所を検出したいオブジェクトが、「２：Ｄａｔａ」又は「４：Ｄａｔａ」であるとする。「２：Ｄａｔａ」及び「４：Ｄａｔａ」は、いずれも「６：ｍｅｔｈｏｄ２」にエスケープするので、「ｍｅｔｈｏｄ２」をスニッフする必要がある。
グラフ（１２５３）は、プログラム・コード（１２０１ａ）の１０行目の命令を読み込むステップ（図１７Ｂのステップ１７０８に対応する）を経て生成されるグラフである。なお、「ｍｅｔｈｏｄ２」は、返り値が無いので、変数ノード「ｒｅｔｕｒｎ」は不要である。
グラフ（１２５４）は、１１及び１２行目の命令を読み込むステップ（図１７Ｂのステップ１７０６に対応する）を経て生成されるグラフである。
グラフ（１２５５）は、「ｍｅｔｈｏｄ２」についてのグラフ（１２５４）を「ｍｅｔｈｏｄ１」についてのグラフ（１１５２）にマージするステップ（図１６のステップ１６０７に対応する）を経て生成されるグラフである。本例では、グラフ（１２５４）の「ｐａｒｍ１」及び「１１：Ｄａｔａ」がグラフ（１１５２）の「２：Ｄａｔａ」及び「７：（Ｌｏａｄ）」にそれぞれ対応するので、対応するオブジェクト同士がマージされる。なお、コード（１２０１ａ）の６行目の「ｍｅｔｈｏｄ２」呼び出しは解析済みであるので、「６：ｍｅｔｈｏｄ２」は削除される。
グラフ（１２５６）は、グラフ（１２５５）中の全てのオブジェクト・ノードのエスケープ属性を全て「false」に初期化をするステップ（図１８Ａのステップ１８０２に対応する）を経て生成されるグラフである。
グラフ（１２５７）は、グラフ（１２５６）中の引数オブジェクトを表すオブジェクト・ノード及びメソッド呼び出しの返り値オブジェクトを表すオブジェクト・ノードのエスケープ属性を「true」にするステップ（図１８Ａのステップ１８０３に対応する）を経て得られるグラフである。グラフ（１２５７）は、引数オブジェクトを表すオブジェクト・ノード及びメソッド呼び出しの返り値オブジェクトを表すオブジェクト・ノードのいずれも有していないので、グラフ（１２５７）はグラフ（１２５６）と同じである。
グラフ（１２５８）は、グラフ（１２５７）中の変数「ｒｅｔｕｒｎ」から指されるオブジェクト「４：Ｄａｔａ」のエスケープ属性を「false」から「true」にする（図１８Ａのステップ１８０４に対応する）を経て得られるグラフである。
グラフ（１２５９）は、図１２Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフ（１２１２）である。グラフ（１２５７）においてロード・ノードを追加する必要はない。なお、グラフ（１２５９）では、エスケープ属性は通常記載しないので、エスケープ属性が記載されていない。なお、グラフ（１２５９）から、「４：Ｄａｔａ」が「ｍｅｔｈｏｄ１」の呼び出し元にエスケープすることが分かるので、ポインタ解析は引き続き行われる（図１８Ｂのフローチャートを参照）。
【００８４】
図１２Ｄ及び図１２Ｅは、図１２Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。以下では、経時的に生成されるグラフの順に説明する。ただし、図１２Ｄ及び図１２Ｅに示されているグラフが経時的に生成されるグラフの全てを示すものではない。
グラフ（１２６１）は、プログラム・コード（１２０１ｂ）中の１行目の命令を読み込むステップ（図１７Ａのステップ１７０２に対応する）を経て生成されるグラフである。
グラフ（１２６２）は、２行目の命令を読み込むステップ（図１７Ｂのステップ１７０７に対応する）を経て生成されるグラフである。
グラフ（１２６３）は、３及び４行目の命令を読み込むステップ（図１７Ｂのステップ１７０７に対応する）を経て生成されるグラフである。
グラフ（１２６４）は、７行目の命令を読み込むステップ（図１７Ｂのステップ１７１１に対応する）を経て生成されるグラフである。なお、５及び６行目の命令は頻繁に実行されない命令であることから、当該命令は読み込まれずにスキップされる。
グラフ（１２６５）は、８及び９行目の命令を読み込むステップ（図１７Ｂのステップ１７０８に対応する）を経て生成されるグラフである。
グラフ（１２６６）は、グラフ（１２６５）中の全てのオブジェクト・ノードのエスケープ属性を全て「false」に初期化をするステップ（図１８Ａのステップ１８０２に対応する）を経て生成されるグラフである。
グラフ（１２６７）は、グラフ（１２６６）中の引数オブジェクトを表すオブジェクト・ノード及びメソッド呼び出しの返り値オブジェクトを表すオブジェクト・ノードのエスケープ属性を「true」にするステップ（図１８Ａのステップ１８０３に対応する）を経て得られるグラフである。グラフ（１２６６）は、引数オブジェクトを表すオブジェクト・ノード及びメソッド呼び出しの返り値オブジェクトを表すオブジェクト・ノードのいずれも有していないので、グラフ（１２６７）はグラフ（１２６６）と同じである。
グラフ（１２６８）は、グラフ（１２６７）中の変数「ｒｅｔｕｒｎ」から指されるオブジェクト「４：Ｄａｔａ」のエスケープ属性を「false」から「true」にするステップ（図１８Ａのステップ１８０４に対応する）を経て得られるグラフである。
グラフ（１２６９）は、図１２Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフ（１２２２）である。この段階で、「ｍｅｔｈｏｄ１」に関するポイント・ツー・グラフが完成する。なお、グラフ（１２６９）では、エスケープ属性は通常記載しないので、エスケープ属性が記載されていない。
【００８５】
図１２Ｆは、図１２Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフをさらにスニッフする必要があるかどうかを検出することを説明する図である。
ここで、アクセス箇所を知りたいオブジェクトが、例えば「２：Ｄａｔａ」であるとする。グラフ（１２７１）に示されているように、「２：Ｄａｔａ」のエスケープ属性は「false」であるので（１２７２）（図１８Ｂのステップ１８０９を参照）、「２：Ｄａｔａ」はエスケープしないとみなされる（図１８Ｂのステップ１８１１を参照）。従って、「ｍｅｔｈｏｄ２」をさらにスニッフする必要はない。
ここで、アクセス箇所を知りたいオブジェクトが、例えば「４：Ｄａｔａ」であるとする。グラフ（１２７３）に示されているように、「４：Ｄａｔａ」のエスケープ属性は「true」であるので（図１８Ｂのステップ１８０９を参照）、グラフ（１２７３）の矢印を逆方向に辿り（１２７４）（図１８Ｂのステップ１８１０を参照）、変数「ｒｅｔｕｒｎ」に到達するので、「４：Ｄａｔａ」は「ｍｅｔｈｏｄ１」の呼び出し元にエスケープすることがわかる（図１８Ｂのステップ１８１３を参照）。従って、「ｍｅｔｈｏｄ２」をさらにスニッフする必要はない。
以上のように、アクセス箇所を知りたいオブジェクトが「２：Ｄａｔａ」及び「４：Ｄａｔａ」のいずれであっても、「ｍｅｔｈｏｄ２」をスニッフする必要がない。従って、この状態が、図１２Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフ（１２２２）である。なお、「４：Ｄａｔａ」が「ｍｅｔｈｏｄ１」の呼び出し元にエスケープするので、ポインタ解析が引き続き行われうる。
【００８６】
図１３Ａは、プライベート・フィールドを考慮しないで解析することを説明する図である。一方、図１３Ｂ及び図１３Ｃは、プライベート・フィールドを考慮して解析することを説明する図である。
図１３Ａ及び図１３Ｂに記載のプログラム・コード（１３０１ａ及び１３０１ｂ）は同じコードである。
【００８７】
（図１３Ａの上段）
プログラム・コード（１３０１ａ）の７行目の命令で割り付けられたＤａｔａオブジェクト（「７：Ｄａｔａ」）がアクセスされる箇所を知りたいとする。すなわち、７行目で割り付けられたＤａｔａオブジェクトがアクセス箇所を検出したいオブジェクトである。
【００８８】
プログラム・コード（１３０１ａ）を、図９Ａ〜図９Ｃ、及び図１０Ａ（下段）及び図１０Ｂに示す通常のインクリメンタライズド技法による解析によってポインタ解析すると（１３１１）、図１３Ａの上側に示すポイント・ツー・グラフ（１３１２）が得られる。ポイント・ツー・グラフ（１３１２）の生成の詳細を、下記図１４Ａ〜図１４Ｃに記載する。ポイント・ツー・グラフ（１３１２）は、「ｍｅｔｈｏｄ１」及び「ｍｅｔｈｏｄ２」を解析した段階のポイント・ツー・グラフである。ポイント・ツー・グラフ（１３１２）において、「ｔｈｉｓ＿ｍｅｔｈｏｄ１」及び「ｔｈｉｓ＿ｍｅｔｈｏｄ２」は、「ｍｅｔｈｏｄ１」のｔｈｉｓ変数と、「ｍｅｔｈｏｄ２」のｔｈｉｓ変数とを区別するために名前を変えて表記したものである。また、ポイント・ツー・グラフ（１３１２）では、「ｍｅｔｈｏｄ１」の第０引数であるＤａｔａＳｅｔオブジェクトを表す特別なノードである「ｐａｒｍ０」ノードが用意されている。ポイント・ツー・グラフ（１３１２）から、「７：Ｄａｔａ」は、「ｍｅｔｈｏｄ１」の「ｐａｒｍ０」経由で「ｍｅｔｈｏｄ１」の呼び出し元にエスケープすることが分かる。従って、「７：Ｄａｔａ」がアクセスされる箇所を知るためには、他のメソッドである「ｍｅｔｈｏｄ０」をさらにスニッフする必要がある（コード（１３０１ａ）の３行目を参照）。従って、コンピュータは、プログラム・コード（１３０１ａ）を更に解析して、ポイント・ツー・グラフ（１３１２）を更新する必要がある（下記図１４Ｅを参照）。そのために、更新して得られるポイント・ツー・グラフはさらに大きくなるために（下記図１４Ｆ及び図１４Ｇを参照）、解析時間及び必要なメモリ量が増える。
【００８９】
（図１３Ａの下段）
プログラム・コード（１３０１ａ）を、フロー・インセンシティブ技法のうちのユニフィケーション・ベースド技法による解析と、図９Ａ〜図９Ｃ、及び図１０Ａ（下段）及び図１０Ｂに示す通常のインクリメンタライズド技法による解析との組み合わせによってポインタ解析すると（１３２１）、図１３Ａの下側に示すポイント・ツー・グラフ（１３２２）が得られる。ポイント・ツー・グラフ（１３２２）の生成の詳細を、下記図１４Ｄに記載する。ポイント・ツー・グラフ（１３２２）において、「ｐａｒｍ０」が「ｍｅｔｈｏｄ１」の呼び出し元にエスケープするので、９行目の命令のロードに応じて、「９：（Ｌｏａｄ）」が用意されている。そして、ユニフィケーション・ベースド技法による解析（１１２１）では、「ｍｅｔｈｏｄ１」から指される「ｐａｒｍ０」の「ｄａｔａ」フィールドが「９：（Ｌｏａｄ）」と「７：Ｄａｔａ」の２つのオブジェクトを指すようになるので、「９：（Ｌｏａｄ）」と「７：Ｄａｔａ」は統合されて区別されなくなる。
【００９０】
（図１３Ｂの上段）
図１３Ｂの上段は、本発明の実施態様に従い、インクリメンタライズド技法による解析に、ポイント・ツー・グラフ中にロード・ノード及びプライベート・フィールドを用意する技法を組み合わせて、当該ポイント・ツー・グラフを更新することを示す図である。
図１３Ａにおいて説明したように、「７：Ｄａｔａ」がアクセスされる箇所を知るためには、他のメソッドである「ｍｅｔｈｏｄ０」をさらにスニッフする必要がある（コード（１３０１ａ）の３行目を参照）。しかしながら、ＤａｔａＳｅｔクラスの「ｄａｔａ」フィールドがプライベート属性であることを利用すると、「ｍｅｔｈｏｄ０」をスニッフする必要がない。なぜならば、「ｐａｒｍ０」経由で「７：Ｄａｔａ」にアクセスするためには、コンピュータは、「ｄａｔａ」フィールドを読み込む必要があるからである。ここで、「ｄａｔａ」フィールドは、プライベート・フィールドである。プライベート・フィールドはクラス宣言の外からアクセスされることはないという性質を有する。従って、「ｄａｔａ」フィールドの読み込み箇所はＤａｔａＳｅｔクラスの中に限られている。コード（１３０１ｂ）の例では、「ｄａｔａ」フィールドの読み込みは９行目のみである。従って、コード（１３０１ｂ）の９行目でロードされるオブジェクトがどこでアクセスされるかを解析することは、「７：Ｄａｔａ」がどこでアクセスされるかを解析することに等しい。９行目でロードされるオブジェクトは、ポイント・ツー・グラフ（１３３２）中の「９：（Ｌｏａｄ）」である。従って、９行目でロードされるオブジェクトがどこでアクセスされるかは、ポイント・ツー・グラフ（１３３２）において既に解析済みである。従って、コード（１３０１ｂ）の９行目の「this.data.field」が、７行目の命令で割り付けられたＤａｔａオブジェクトによってアクセスされる箇所であることがわかる。このように、本発明の実施態様に従いプライベート・フィールドを使用することで、ポイント・ツー・グラフ（１３３２）を更新することなく、７行目の命令で割り付けられたＤａｔａオブジェクトによってアクセスされる箇所を知ることができる。以上から、プライベート・フィールドはクラス宣言の外からアクセスされないという性質を利用して、解析対象とするメソッドの数を減少させることができる。
【００９１】
図１３Ｂの上段に示すポイント・ツー・グラフ（１３３２）の生成の詳細を、下記図１４Ｈに記載する。
【００９２】
（図１３Ｂの下段）
図１３Ｂの下段の図は、本発明の実施態様に従い、フロー・インセンシティブ技法のうちのユニフィケーション・ベースド技法による解析とインクリメンタライズド技法による解析とを組み合わせ、さらにポイント・ツー・グラフ中にロード・ノード及びプライベート・フィールドを用意して当該ポイント・ツー・グラフを更新することを示す図である。
図１３Ｂの上段のポイント・ツー・グラフ（１３３２）の説明で述べたように、「ｐａｒｍ０」が「ｍｅｔｈｏｄ１」の呼び出し元にエスケープするので、９行目の命令のロードに応じて、「９：（Ｌｏａｄ）」が生成される。しかし、ユニフィケーション・ベースド技法による解析（１３４１）では、図１３Ｂの上段に示す解析（１３３１）と異なり、「９：（Ｌｏａｄ）」と「７：Ｄａｔａ」が統合される。すなわち、ユニフィケーション・ベースド技法による解析（１３４１）では、「ｍｅｔｈｏｄ１」から指される「ｐａｒｍ０」の「ｄａｔａ」フィールドが「９：（Ｌｏａｄ）」と「７：Ｄａｔａ」の２つのオブジェクトを指すようになるので、「９：（Ｌｏａｄ）」と「７：Ｄａｔａ」は統合されて区別されなくなる。その結果として作成されたポイント・ツー・グラフが、図１３Ｂの下段に示すポイント・ツー・グラフ（１３４２）である。ポイント・ツー・グラフ（１３４２）の生成の詳細を、下記図１４Ｉに記載する。
【００９３】
（図１３Ｃの上段）
図１３Ｃの上段は、本発明の実施態様に従い、インクリメンタライズド技法による解析に、ポイント・ツー・グラフ中にロード・ノード及びプライベート・フィールドを用意する技法を組み合わせて、当該ポイント・ツー・グラフを更新することを示す図である。
図１３Ｃに記載のプログラム・コード（１３０１ｃ）は、プログラム・コード（１３０１ａ及び１３０１ｂ）を一部に含むコードである。仮に、プログラム・コード（１３０１ｃ）中に、９行目以外に、１６行目においても「ｄａｔａ」フィールドの読み込み箇所があるとする。その場合、コンピュータは、コード（１３０１ｃ）中の１６行目でロードされるオブジェクトのアクセス箇所をまた解析する必要がある。そして、コンピュータは、「ｍｅｔｈｏｄ３」をスニッフする必要がある（コード（１３０１ｃ）の１５行目を参照）。または、図１３Ａの説明において述べたように、「７：Ｄａｔａ」がアクセスされる箇所を知るためには、「ｍｅｔｈｏｄ０」をさらにスニッフする必要がある（コード（１３０１ｃ）の３行目を参照）。ただし、「ｍｅｔｈｏｄ３」及び「ｍｅｔｈｏｄ０」のどちらのメソッドをスニッフした方が良いかは、解析時間、又は必要なメモリ量による。従って、図１３Ｃの上段に示すポイント・ツー・グラフ（１３５２）は、「ｍｅｔｈｏｄ３」及び「ｍｅｔｈｏｄ０」のどちらのメソッドをスニッフするかでさらに大きくなりうる。
【００９４】
（図１３Ｃの下段）
図１３Ｃの下段の図は、本発明の実施態様に従い、フロー・インセンシティブ技法のうちのユニフィケーション・ベースド技法による解析とインクリメンタライズド技法による解析とを組み合わせ、さらにポイント・ツー・グラフ中にロード・ノード及びプライベート・フィールドを用意して当該ポイント・ツー・グラフを更新することを示す図である。
図１３Ｃの上段のポイント・ツー・グラフ（１３５２）の説明で述べたように、「ｐａｒｍ０」が「ｍｅｔｈｏｄ１」の呼び出し元にエスケープするので、９行目の命令のロードに応じて、「９：（Ｌｏａｄ）」が生成される。しかし、ユニフィケーション・ベースド技法による解析（１３６１）では、図１３Ｃの上段に示す解析（１３５１）と異なり、「９：（Ｌｏａｄ）」と「７：Ｄａｔａ」が統合される。すなわち、ユニフィケーション・ベースド技法による解析（１３６１）では、「ｍｅｔｈｏｄ１」から指される「ｐａｒｍ０」の「ｄａｔａ」フィールドが「９：（Ｌｏａｄ）」と「７：Ｄａｔａ」の２つのオブジェクトを指すようになるので、「９：（Ｌｏａｄ）」と「７：Ｄａｔａ」は統合されて区別されなくなる。その結果として作成されたポイント・ツー・グラフが、図１３Ｃの下段に示すポイント・ツー・グラフ（１３６２）である。
【００９５】
図１４Ａ〜図１４Ｃは、図１３Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフ（１３１２）の生成の詳細を示す図である。以下では、経時的に生成されるグラフの順に説明する。ただし、図１４Ａ〜図１４Ｃに示しているグラフが経時的に生成されるグラフの全てを示すものではない。
グラフ（１４０１）は、プログラム・コード（１３０１ａ）中の６行目の命令を読み込むステップ（図１７Ａのステップ１７０２に対応する）を経て生成されるグラフである。
グラフ（１４０２）は、７行目の命令を読み込むステップ（図１７Ｂのステップ１７０７に対応する）を経て生成されるグラフである。
グラフ（１４０３）は、８行目の命令を読み込むステップ（図１７Ｂのステップ１７１３に対応する）を経て生成されるグラフである。
グラフ（１４０４）は、９、１０及び１１行目の命令を読み込むステップ（図１７Ｂのステップ１７１１に対応する）を経て生成されるグラフである。
グラフ（１４０５）は、グラフ（１４０４）中の全てのオブジェクト・ノードのエスケープ属性を全て「false」に初期化をするステップ（図１８Ａのステップ１８０２に対応する）を経て生成されるグラフである。
グラフ（１４０６）は、グラフ（１４０５）中の引数オブジェクトを表すオブジェクト・ノード及びメソッド呼び出しの返り値オブジェクトを表すオブジェクト・ノードのエスケープ属性を「true」にするステップ（図１８Ａのステップ１８０３に対応する）を経て得られるグラフである。本例では、「ｐａｒｍ０」のエスケープ属性が「true」に変わる。
グラフ（１４０７）は、グラフ（１４０６）中の、変数「ｒｅｔｕｒｎ」及び「ａｒｇ１」から指されるオブジェクト（「ｐａｒｍ０」）のエスケープ属性を「true」にする（図１８Ａのステップ１８０４に対応する）を経て得られるグラフである。
グラフ（１４０８）は、グラフ（１４０７）中にロード・ノード「９：（Ｌｏａｄ）」を追加するステップ（図１８Ａのステップ１８０５及び１８０６に対応する）を経て得られるグラフである。
グラフ（１４０９）は、グラフ（１４０８）中において、エスケープ属性が「true」であるオブジェクト（「７：Ｄａｔａ」）から指されるオブジェクト（「９：Ｌｏａｄ」）のエスケープ属性を「true」にするステップ（図１８Ａのステップ１８０７及び１８０８に対応する）を経て得られるグラフである。この段階で、「ｍｅｔｈｏｄ１」に関するポイント・ツー・グラフが完成する。
ここで、アクセス箇所を知りたいオブジェクトが、例えば「７：Ｄａｔａ」であるとする。グラフ（１４１０）に示されているように、「７：Ｄａｔａ」のエスケープ属性が「true」であるので（図１８Ｂのステップ１８０９を参照）、グラフ（１４１０）の矢印を逆方向に辿り（図１８Ｂのステップ１８１０を参照）、変数「ａｒｇ１」に到達するので、「７：Ｄａｔａ」は「８：ｍｅｔｈｏｄ２」にエスケープすることがわかる（図１８Ｂのステップ１８１３を参照）。そこで、「ｍｅｔｈｏｄ２」をスニッフする必要があることが分かる。
グラフ（１４１１）は、「ｍｅｔｈｏｄ２」をスニッフするために、１２行目の命令を読み込むステップ（図１７Ａのステップ１７０２に対応する）を経て生成されるグラフである。
グラフ（１４１２）は、１４行目の命令を読み込むステップ（図１７Ａのステップ１７０２に対応する）を経て生成されるグラフである。
グラフ（１４１３）は、「ｍｅｔｈｏｄ２」についてのグラフ（１４１２）を「ｍｅｔｈｏｄ１」についてのグラフ（１４１０）にマージするステップ（図１６のステップ１６０７に対応する）を経て生成されるグラフである。本例では、グラフ（１４１２）中の「ｍｅｔｈｏｄ２」から指される「ｐａｒｍ０」及び「ｐａｒｍ１」がグラフ（１４１０）中の「ｍｅｔｈｏｄ１」から指される「ｐａｒｍ０」及び「７：Ｄａｔａ」にそれぞれ対応するので、対応するオブジェクト同士がマージされる。なお、コード（１３０１ａ）の８行目の「ｍｅｔｈｏｄ２」呼び出しは解析済みであるので、「８：ｍｅｔｈｏｄ２」は削除される。
グラフ（１４１４）は、「８：ｍｅｔｈｏｄ２」が削除されている点以外は、図１３Ａの上段に示すポインタ解析により得られるポイント・ツー・グラフ（１３１２）に対応する。なお、グラフ（１４１４）では、エスケープ属性は通常記載しないので、エスケープ属性が記載されていない。
【００９６】
図１４Ｄは、図１３Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフ（１３２２）の生成の詳細を示す図である。以下では、経時的に生成されるグラフの順に説明する。ただし、図１４Ｄに示されているグラフが経時的に生成されるグラフの全てを示すものではない。
図１４Ａ〜図１４Ｃのグラフ（１４０１〜１４１２）が、本ポインタ解析によっても生成される。従って、それらの説明は省略する。
グラフ（１４２３）は、「ｍｅｔｈｏｄ２」についてのグラフ（１４１２）を「ｍｅｔｈｏｄ１」についてのグラフ（１４１０）にマージするステップ（図１６のステップ１６０７に対応する）を経て生成されるグラフである。本例では、グラフ（１４１２）中の「ｍｅｔｈｏｄ２」から指される「ｐａｒｍ０」及び「ｐａｒｍ１」がグラフ（１４１０）中の「ｍｅｔｈｏｄ１」から指される「ｐａｒｍ０」及び「７：Ｄａｔａ」にそれぞれ対応するので、対応するオブジェクト同士がマージされる。なお、コード（１３０１ａ）の８行目の「ｍｅｔｈｏｄ２」呼び出しは解析済みであるので、「８：ｍｅｔｈｏｄ２」は削除される。また、グラフ（１４２３）では、「ｍｅｔｈｏｄ１」から指される「ｐａｒｍ０」の「ｄａｔａ」フィールドが「９：（Ｌｏａｄ）」と「７：Ｄａｔａ」の２つのオブジェクトを指すようになるので、「９：（Ｌｏａｄ）」と「７：Ｄａｔａ」とが統合されている。
グラフ（１４２４）は、「８：ｍｅｔｈｏｄ２」が削除されている点以外は、図１３Ａの下段に示すポインタ解析により得られるポイント・ツー・グラフ（１３２２）に対応する。この段階で、「ｍｅｔｈｏｄ２」に関するポイント・ツー・グラフが完成する。なお、グラフ（１４２４）では、エスケープ属性は通常記載しないので、エスケープ属性が記載されていない。
【００９７】
図１４Ｅは、図１３Ａの下段に示すポインタ解析において、さらにポインタ解析が必要であることを説明する図である。
ここで、アクセス箇所を知りたいオブジェクトが、例えば「７：Ｄａｔａ」であるとする。グラフ（１４３１）は、グラフ（１４２３）と同じである。グラフ（１４３１）に示されているように、「７：Ｄａｔａ」のエスケープ属性は「true」であるので（図１８Ｂのステップ１８０９を参照）、グラフ（１４３１）の矢印を逆方向に辿り（１４３２）（図１８Ｂのステップ１８１０を参照）、「ｍｅｔｈｏｄ１」から指されている「ｐａｒｍ０」に到達するので、「７：Ｄａｔａ」は「ｍｅｔｈｏｄ１」の呼び出し元にエスケープすることがわかる（図１８Ｂのステップ１８１３を参照）。従って、通常のインクリメンタライズド技法による解析では、「ｍｅｔｈｏｄ１」の呼び出し元である「ｍｅｔｈｏｄ０」をさらにスニッフする必要がある。そのために、さらにグラフが大きくなる。
【００９８】
図１４Ｆ及び図１４Ｇは、図１３Ａの上段及び下段に示すポインタ解析では、グラフがさらに大きくなることを示す図である。
図１４Ａ〜図１４Ｃのグラフ（１４０１〜１４１２）、及び図４Ｄのグラフ（１４２３）が、本ポインタ解析によっても生成される。従って、それらの説明は省略する。
グラフ（１４４５）は、「ｍｅｔｈｏｄ１」の呼び出し元である「ｍｅｔｈｏｄ０」をさらにスニッフするために、コード（１３０１ａ）中の３行目の命令を読み込むステップ（図１７Ａのステップ１７０２に対応する）を経て生成されるグラフである。
グラフ（１４４６）は、４及び５行目の命令を読み込むステップ（図１７Ｂのステップ１７１２に対応する）を経て生成されるグラフである。
グラフ（１４４７）は、「ｍｅｔｈｏｄ０」についてのグラフ（１４４６）を「ｍｅｔｈｏｄ１」についてのグラフ（１４４４）にマージするステップ（図１６のステップ１６０７に対応する）を経て生成されるグラフである。本例では、グラフ（１４４６）中の「ｍｅｔｈｏｄ０」から指される「ｐａｒｍ０」がグラフ（１４４４）中の「ｍｅｔｈｏｄ１」から指される「ｐａｒｍ０」に対応するので、対応するオブジェクト同士がマージされる。なお、コード（１３０１ａ）の４行目の「ｍｅｔｈｏｄ１」呼び出しは解析済みであるので、「４：ｍｅｔｈｏｄ１」は削除される。
グラフ（１４４８）は、「ｍｅｔｈｏｄ０」の解析結果を示すグラフである。グラフ（１４４８）は、グラフ（１４２４）と比べて大きくなっている。また、グラフ（１４４７）において、「７：Ｄａｔａ」のエスケープ属性は「true」であるので（図１８Ｂのステップ１８０９を参照）、グラフ（１４４７）の矢印を逆方向に辿り（図１８Ｂのステップ１８１０を参照）、「ｍｅｔｈｏｄ０」から指されている「ｐａｒｍ０」に到達するので、「７：Ｄａｔａ」は「ｍｅｔｈｏｄ０」の呼び出し元にエスケープすることがわかる（図１８Ｂのステップ１８１３を参照）。従って、通常のインクリメンタライズド技法による解析では、「ｍｅｔｈｏｄ０」の呼び出し元であるメソッドをさらにスニッフする必要がある。そのために、さらにグラフが大きくなる。
【００９９】
図１４Ｈは、図１３Ｂの上段に示すポインタ解析により得られるポイント・ツー・グラフの生成の詳細を示す図である。以下では、経時的に生成されるグラフの順に説明する。ただし、図１４Ｈに示されているグラフが経時的に生成されるグラフの全てを示すものではない。
図１４Ａ〜図１４Ｃのグラフ（１４０１〜１４１２）及び図１４Ｃのグラフ（１４１３）が、本ポインタ解析によっても生成される。従って、それらの説明は省略する。
グラフ（１４５４）において、「７：Ｄａｔａ」のエスケープ属性は「true」であるので（図１８Ｂのステップ１８０９を参照）、グラフ（１４５４）の矢印を逆方向に辿り（図１８Ｂのステップ１８１０を参照）、「ｍｅｔｈｏｄ１」から指されている「ｐａｒｍ０」の「ｄａｔａ」フィールドに到達する。ｄａｔａフィールドはプライベート・フィールドであり、その読み出し箇所はコード（１３０１ｂ）の９行目のみである。ここで、９行目で読み出されるオブジェクトに対応するロード・ノード（「９：Ｄａｔａ」）は既に解析済みである。従って、「ｍｅｔｈｏｄ１」の呼び出し元である「ｍｅｔｈｏｄ０」をさらにスニッフする必要はない。このように、本発明の実施態様に従うと、解析が「７：Ｄａｔａ」から「ｐａｒｍ０」に到達しなかったので、「７：Ｄａｔａ」はエスケープしないとみなされる（図１８Ｂのステップ１８１３を参照）。よって、図１３Ｂの上段に示すポインタ解析は、この段階で終了する（図１６のステップ１６０５においてＮｏであることに対応する）。従って、この先の解析は行われないことから、解析時間の短縮及び必要なメモリが節約できる。
【０１００】
図１４Ｉは、図１３Ｂの下段に示すポインタ解析により得られるポイント・ツー・グラフ（１３４２）の生成の詳細を示す図である。以下では、経時的に生成されるグラフの順に説明する。ただし、図１４Ｉに示されているグラフが経時的に生成されるグラフの全てを示すものではない。グラフ（１４６４）は、グラフ（１４２３）と同じである。
図１４Ａ〜図１４Ｃのグラフ（１４０１〜１４１２）及び図１４Ｄのグラフ（１４２３）が、本ポインタ解析によっても生成される。従って、それらの説明は省略する。
グラフ（１４６４）において、「７：Ｄａｔａ」のエスケープ属性は「true」であるので（図１８Ｂのステップ１８０９を参照）、グラフ（１４６４）の矢印を逆方向に辿り（図１８Ｂのステップ１８１０を参照）、「ｍｅｔｈｏｄ１」から指されている「ｐａｒｍ０」の「ｄａｔａ」フィールドに到達する。ｄａｔａフィールドはプライベート・フィールドであり、その読み出し箇所はコード（１３０１ｂ）の９行目のみである。ここで、９行目で読み出されるオブジェクトに対応するロード・ノード（「９：Ｄａｔａ」）は既に解析済みである。従って、「ｍｅｔｈｏｄ１」の呼び出し元である「ｍｅｔｈｏｄ０」をさらにスニッフする必要はない。このように、本発明の実施態様に従うと、解析が「７：Ｄａｔａ」から「ｐａｒｍ０」に到達しなかったので、「７：Ｄａｔａ」はエスケープしないとみなされる（図１８Ｂのステップ１８１３を参照）。よって、図１３Ｂの下段に示すポインタ解析は、この段階で終了する（図１６のステップ１６０５においてＮｏであることに対応する）。従って、この先の解析は行われないことから、解析時間の短縮及び必要なメモリが節約できる。
【０１０１】
図１５Ａは、本発明の実施形態におけるコンピュータ・ハードウェアの基本的なブロック図を示す。
コンピュータ（１５０１）は、ＣＰＵ（１５０２）とメイン・メモリ（１５０３）とを備えており、これらはバス（１５０４）に接続されている。ＣＰＵ（１５０２）は好ましくは、３２ビット又は６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＣｏｒｅ  ｉ（商標）シリーズ、Ｃｏｒｅ  ２（商標）シリーズ、Ａｔｏｍ（商標）シリーズ、Ｘｅｏｎ（商標）シリーズ、Ｐｅｎｔｉｕｍ（登録商標）シリーズ、Ｃｅｌｅｒｏｎ（登録商標）シリーズ、ＡＭＤ社のＰｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（商標）シリーズ又はＳｅｍｐｒｏｎ（商標）が使用されうる。バス（１５０４）には、ディスプレイ・コントローラ（１５０５）を介して、ディスプレイ（１５０６）、例えば液晶ディスプレイ（ＬＣＤ）が接続されうる。ディスプレイ（１５０６）は、コンピュータの管理のために、通信回線を介してネットワークに接続されたコンピュータについての情報と、そのコンピュータ上で動作中のソフトウェアについての情報を、適当なグラフィック・インタフェースで表示するために使用される。バス（１５０４）にはまた、ＳＡＴＡ又はＩＤＥコントローラ（１５０７）を介して、記憶装置（１５０８）、例えばハードディスク又はシリコン・ディスクと、ドライブ（１５０９）、例えばＣＤ、ＤＶＤ又はＢＤドライブとが接続されうる。バス（１５０４）にはさらに、キーボード・マウスコントローラ（１５１０）又はＵＳＢバス（図示せず）を介して、キーボード（１５１１）及びマウス（１５１２）が接続されうる。
【０１０２】
記憶装置（１５０８）には、オペレーティング・システム、Ｊ２ＥＥなどのＪａｖａ（登録商標）処理環境、Ｊａｖａ（登録商標）アプリケーション、Ｊａｖａ（登録商標）仮想マシン（ＶＭ）、Ｊａｖａ（登録商標）実行時（ＪＩＴ）コンパイラを提供するプログラム、その他のプログラム、及びデータが、メイン・メモリにロード可能に記憶されている。
ドライブ（１５０９）は、必要に応じて、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はＢＤからプログラムを記憶装置（１５０８）にインストールするために使用される。
【０１０３】
通信インタフェース（１５１４）は、例えばイーサネット（登録商標）・プロトコルに従う。通信インタフェース（１５１４）は、通信コントローラ（１５１３）を介してバス（１５０４）に接続され、コンピュータ（１５０１）を通信回線（１５１５）に物理的に接続する役割を担い、コンピュータ（１５０１）のオペレーティング・システムの通信機能のＴＣＰ／ＩＰ通信プロトコルに対して、ネットワーク・インタフェース層を提供する。なお、通信回線は、有線ＬＡＮ環境、又は例えばＩＥＥＥ８０２．１１ａ／ｂ／ｇ／ｎなどの無線ＬＡＮ接続規格に基づく無線ＬＡＮ環境であってもよい。
【０１０４】
図１５Ｂは、図１５Ａに示すコンピュータ・ハードウェアの機能を有し、本発明の実施態様に従うシステムの機能ブロック図を示す。
図１５Ｂは、本発明の実施態様に従うコンピュータ（１５０１）が備えているコンパイラ部（１５２１）の機能ブロック図を示す。
コンピュータ（１５０１）は、図１５Ａに示す例えばＣＰＵ（１５０２）、メイン・メモリ（１５０３）及び記憶装置（１５０８）に加えて、コンパイラ部（１５２１）を備えている。コンパイラ部（１５２１）は、グラフ作成部（１５３１）及び検出部（１５３２）を備えている。コンピュータ（１５０１）はさらに、コード最適化部（１５３３）を備えうる。
【０１０５】
グラフ作成部（１５３１）は、コンパイラによって、コンパイル対象のメソッドを対象として、解析対象であるプログラム又はその一部のプログラムに対するフロー・インセンシティブな１つのポイント・ツー・グラフをメモリ（１５０３）又は記憶送致（１５０８）内に作成する。
【０１０６】
本発明の１つの実施態様において、グラフ作成部（１５３１）は、上記１つのポイント・ツー・グラフをメモリ内に作成するために、
（ａ）アクセス箇所を検出したいオブジェクトが特定されることに応じて、当該特定されたオブジェクトを生成するメソッド（最初のメソッド）を対象として、フロー・インセンシティブな第１のポイント・ツー・グラフを作成すること、
（ｂ）上記作成された第１のポイント・ツー・グラフを使用して、上記アクセス箇所を検出したいオブジェクトが、上記最初のメソッドの呼び出し元の少なくとも１のメソッド（第１の呼び出し元のメソッド）に又は上記最初のメソッドから呼び出される側の少なくとも１のメソッド（第１の呼び出される側のメソッド）にエスケープするかどうかを検出することを実行する。そして、グラフ作成部（１５３１）は、上記第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）上記第１の呼び出し元のメソッドから又は上記第１の呼び出される側のメソッドから到達可能であること且つ（２）上記第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第１のロード・ノードを上記第１のポイント・ツー・グラフ中に用意して、当該第１のポイント・ツー・グラフを更新することを含む。言い換えれば、グラフ作成部（１５３１）は、上記第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが上記第１の呼び出し元のメソッドから到達不可能であり且つ上記第１の呼び出される側のメソッドから到達不可能である場合に、又は、上記第１のポイント・ツー・グラフ中のオブジェクトを指している状態である場合に、第１のロード・ノードを上記第１のポイント・ツー・グラフ中に用意することを禁止する。ここで、上記第１のロード・ノードが、上記更新された第１のポイント・ツー・グラフ中において上記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される。
【０１０７】
本発明の上記１つの実施態様において、グラフ作成部（１５３１）は、さらに、
（ｃ）上記アクセス箇所を検出したいオブジェクトが上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドにエスケープすることに応じて、上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドを対象として、フロー・インセンシティブな第２のポイント・ツー・グラフを作成し、上記第１のロード・ノードが用意されている場合には上記更新された第１のポイント・ツー・グラフに又は上記第１のロード・ノードが用意されていない場合には前記第１のポイント・ツー・グラフに上記第２のポイント・ツー・グラフをマージすること、
（ｄ）上記マージされた第１のポイント・ツー・グラフを使用して、上記アクセス箇所を検出したいオブジェクトがこれまでのステップにおいて解析されたメソッドの呼び出し元のメソッドのうちまだ解析されていないメソッド（第２の呼び出し元のメソッド）に又は上記これまでのステップにおいて解析されたメソッドから呼び出される側のメソッドのうちまだ解析されていないメソッド（第２の呼び出される側のメソッド）にエスケープするかどうかを検出することであって、上記マージされた第１のポイント・ツー・グラフ中の少なくとも１のオブジェクトのフィールドが、（１）上記第２の呼び出し元のメソッドから又は上記第２の呼び出される側のメソッドから到達可能であること且つ（２）上記マージされた第１のポイント・ツー・グラフ中のオブジェクトを指していない状態であることを条件に、第２のロード・ノードを上記マージされた第１のポイント・ツー・グラフ中に用意して、当該マージされた上記第１のポイント・ツー・グラフを更新することを含み、上記第２のロード・ノードが、上記更新されたマージされた第１のポイント・ツー・グラフ中において上記アクセス箇所を検出したいオブジェクトがエスケープするかどうかを検出するために使用される、上記検出すること、及び
（ｅ）上記アクセス箇所を検出したいオブジェクトがエスケープしなくなるまで、又は、上記最初のメソッド以外の解析対象のメソッドが所定のしきい値に達するまで、上記（ｃ）及び（ｄ）を繰り返すこと
をさらに実行しうる。
【０１０８】
本発明の１つの実施態様において、検出部（１５３２）は、上記アクセス箇所を検出したいオブジェクトが上記第１の呼び出し元のメソッド又は上記第１の呼び出される側のメソッドにエスケープしないことに応じて、上記第１のロード・ノードが用意されている場合には上記更新された第１のポイント・ツー・グラフを又は上記第１のロード・ノードが用意されていない場合には上記第１のポイント・ツー・グラフを辿って、上記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出する。
【０１０９】
本発明の上記１つの実施態様において、上記（ｅ）において最終的に得られたポイント・ツー・グラフを辿って、上記アクセス箇所を検出したいオブジェクトのアクセス箇所を検出することを実行する。
【０１１０】
コード最適化部（１５３３）は、検出部（１５３２）によって検出されたアクセス箇所を使用して、コードの最適化を行う。コードの最適化は、例えば、最後である可能性のあるアクセス・ポイントでキャッシュ・フラッシュ命令を挿入すること、アクセスされないようであるオブジェクトを圧縮された形式でメモリに割り当てること、オブジェクト中のフィールドを再配置すること、及びオブジェクトを遅延的に(lazily)メモリに割り当てることを包含する。
【０１１１】
図１６は、本発明の実施態様に従う、ポインタを解析する方法のフローチャートである。
ステップ１６０１では、コンピュータ（１５０１）は、解析対象であるプログラム又はその一部のプログラムにおけるポインタを解析するためのアルゴリズムを開始する。
【０１１２】
ステップ１６０２では、コンピュータ（１５０１）のグラフ作成部（１５３１）は、開発者又はコンピュータ（１５０１）によって特定された、アクセス箇所を検出したいオブジェクトを認識する。開発者が上記アクセス箇所を検出したいオブジェクトを特定する場合、当該開発者は、開発環境上において、例えば、グラフィカル・ユーザ・インタフェースを使用して、１又は複数のオブジェクトを特定する。コンピュータ（１５０１）が上記アクセス箇所を検出したいオブジェクトを特定する場合、コンピュータ（１５０１）は、例えば、コード最適化部（１５３３）が解析対象であるプログラム又はその一部のプログラムから、１又は複数のオブジェクトを特定する。
【０１１３】
ステップ１６０３では、グラフ作成部（１５３１）は、ステップ１６０２において特定されたオブジェクトを生成するメソッドを対象として、フロー・インセンシティブなポイント・ツー・グラフを作成する。以下、本ポイント・ツー・グラフを便宜的に第１のポイント・ツー・グラフと呼ぶ。ここで、ステップ１６０２において、アクセス箇所を検出したいオブジェクトが複数ある場合には、当該特定された各オブジェクトを生成するメソッド（最初のメソッド）を対象として、第１のポイント・ツー・グラフが作成されうる。第１のポイント・ツー・グラフの作成の詳細は、図１７においてさらに詳細に説明されている。
【０１１４】
ステップ１６０４では、グラフ作成部（１５３１）は、第１のポイント・ツー・グラフを使用して、ステップ１６０２で特定されたオブジェクトが、当該最初のメソッドの呼び出し元の少なくとも１のメソッド（第１の呼び出し元のメソッド）に又は当該最初のメソッドから呼び出される側の少なくとも１のメソッド（第１の呼び出される側のメソッド）にエスケープするかどうかを検出する。エスケープするかどうかを決定するアルゴリズムは、図１８Ａ〜図１８Ｂにおいてさらに詳細に説明されている。
【０１１５】
ステップ１６０５では、グラフ作成部（１５３１）は、ステップ１６０４の条件に従い、ステップ１６０２で特定されたオブジェクトが第１の呼び出し元のメソッドに、又は、第１の呼び出される側のメソッドにエスケープすることに応じて、処理をステップ１６０６に進める。一方、グラフ作成部（１５３１）は、エスケープしないことに応じて、処理をステップ１６０８に進める。
【０１１６】
ステップ１６０６では、グラフ作成部（１５３１）は、例えば、当該ステップまでに解析したメソッドの合計サイズ、解析時間又は必要なメモリ量が、所定のしきい値未満であるかどうかを判断する。グラフ作成部（１５３１）は、所定のしきい値未満であることに応じて、処理をステップ１６０７に進める。一方、グラフ作成部（１５３１）は、所定のしきい値以上であることに応じて、処理をステップ１６０８に進める。
【０１１７】
ステップ１６０７では、グラフ作成部（１５３１）は、エスケープする先の呼び出し元のメソッド（第１の呼び出し元のメソッド）又は呼び出される側のメソッド（第１の呼び出される側のメソッド）を対象として、フロー・インセンティブなポイント・ツー・グラフを作成する。以下、本ポイント・ツー・グラフを便宜的に第２のポイント・ツー・グラフと呼ぶ。第２のポイント・ツー・グラフの作成の詳細は、第１のポイント・ツー・グラフの作成と同様に、図１７Ａ及び図１７Ｂにおいてさらに詳細に説明する。そして、グラフ作成部（１５３１）は、ステップ１６０３において作成された第１のポイント・ツー・グラフに、又は、ステップ１６０３において作成された第１のポイント・ツー・グラフ中にステップ１６０４（より詳細には、図１８Ａのステップ１８０６）において用意されたロード・ノードが追加されたポイント・ツー・グラフ（更新された第１のポイント・ツー・グラフ）に、第２のポイント・ツー・グラフをマージする。その結果、マージされた第１のポイント・ツー・グラフが作成される。グラフ作成部（１５３１）は、更新された第１のポイント・ツー・グラフが作成されると、ステップ１６０４に戻り、当該更新された第１のポイント・ツー・グラフを使用して、ステップ１６０２で特定されたオブジェクトが、これまでのステップにおいて解析されたメソッドの呼び出し元のメソッドのうちまだ解析されていないメソッド（第２の呼び出し元のメソッド）に又はこれまでのステップにおいて解析されたメソッドから呼び出される側のメソッドのうちまだ解析されていないメソッド（第２の呼び出される側のメソッド）にエスケープするかどうかを検出する。以降、処理がステップ１６０５又はステップ１６０６からステップ１６０８に進むまで、ステップ１６０４〜ステップ１６０７が繰り返される。
【０１１８】
ステップ１６０８では、検出部（１５３２）は、ステップ１６０３で作成された第１のポイント・ツー・グラフ、又はステップ１６０４で更新された第１のポイント・ツー・グラフ、ステップ１６０７でマージされた第１のポイント・ツー・グラフを辿って、アクセス箇所を検出したいオブジェクトのアクセス箇所を検出する。
【０１１９】
ステップ１６０９では、コンピュータ（１５０１）は、ポインタを解析するためのアルゴリズムを終了する。
【０１２０】
図１７Ａ及び図１７Ｂは、図１６のフローチャートにおいて、フロー・インセンシティブなポイント・ツー・グラフを作成するステップ（１６０３及び１６０７）の詳細なフローチャートである。
ステップ１７０１では、グラフ作成部（１５３１）は、ポイント・ツー・グラフを作成するためのアルゴリズムを開始する。ポイント・ツー・グラフは、図１６のステップ１６０３又はステップ１６０７で作成されるグラフである。
【０１２１】
ステップ１７０２では、グラフ作成部（１５３１）は、（１）解析対象のメソッドの引数オブジェクトを表すオブジェクト・ノード（例えば、図１３Ｂ及び図１３Ｃの「ｐａｒｍ０」）と、（２）解析対象のメソッドの返り値を表す変数ノード（例えば、図１１Ａ及び１１Ｂの「ｒｅｔｕｒｎ」）とを含むポイント・ツー・グラフを初期化する。そして、グラフ作成部（１５３１）は、ステップ１７０２よりも後のステップにおいて、オブジェクト・ノードと変数ノードとを順次ポイント・ツー・グラフに追加していく。
【０１２２】
ステップ１７０３では、グラフ作成部（１５３１）は、解析対象のメソッドを全て読み込んだかどうかを判定する。グラフ作成部（１５３１）は、全て読み込んでいないことに応じて、処理をステップ１７０４に進める。一方、グラフ作成部（１５３１）は、全て読み込んでいることに応じて、処理をステップ１７１４に進める。
【０１２３】
ステップ１７０４では、グラフ作成部（１５３１）は、解析対象のメソッドから当該メソッドに関連する命令のうちの１行をメモリ内に読み込む。
【０１２４】
ステップ１７０５では、グラフ作成部（１５３１）は、読み込んだ１行が、頻繁に実行されるプログラム領域にあるプログラムであるかどうかを検査する。グラフ作成部（１５３１）は、読み込んだ１行が頻繁に実行されるプログラム領域にあるプログラムである場合、処理をステップ１７０６（図１７Ｂへ）に進める。一方、グラフ作成部（１５３１）は、読み込んだ１行が頻繁に実行されるプログラム領域にあるプログラムでない場合、処理をステップ１７０３に戻す。なお、ステップ１７０５は任意のステップであり、グラフ作成部（１５３１）は、ステップ１７０５をスキップして、処理をステップ１７０３からステップ１７０６に進めてもよい。
【０１２５】
ステップ１７０６では、グラフ作成部（１５３１）は、読み込んだ１行が、オブジェクト生成文であるかどうかを判断する。グラフ作成部（１５３１）は、オブジェクト生成文であることに応じて、処理をステップ１７０７に進める。一方、グラフ作成部（１５３１）は、オブジェクト生成文でないことに応じて、処理をステップ１７０８に進める。
【０１２６】
ステップ１７０７では、グラフ作成部（１５３１）は、ステップ１７０２で新たに作成されたポイント・ツー・グラフに、又はステップ１７０７、１７０９、１７１１若しくは１７１３で更新されたポイント・ツー・グラフに、通常のオブジェクト・ノードを追加して、（１）当該追加された通常のオブジェクト・ノードと、（２）代入先のローカル変数ノードが指すオブジェクト・ノードとを統合する。ステップ１７０７において行われるグラフの生成の例を図１７Ｃに示す。当該統合が終了することに応じて、グラフ作成部（１５３１）は、処理をステップ１７０３に戻す。
【０１２７】
ステップ１７０８では、グラフ作成部（１５３１）は、読み込んだ１行が、コピー文であるかどうかを判断する。グラフ作成部（１５３１）は、コピー文であることに応じて、処理をステップ１７０９に進める。一方、グラフ作成部（１５３１）は、コピー文でないことに応じて、処理をステップ１７１０に進める。
【０１２８】
ステップ１７０９では、グラフ作成部（１５３１）は、ステップ１７０２で更新されたポイント・ツー・グラフに、又はステップ１７０７、１７０９、１７１１若しくは１７１３で更新されたポイント・ツー・グラフにおいて、代入元のローカル変数ノードが指すオブジェクト・ノードと代入先のローカル変数ノードが指すオブジェクト・ノードとを統合する。当該統合が終了することに応じて、グラフ作成部（１５３１）は、処理をステップ１７０３に戻す。
【０１２９】
ステップ１７１０では、グラフ作成部（１５３１）は、読み込んだ１行が、ロード・ストア文であるかどうかを判断する。グラフ作成部（１５３１）は、ロード・ストア文であることに応じて、処理をステップ１７１１に進める。一方、グラフ作成部（１５３１）は、ロード・ストア文でないことに応じて、処理をステップ１７１２に進める。
【０１３０】
ステップ１７１１では、グラフ作成部（１５３１）は、ステップ１７０２で更新されたポイント・ツー・グラフに、又はステップ１７０７、１７０９、１７１１若しくは１７１３で更新されたポイント・ツー・グラフにおいて、ロード・ストア対象のオブジェクトのフィールド変数ノードがなければ、当該ロード・ストア対象のオブジェクトのフィールド変数ノードを追加し（図１１Ｂの「ｎｅｘｔ」）、（１）当該追加されたフィールド変数ノードが指すオブジェクト・ノードと、（２）代入元（ストア文の場合）又は代入先（ロード文の場合）のローカル変数ノードが指すオブジェクト・ノードとを統合する。ステップ１７１１において行われるグラフの生成の例を図１７Ｄに示す。当該統合が終了することに応じて、グラフ作成部（１５３１）は、処理をステップ１７０３に戻す。
【０１３１】
ステップ１７１２では、グラフ作成部（１５３１）は、読み込んだ１行が、メソッド呼び出し文であるかどうかを判断する。グラフ作成部（１５３１）は、メソッド呼び出し文であることに応じて、処理をステップ１７１３に進める。一方、グラフ作成部（１５３１）は、メソッド呼び出し文でないことに応じて、処理をステップ１７０３に戻す。
【０１３２】
ステップ１７１３では、グラフ作成部（１５３１）は、ステップ１７０２で更新されたポイント・ツー・グラフに、又はステップ１７０７、１７０９、１７１１若しくは１７１３で更新されたポイント・ツー・グラフに、メソッド・ノード（この段階で、スニッフしていないが、後の段階でスニッフされるかもしれないメソッドである）、メソッド呼び出しの引数を表す変数ノード（例えば、図１０Ｂ、並びに図１１Ａ及び図１１Ｂの「arg1」）、及びメソッド呼び出しの返り値のためのオブジェクトを表すオブジェクト・ノードを追加して、上記引数を表す変数ノードから上記引数へ代入されるオブジェクト・ノードへエッジを張り、（１）上記返り値のためのオブジェクトを表すオブジェクト・ノードと、（２）返り値の代入先のローカル変数が指すオブジェクト・ノードとを統合する。ステップ１７１３において行われるグラフの生成の例を図１７Ｅに示す。当該統合が終了することに応じて、グラフ作成部（１５３１）は、処理をステップ１７０３に戻す。
【０１３３】
ステップ１７１４では、グラフ作成部（１５３１）は、ポイント・ツー・グラフを作成するためのアルゴリズムを終了する。
【０１３４】
図１７Ｃは、図１７Ｂのステップ１７０７において行われるグラフの生成の例を説明するためのグラフである。解析対象であるプログラムの一部が、プログラム・コード（１７２１）であるとする。
ステップ１７３１はステップ１７０７で実行され、ステップ１７３１では、グラフ作成部（１５３１）は、コード（１７２１）中の１行目をメモリ内に読み込み、グラフを生成する。
ステップ１７３２はステップ１７０７で実行され、ステップ１７３２では、グラフ作成部（１５３１）は、２行目をメモリ内に読み込み、グラフを生成する。当該ステップにおいて、通常のオブジェクト・ノード（「２：Ｄａｔａ」）と、変数ノードａが指すオブジェクト・ノード（「１：Ｄａｔａ」）とが統合される。
【０１３５】
図１７Ｄは、図１７Ｂのステップ１７１１において行われるグラフの生成の例を説明するためのグラフである。解析対象であるプログラムの一部が、プログラム・コード（１７２２）であるとする。
ステップ１７４１はステップ１７０７で実行され、ステップ１７４１では、グラフ作成部（１５３１）は、コード（１７２２）中の１、２、３及び４行目をメモリ内に読み込み、グラフを生成する。
ステップ１７４２はステップ１７１１で実行され、ステップ１７４２では、グラフ作成部（１５３１）は、５行目をメモリ内に読み込み、グラフを生成する。当該ステップにおいて、フィールド変数ノード「next」が追加される。
ステップ１７４３はステップ１７１１で実行され、ステップ１７４３では、グラフ作成部（１５３１）は、６行目をメモリ内に読み込み、グラフを生成する。当該ステップにおいて、フィールド変数ノード「next」が指すオブジェクト・ノード（「２：Ｄａｔａ」）と、当該オブジェクト・ノード（「２：Ｄａｔａ」）を指す変数ノードｃが指すオブジェクト・ノード（「３：Ｄａｔａ」）とが統合される。
ステップ１７４４はステップ１７１１で実行され、ステップ１７４４では、グラフ作成部（１５３１）は、７行目をメモリ内に読み込み、グラフを生成する。当該ステップにおいて、フィールド変数ノード「next」が指すオブジェクト・ノード（「２：Ｄａｔａ」及び「３：Ｄａｔａ」）と、変数ノードｄが指すオブジェクト・ノード（「４：Ｄａｔａ」）とが統合される。
【０１３６】
図１７Ｅは、図１７Ｂのステップ１７１３において行われるグラフの生成の例を説明するためのグラフである。解析対象であるプログラムの一部が、プログラム・コード（１７２３）であるとする。
ステップ１７５１はステップ１７０２で実行され、ステップ１７５１では、グラフ作成部（１５３１）は、コード（１７２３）中の１行目をメモリ内に読み込み、グラフを生成する。
ステップ１７５２はステップ１７０７で実行され、ステップ１７５２では、グラフ作成部（１５３１）は、２行目をメモリ内に読み込み、グラフを生成する。
ステップ１７５３はステップ１７１３で実行され、ステップ１７５３では、グラフ作成部（１５３１）は、３及び４行目をメモリ内に読み込み、グラフを生成する。当該ステップにおいて、返り値オブジェクトを表すオブジェクト・ノード（「ｒｅｔｕｒｎ」）と、返り値の代入先のローカル変数「ａ」が指すオブジェクト・ノード（「１：Ｄａｔａ」）とが統合される。
【０１３７】
図１８Ａ及び図１８Ｂは、図１６のフローチャートにおいて、フロー・インセンシティブなポイント・ツー・グラフを使用して、アクセス箇所を検出したいオブジェクトが、呼び出し元のメソッドに又は呼び出される側のメソッドにエスケープするかどうかを検出するステップ（１６０４）の詳細なフローチャートである。
ステップ１８０１では、グラフ作成部（１５３１）は、アクセス箇所を検出したいオブジェクトが呼び出し元のメソッドに又は呼び出される側のメソッドにエスケープするかどうかを検出するアルゴリズムを開始する。
【０１３８】
ステップ１８０２では、グラフ作成部（１５３１）は、ステップ１６０３で作成されたポイント・ツー・グラフ、又はステップ１６０４若しくはステップ１６０７で更新されたポイント・ツー・グラフ中の全てのオブジェクト・ノードのエスケープ属性を「false」に初期化する。
【０１３９】
ステップ１８０３では、グラフ作成部（１５３１）は、引数オブジェクトを表すオブジェクト・ノード（例えば、図１３Ｂ及び図１３Ｃの「ｐａｒｍ０」）、及びメソッド呼び出しの返り値のためのオブジェクトを表すオブジェクト・ノードのエスケープ属性を「true」にする。
【０１４０】
ステップ１８０４では、グラフ作成部（１５３１）は、メソッド呼び出しの返り値を表す変数ノード（図１０Ｂの「return」）とメソッド呼び出しの引数を表す変数ノード（例えば、図１０Ｂ、並びに図１１Ａ及び図１１Ｂの「arg1」）とが指すオブジェクト・ノード（例えば、図１０Ｂの「２：Ｄａｔａ」及び「１０：Ｄａｔａ」）のエスケープ属性を「true」にする。
【０１４１】
ステップ１８０５では、グラフ作成部（１５３１）は、エスケープ属性が「true」であるオブジェクト・ノードのフィールド変数ノードが、いずれかのオブジェクト・ノードを指しているかどうかを判断する。グラフ作成部（１５３１）は、上記フィールド変数ノードがいずれかのオブジェクト・ノードを指していることに応じて、処理をステップ１８０７に進める。一方、グラフ作成部（１５３１）は、上記フィールド変数ノードがいずれかのオブジェクト・ノードを指していないことに応じて、処理をステップ１８０６に進める。
【０１４２】
ステップ１８０６では、グラフ作成部（１５３１）は、ステップ１６０３で作成されたポイント・ツー・グラフ、又はステップ１６０４若しくはステップ１６０７で更新されたポイント・ツー・グラフ中にロード・ノードを用意し、当該ロード・ノードがステップ１８０５のエスケープ属性が「true」であるオブジェクト・ノードのフィールド変数ノードから指されるように、上記当該ポイント・ツー・グラフを更新する。
【０１４３】
ステップ１８０７では、グラフ作成部（１５３１）は、エスケープ属性が「true」であるオブジェクト・ノードのフィールド変数ノードが、エスケープ属性が「false」であるオブジェクト・ノードを指しているかどうかを判断する。グラフ作成部（１５３１）は、上記フィールド変数ノードが、エスケープ属性が「false」であるオブジェクト・ノードを指していることに応じて、処理をステップ１８０８に進める。一方、グラフ作成部（１５３１）は、上記フィールド変数ノードが、エスケープ属性が「false」であるオブジェクト・ノードを指していないことに応じて、処理をステップ１８０９（図１８Ｂへ）に進める。
【０１４４】
ステップ１８０８では、グラフ作成部（１５３１）は、エスケープ属性が「true」であるオブジェクト・ノードのフィールド変数ノードが指すオブジェクト・ノードのエスケープ属性を「true」にする。
【０１４５】
ステップ１８０９では、グラフ作成部（１５３１）は、アクセス箇所を検出したいオブジェクトを表すオブジェクト・ノードのエスケープ属性が「true」であるかどうかを判断する。グラフ作成部（１５３１）は、上記エスケープ属性が「true」であることに応じて、処理をステップ１８１０に進める。一方、グラフ作成部（１５３１）は、上記エスケープ属性が「true」でないことに応じて、処理をステップ１８１１に進める。
【０１４６】
ステップ１８１０では、グラフ作成部（１５３１）は、アクセス箇所を検出したいオブジェクトを表すオブジェクト・ノードのエスケープ属性が「true」であることに応じて、当該アクセス箇所を検出したいオブジェクトを表すオブジェクト・ノードを指す変数ノードと、オブジェクト・ノード（アクセス箇所を検出したいオブジェクト・ノード以外のプログラム中にあるその他のオブジェクト・ノードである）とを再帰的に辿る。グラフ作成部（１５３１）は、引数オブジェクトを表すオブジェクト・ノード、又は返り値を表す変数ノードに到達したら、アクセス箇所を検出したいオブジェクトを呼び出し元のメソッドにエスケープするとみなし、メソッド呼び出しの引数を表す変数ノード、又は返り値オブジェクトを表すオブジェクト・ノードに到達したら、アクセス箇所を検出したいオブジェクトを呼び出される側のメソッドにエスケープするとみなす。
【０１４７】
ステップ１８１１では、グラフ作成部（１５３１）は、アクセス箇所を検出したいオブジェクトを表すオブジェクト・ノードのエスケープ属性が「true」でないことに応じて、当該アクセス箇所を検出したいオブジェクトを表すオブジェクトがエスケープしないとみなす。
【０１４８】
ステップ１８１２では、グラフ作成部（１５３１）は、辿る最中に訪れたフィールド変数ノードがプライベート・フィールドを表しており、且つその全ての読み出し箇所に対応するロード・ノード又はそれに対応するノードのアクセス箇所が解析済み（例えば、アクセス箇所を検出したいオブジェクトからエッジを逆に辿って到達可能である）であるならば、そのフィールド変数ノードから先には辿らない。
【０１４９】
ステップ１８１３では、グラフ作成部（１５３１）は、再帰的に辿った結果、引数オブジェクトを表すオブジェクト・ノード、又は返り値を表す変数ノードに到達したら、アクセス箇所を検出したいオブジェクトを呼び出し元のメソッドにエスケープするとみなし、メソッド呼び出しの引数を表す変数ノード、又は返り値オブジェクトを表すオブジェクト・ノードに到達したら、アクセス箇所を検出したいオブジェクトを呼び出される側のメソッドにエスケープするとみなす。
【０１５０】
ステップ１８１４では、グラフ作成部（１５３１）は、アクセス箇所を検出したいオブジェクトが呼び出し元のメソッドに又は呼び出される側のメソッドにエスケープするかどうかを検出するアルゴリズムを終了する。
【０１５１】
図１９は、本発明の実施態様に従うポインタ解析において使用されるメモリ使用量の削減効果の実験結果を示す図である。
実験は、Ｌｉｎｕｘ（商標）  ｐ６  ４．７ＧＨｚ×１６上でＩＢＭ（商標）ｐｐｃ−３２  Ｊ９／ＴＲ  Ｊａｖａ（登録商標）６（ＳＲ６）に、下記に示すポインタ解析のアルゴリズムを実装して評価された。ポインタ解析のアルゴリズムは、（１）既存のポインタ解析（単純なフロー・インセンティブ技法による解析）、（２）本発明の第１の実施態様に従うポインタ解析（プライベート・フィールドを考慮した解析、図１３Ａ〜図１３Ｃを参照）、及び（３）本発明の第２の実施態様に従うポインタ解析（不要なロード・ノード生成の抑制、図１１Ａを参照）の３つである。ベンチマーク・ソフトウェアとして、SPEC(Standard Performance Evaluation Corporation)jbb2005(Java Server Benchmark)、compiler.compiler、及びxml.validationの３種類のベンチマーク・プログラムを使用した。その結果を図１９に示す。
【０１５２】
（SPECjbb2005によるベンチマーク結果）
本発明に従う第１の実施態様に従うポインタ解析では、既存のポインタ解析に比べて、最大メモリ使用量が７４％に抑えられた。また、本発明に従う第２の実施態様に従うポインタ解析では、既存のポインタ解析に比べて、最大メモリ使用量が６２．９％に抑えられた。
【０１５３】
（compiler.compilerによるベンチマーク結果）
本発明に従う第２の実施態様に従うポインタ解析では、既存のポインタ解析に比べて、最大メモリ使用量が８．６％に減少した。
【０１５４】
（xml.validationによるベンチマーク結果）
本発明に従う第２の実施態様に従うポインタ解析では、既存のポインタ解析に比べて、最大メモリ使用量が５．２％に減少した。
【０１５５】
図２０は、ポインタ解析の結果を使用して、エイリアス解析を行い、コードの最適化を行う例を示す図である。
エイリアス解析とは、変数が同じオブジェクトを複数の名前で参照しているか否かを判定することをいう。
プログラム・コード（２００１）を対象として、ポインタ解析（２００２）を行ったところ、ポイント・ツー・グラフ（２００３）が得られたとする。ポイント・ツー・グラフ（２００３）から、変数「ａ」と変数「ｂ」とが指すオブジェクト（の集合）は重ならないことがわかる。すなわち、変数「ａ」と変数「ｂ」とは、必ず違うオブジェクトを指す。従って、プログラム・コード（２００１）は、コード最適化部（１５３３）によって自動的に又は開発者によって最適化され（２００４）、プログラム・コード（２００５）が作成される。当該最適化において、コード（２００５）の７行目に示されているように、コード（２００１）の７行目「y=a.field」が「y=x」へと書き換えられている。
【０１５６】
図２１は、ポインタ解析の結果を使用して、オブジェクトのアクセス解析を行い、コードの最適化を行う例を示す図である。
プログラム・コード（２１０１）を対象として、ポインタ解析（２１０２）を行ったところ、ポイント・ツー・グラフ（２１０３）が得られたとする。ポイント・ツー・グラフ（２１０３）から、コード（２１０１）の６行目で割り付けたオブジェクトを指すのは変数「ａ」及び変数「ｂ」だけであることがわかる。よって、変数「ａ」と変数「ｂ」の使用箇所を調べることで、６行目で割り付けたＤａｔａオブジェクトに最後にアクセスする箇所は３行目のコードであることがわかる。従って、プログラム・コード（２１０１）は、コード最適化部（１５３３）によって自動的に又は開発者によって最適化され（２１０４）、プログラム・コード（２１０５）が作成される。当該最適化において、コード（２１０５）の３行目の直後に示されているように、コード（２１０５）の３行目「use(b.field)」の直後に、ＤａｔａオブジェクトをＣＰＵのキャッシュから追い出す命令「cache_flush(b)」が挿入されている。このように、最後である可能性のあるアクセス・ポイントでキャッシュ・フラッシュ命令「cache_flush(b)」が挿入されることで、コンピュータはキャッシュを有効に利用することができる。
【０１５７】
図２２は、ポインタ解析の結果を使用して、オブジェクトの圧縮を行い、コードの最適化を行う例を示す図である。
図２２は、通常のオブジェクト・フォーマットが圧縮により変形されたオブジェクト・フォーマットの例を示す。
圧縮により変形されるとは例えば、ある文字配列(character array(s))又はある部位に割り当てられた文字配列がアクセスされない傾向にあり且つそれら文字配列がアスキー（ＡＳＣＩＩ）文字列のみを含む場合に、当該文字配列が圧縮されうることをいう。オブジェクトの圧縮は、オブジェクト・アクセスの最適化をもたらす。
【０１５８】
オブジェクト・フォーマット（２２０１）は、通常のフォーマットを示す。オブジェクト・フォーマット（２２０２）は、オブジェクト・フォーマット（２２０１）が圧縮により変形された場合のフォーマットを示す。
オブジェクト・フォーマット（２２０１）は、ヘッダ（２２１１）並びに、ヌル値のデータ・フィールド（２２１２、２２１４、２２１６及び２２１８）及びアスキーのデータ・フィールド（２２１３、２２１５、２２１７及び２２１９）を含む。オブジェクト・フォーマット（２２０２）は、ヘッダ（２２２１）及び、アスキーのデータ・フィールド（２２２２〜２２２５）を含む。
【０１５９】
変形されたオブジェクト・フォーマット（２２０２）では、オブジェクト・フォーマット（２２０１）のヌル値のデータ・フィールド（２２１２、２２１４、２２１６及び２２１８）が削除され、且つアスキーのデータ・フィールド（２２１３、２２１５、２２１７及び２２１９）が結合されている。変形されたオブジェクト・フォーマット（２２０２）のデータ・フィールドの数は４であり、オブジェクト・フォーマット（２２０１）のデータ・フィールドの数は８であることから、変形されたオブジェクト・フォーマット（２２０２）のデータ・フィールドはオブジェクト・フォーマット（２２０１）のデータ・フィールドの半分に圧縮されている。変形されたオブジェクト・フォーマット（２２０２）では、データ・フィールドの数が圧縮されているので、オブジェクト・フォーマット（２２０１）に比べてメモリのコストを低減することが可能である。オブジェクトの圧縮方法については、多くの知られている方法がある。
【０１６０】
本発明の実施態様に従い、プログラム・コードをポインタ解析し、その結果として得られたポイント・ツー・グラフから、オブジェクトがほとんどアクセスされないことがわかったとする。コード最適化部（１５３３）又は開発者は、ほとんどアクセスされないようであるオブジェクトを圧縮した形式で（例えば、上記のように値として０を含むデータ・フィールドを省略することで）メモリに割り当てられるようにコードを最適化する。当該最適化によって、メモリの使用量を減らすことができる。
【０１６１】
図２３は、ポインタ解析の結果を使用して、頻繁にアクセスされるフィールドの再配置を行い、コードの最適化を行う例を示す図である。
フィールド再配置とは例えば、オブジェクト中の２つ又はそれ以上のフィールドが同時にアクセスされる傾向にある場合に、当該２つ又はそれ以上のフィールドについてのデータキャッシュミスを減少させるために、当該２つ又はそれ以上のフィールドが隣接場所に配置（co-locate）されることを示す。
【０１６２】
オブジェクト・フォーマット（２３０１）は、通常のフォーマットを示す。オブジェクト・フォーマット（２３０２）は、オブジェクト・フォーマット（２３０１）が変形された場合のフォーマットを示す。
オブジェクト・フォーマット（２３０１）は、ヘッダ（２３１１）及び、データ・フィールドを１〜６（２３１２〜２３１７）の順で含む。オブジェクト・フォーマット（２３０２）は、ヘッダ（２３２１）及び、データ・フィールドを１、６、３、４、５及び２（２３２１〜２３２７）の順で含む。データ・フィールド１（２３１２）及びデータ・フィールド６（２３１７）は、同時にアクセスされる傾向にあるとする。
オブジェクト・フォーマット（２３０１）では、同時にアクセスされる傾向にあるデータ・フィールド１（２３１２）及びデータ・フィールド６（２３１７）が離れて存在している。そこで、変形されたオブジェクト・フォーマット（２３０２）では、同時にアクセスされる傾向にあるデータ・フィールド６（２３２３）がデータ・フィールド１（２３２２）の隣に位置するように最適化されている。変形されたオブジェクト・フォーマット（２３０２）では、データ・フィールド１（２３２２）及びデータ・フィールド６（２３２３）が同時にアクセスされうるので、オブジェクト・フォーマット（２３０１）に比べてメモリ・アクセスのコストを低減することが可能である。
【０１６３】
本発明の実施態様に従い、プログラム・コードをポインタ解析し、その結果として得られたポイント・ツー・グラフから、オブジェクトのうちの特定の幾つかのフィールドが同時にアクセスされることがわかったとする。コード最適化部（１５３３）又は開発者は、それらのフィールドをオブジェクト中で近い位置に再配置されるようにコードを最適化する。当該最適化によって、同じキャッシュラインに乗せることが可能になるので、キャッシュ・ミスを減らすことが可能である。
【０１６４】
図２４Ａは、ポインタ解析の結果を使用して、オブジェクトを遅延的に生成し、コードの最適化を行う例を示す図である。
ポインタを使用して文字配列を指定するとは例えば、ある部位に割り当てられた複数のストリング・オブジェクトがアクセスされない傾向にあり且つそれらストリング・オブジェクトが他のストリング・オブジェクトと連結されることによって生成される場合に、当該連結されうる文字配列がポインタを使用して文字配列を指定されることをいう。当該ポインタを使用する文字配列の割り当ては、遅延的に(lazily)生じうる。遅延割り当ては、オブジェクトが実際に必要とされるまで当該オブジェクトを割り当てない。従って、遅延割り当ては、オブジェクト・アクセスの最適化をもたらす。
【０１６５】
オブジェクト・フォーマット（２４０１）は、通常のフォーマットを示す。オブジェクト・フォーマット（２４０２）は、オブジェクト・フォーマット（２４０１）が変形された場合のフォーマットを示す。
【０１６６】
オブジェクト・フォーマット（２４０１）では、文字配列（２４１２）及び文字配列（２４２２）の２つが異なる位置に割り当てられている場合に、文字配列（２４１２）及び文字配列（２４２２）が結合されて、文字配列（オブジェクト・フォーマット（２４３２）が新たに生成されることを示す。文字配列（２４３２）の生成は、遅延的に生じうる。オブジェクト・フォーマット（２４０２）では、文字配列（２４４２）及び文字配列（２４５２）が異なる位置に割り当てられている場合に、文字配列（２４４２）及び文字配列（２４５２）のそれぞれが、２つのポインタ（２４６２及び２４６３）を使用して指定されることを示す。
【０１６７】
変形されたオブジェクト・フォーマット（２４０２）では、オブジェクト・フォーマット（２４０１）の文字配列（２４３２）の代わりに２つのポインタ（２４６２及び２４６３）を有している点で異なっている。オブジェクト・フォーマット（２４０２）では、文字配列（２４３２）の代わりに２つのポインタ（２４６２及び２４６３）で済むことから、メモリのコストを低減することが可能である。
【０１６８】
本発明の実施態様に従い、プログラム・コードをポインタ解析し、その結果として得られたポイント・ツー・グラフから、オブジェクトが特定のパスでしか使われないことがわかったとする。コード最適化部（１５３３）又は開発者は、オブジェクトの生成を当該特定のパスの実行まで遅らせるようにコードを最適化する。すなわち、オブジェクトを遅延的にメモリに割り当てる。当該最適化によって、別のパスを実行した時のメモリ使用量を減らすことができる。
【０１６９】
図２４Ｂは、ポインタ解析の結果を使用して、オブジェクトを遅延的に生成するコードの例を示す図である。
本発明の実施態様に従い、プログラム・コード（２４７１）をポインタ解析し、その結果として得られたポイント・ツー・グラフから、２行目で生成されたオブジェクトは４行目でしか使用されないことがわかる。コード最適化部（１５３３）又は開発者は、オブジェクトの生成を４行目の直前まで遅らせるようにコードを最適化する（２４７２）。最適化後のコード（２４７３）では、コード（２４７１）の２行目の命令が３行目と４行目の間に移動している。当該最適化によって、最適化後のコード（２４７３）では、４行目の命令を通らない実行パスでは、オブジェクトを生成する必要がなくなる。従って、メモリ使用量を減らすことが可能である。
【図１】
0005656602.tif 000002
【図２Ａ】
0005656602.tif 000003
【図２Ｂ】
0005656602.tif 000004
【図３】
0005656602.tif 000005
【図４】
0005656602.tif 000006
【図５Ａ】
0005656602.tif 000007
【図５Ｂ】
0005656602.tif 000008
【図６Ａ】
0005656602.tif 000009
【図６Ｂ】
0005656602.tif 000010
【図７Ａ】
0005656602.tif 000011
【図７Ｂ】
0005656602.tif 000012
【図８】
0005656602.tif 000013
【図９Ａ】
0005656602.tif 000014
【図９Ｂ】
0005656602.tif 000015
【図９Ｃ】
0005656602.tif 000016
【図１０Ａ】
0005656602.tif 000017
【図１０Ｂ】
0005656602.tif 000018
【図１１Ａ】
0005656602.tif 000019
【図１１Ｂ】
0005656602.tif 000020
【図１１Ｃ】
0005656602.tif 000021
【図１１Ｄ】
0005656602.tif 000022
【図１１Ｅ】
0005656602.tif 000023
【図１１Ｆ】
0005656602.tif 000024
【図１１Ｇ】
0005656602.tif 000025
【図１１Ｈ】
0005656602.tif 000026
【図１２Ａ】
0005656602.tif 000027
【図１２Ｂ】
0005656602.tif 000028
【図１２Ｃ】
0005656602.tif 000029
【図１２Ｄ】
0005656602.tif 000030
【図１２Ｅ】
0005656602.tif 000031
【図１２Ｆ】
0005656602.tif 000032
【図１３Ａ】
0005656602.tif 000033
【図１３Ｂ】
0005656602.tif 000034
【図１３Ｃ】
0005656602.tif 000035
【図１４Ａ】
0005656602.tif 000036
【図１４Ｂ】
0005656602.tif 000037
【図１４Ｃ】
0005656602.tif 000038
【図１４Ｄ】
0005656602.tif 000039
【図１４Ｅ】
0005656602.tif 000040
【図１４Ｆ】
0005656602.tif 000041
【図１４Ｇ】
0005656602.tif 000042
【図１４Ｈ】
0005656602.tif 000043
【図１４Ｉ】
0005656602.tif 000044
【図１５Ａ】
0005656602.tif 000045
【図１５Ｂ】
0005656602.tif 000046
【図１６】
0005656602.tif 000047
【図１７Ａ】
0005656602.tif 000048
【図１７Ｂ】
0005656602.tif 000049
【図１７Ｃ】
0005656602.tif 000050
【図１７Ｄ】
0005656602.tif 000051
【図１７Ｅ】
0005656602.tif 000052
【図１８Ａ】
0005656602.tif 000053
【図１８Ｂ】
0005656602.tif 000054
【図１９】
0005656602.tif 000055
【図２０】
0005656602.tif 000056
【図２１】
0005656602.tif 000057
【図２２】
0005656602.tif 000058
【図２３】
0005656602.tif 000059
【図２４Ａ】
0005656602.tif 000060
【図２４Ｂ】
0005656602.tif 000061