(57)【特許請求の範囲】
【請求項１】
コンピュータの処理により、ソフトウェア・プログラムのコードを、前記ソフトウェア・プログラムの複数の関数間の支配関係性につき解析する方法であって、
ソフトウェア・プログラムのソースコードを受け取るステップであって、前記ソースコードは、複数の関数を有する、ステップと；
各々が前記複数の関数のうちの別個の関数についてのものである複数のプロシージャ内支配節グラフを特定するステップと；
前記複数の関数のノード間を論理的に接続するエッジを有するプロシージャ間支配グラフを生成するために、前記複数のプロシージャ内支配節グラフを組み合わせるステップと；
前記プロシージャ間支配グラフを用いて、前記複数の関数のうちの異なる関数のノード間の複数のプロシージャ間支配関係を特定するステップと；
前記プロシージャ間支配グラフから余分のエッジを除去するステップをさらに含み、前記余分のエッジは、前記プロシージャ間支配グラフに既に存在するプロシージャ間エッジを集約する、ステップと；
前記複数のプロシージャ間支配関係にしたがって前記ソフトウェア・プログラムを解析するステップと
を含む、コンピュータ化された方法。
【請求項２】
前記プロシージャ内支配節グラフにおいて一つ以上のプロシージャ間支配候補を特定するステップと；
前記プロシージャ間支配候補の各々につきプロシージャ間支配節集合を計算するステップと；
をさらに含み、
組み合わせるステップは、前記一つ以上のプロシージャ間支配候補と前記プロシージャ間支配節集合からの一つ以上の支配節との間にプロシージャ間エッジを論理的に加えることにより、前記プロシージャ間支配グラフを計算するステップを含む、
請求項１に記載のコンピュータ化された方法。
【請求項３】
前記複数の関数のプロシージャ間制御フローグラフを特定するステップ
をさらに含み、
前記プロシージャ間支配候補は、前記プロシージャ間制御フローグラフにおいて一つより多い先行節を有する関数の入口であるノードを含み、前記ノードは、レジューム・ノードの支配辺境内にあるか、または前記ノードは、別のプロシージャ間支配候補の支配辺境内にある、
請求項２に記載のコンピュータ化された方法。
【請求項４】
組み合わせるステップは、各プロシージャ間支配候補についてのプロシージャ間支配節集合を並列に計算するステップを含む、請求項１に記載のコンピュータ化された方法。
【請求項５】
前記複数の関数の一つ以上に局所的変更を加えるステップと、前記変更された一つ以上の関数の影響を受けたプロシージャ間支配候補についてのみ、プロシージャ間支配節集合を再計算するステップと、影響を受けたノードだけを再接続するステップとをさらに含む、請求項１に記載のコンピュータ化された方法。
【請求項６】
前記プロシージャ間支配グラフは、前記プロシージャ間支配グラフを生成するために前記複数のプロシージャ内支配節グラフを前記組み合わせるステップの中間の期間中に正しい支配関係性を表現する、請求項１に記載のコンピュータ化された方法。
【請求項７】
キャッシュされたデータが後の支配節の演算に利用可能であるように、計算されたプロシージャ間支配節集合のデータを前記キャッシュするステップをさらに含む、請求項１に記載のコンピュータ化された方法。
【請求項８】
組み合わせるステップは、単一の呼び出しサイトを有する関数の呼び出しノードを前記関数の入口ノードに接続するエッジを加えることにより、前記プロシージャ間支配グラフを生成するステップを含む、請求項１に記載のコンピュータ化された方法。
【請求項９】
組み合わせるステップは、各関数出口ノードを前記関数が戻りうる全てのレジューム・ノードに接続するエッジを加えることにより、前記プロシージャ間支配グラフを生成するステップを含む、請求項１に記載のコンピュータ化された方法。
【請求項１０】
前記プロシージャ間支配節集合を計算するステップは、前記プロシージャ間支配候補の一つにつき前記プロシージャ間支配節集合をオンデマンドで計算するステップを含む、請求項２に記載のコンピュータ化された方法。
【請求項１１】
前記計算が循環パスを進まないようにブロッキング・ノードの集合を前記プロシージャ間制御フローグラフに加えるステップをさらに含む、請求項３に記載のコンピュータ化された方法。
【請求項１２】
前記複数の関数の一つ以上の関数呼び出しは、多相的である、請求項１に記載のコンピュータ化された方法。
【請求項１３】
前記プロシージャ内支配節グラフは、プロシージャ内支配節木である、請求項１に記載のコンピュータ化された方法。
【請求項１４】
請求項１〜１３の何れか１項に記載の方法の各ステップをコンピュータに実行させるプログラムをコンピュータ可読媒体に記録した、コンピュータ可読媒体。
【請求項１５】
複数の関連する関数からプロシージャ間支配グラフを計算するためのシステムであって、
第一プロセッサと；
前記プロセッサと電気通信する第一メモリであって、
前記複数の関連する関数のプロシージャ間制御フローグラフを提供するためのモジュール；
ソフトウェア・プログラムのソースコードを受け取るためのモジュールであって、前記ソースコードは、複数の関数を有する、モジュール；
各々が前記複数の関数のうちの別個の関数についてのものである複数のプロシージャ内支配節グラフを特定するためのモジュール；
前記複数の関数のノード間を論理的に接続するプロシージャ間支配グラフを生成するために、前記複数のプロシージャ内支配節グラフを組み合わせるためのモジュール；
前記プロシージャ間支配グラフを用いて、前記複数の関数のうちの異なる関数のノード間の複数のプロシージャ間支配関係を特定するためのモジュール；
前記プロシージャ間支配グラフから余分のエッジを除去するモジュールをさらに含み、前記余分のエッジは、前記プロシージャ間支配グラフに既に存在するプロシージャ間エッジを集約する、モジュール；および
前記複数のプロシージャ間支配関係にしたがって前記ソフトウェア・プログラムを解析するためのモジュール
を格納した前記メモリと
を含む、システム。
【請求項１６】
前記第一プロセッサと電気通信する複数のプロセッサをさらに含み、前記第一メモリは、各プロシージャ間支配候補についてのプロシージャ間支配節集合を前記複数のプロセッサの間で並列に計算するためのモジュールを含む、請求項１５に記載のシステム。
【請求項１７】
ユーザが前記複数の関数の一つ以上に対する変更を入力できるように適合された一つ以上の入力ユニットをさらに含み、前記第一メモリは、前記変更された一つ以上の関数の影響を受けたプロシージャ間支配候補についてのみプロシージャ間支配節集合を再計算するためのモジュールを含む、請求項１５に記載のシステム。
【請求項１８】
前記第一プロセッサおよび前記第一メモリのうちの少なくとも一方と電気通信するキャッシュ・メモリをさらに含み、前記第一メモリは、キャッシュされたデータが後の支配節の演算に利用可能であるように、計算されたプロシージャ間支配節集合のデータを前記キャッシュ・メモリに格納するためのモジュールをさらに含む、請求項１５に記載のシステム。
【請求項１９】
複数の関連する関数からプロシージャ間支配グラフを計算するためのコンピュータ・プログラムであって、コンピュータに、
ソフトウェア・プログラムのソースコードを受け取るステップであって、前記ソースコードは、複数の関数を有する、ステップと、
各々が前記複数の関数のうちの別個の関数についてのものである複数のプロシージャ内支配節グラフを特定するステップと、
前記複数の関数のノード間を論理的に接続するプロシージャ間支配グラフを生成するために、複数のプロシージャ内支配節グラフを組み合わせるステップと、
前記プロシージャ間支配グラフを用いて、前記複数の関数のうちの異なる関数のノード間の複数のプロシージャ間支配関係を特定するステップと、
前記プロシージャ間支配グラフから余分のエッジを除去するステップをさらに含み、前記余分のエッジは、前記プロシージャ間支配グラフに既に存在するプロシージャ間エッジを集約する、ステップと、
前記複数のプロシージャ間支配関係にしたがって前記ソフトウェア・プログラムを解析するステップ
を実行させる、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一部の実施形態においては、支配節を計算する方法もしくはシステムまたはその両方に、特に、プロシージャ間支配節を計算する方法もしくはシステムまたはその両方に関するが、これに限定されない。
【背景技術】
【０００２】
非特許文献１は、「制御フローグラフにおける支配節を見つける問題は、文献において長い歴史を有する。オリジナル・アルゴリズムは、漸近的計算量が大きかったが、理解が容易であった。その後の研究が時間限界を改善したが、一般に実装の単純性および容易性の両方を犠牲にした。本論文は、グローバル・データフロー問題としての単純な支配の定式化に戻る。」と開示していると思われる。
【０００３】
Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  ＩｏａｎｎｉｎａのＬｏｕｋａｓ  Ｇｅｏｒｇｉａｄｉｓは、“Ｆｉｎｄｉｎｇ  Ｄｏｍｉｎａｔｏｒｓ  ｉｎ  Ｉｎｔｅｒｐｒｏｃｅｄｕｒａｌ  Ｆｌｏｗｇｒａｐｈｓ”と題した発表において、プロシージャ間フローグラフにおける支配節を見つけるためのアルゴリズムを提示していると思われる。Ｇｅｏｒｇｉａｄｉｓは、データフロー方程式を解くことに基づいて、もしくはプロシージャ間深さ優先探索に基づいて、またはその両方に基づいてプロシージャ間支配節関係を計算すると思われる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｃｏｏｐｅｒ，Ｋｅｉｔｈ  Ｄ．，Ｔｉｍｏｔｈｙ  Ｊ．Ｈａｒｖｅｙ，およびＫｅｎ  Ｋｅｎｎｅｄｙ著“Ａ  ｓｉｍｐｌｅ，ｆａｓｔ  ｄｏｍｉｎａｎｃｅ  ａｌｇｏｒｉｔｈｍ”Ｓｏｆｔｗａｒｅ  Ｐｒａｃｔｉｃｅ  ＆  Ｅｘｐｅｒｉｅｎｃｅ４（２００１年）：１−１０
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、プロシージャ間支配節を計算するためのシステム、もしくはその方法、またはその両方を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一部の実施形態の一態様によれば、ソフトウェア・プログラムのコードを該ソフトウェア・プログラムの複数の関数間の支配関係性につき解析するコンピュータ化された方法が提供され、この方法には、ソフトウェア・プログラムのソースコードを受け取るステップであって、該ソースコードは、複数の関数を有する、ステップと；各々が該複数の関数のうちの別個の関数についてのものである複数のプロシージャ内支配節グラフを特定するステップと；該複数の関数のノード間を論理的に接続するエッジを有するプロシージャ間支配グラフを生成するために、該複数のプロシージャ内支配節グラフを組み合わせるステップと；該プロシージャ間支配グラフを用いて、該複数の関数のうちの異なる関数のノード間の複数のプロシージャ間支配関係を特定するステップと；該複数のプロシージャ間支配関係にしたがってソフトウェア・プログラムを解析するステップとを含む。
【０００７】
本発明の一部の実施形態によれば、このコンピュータ化された方法は、該プロシージャ内支配節グラフにおいて一つ以上のプロシージャ間支配候補を特定するステップと；該プロシージャ間支配候補の各々につき、プロシージャ間支配節集合を計算するステップとをさらに含み、組み合わせるステップは、該一つ以上のプロシージャ間支配候補と該プロシージャ間支配節集合からの一つ以上の支配節との間にプロシージャ間エッジを論理的に加えることにより、プロシージャ間支配グラフを計算するステップを含む。
【０００８】
任意的に、プロシージャ間支配節集合を計算するステップは、プロシージャ間支配候補の一つにつきプロシージャ間支配節集合をオンデマンドで計算するステップを含む。
【０００９】
任意的に、このコンピュータ化された方法は、該複数の関数のプロシージャ間制御フローグラフを特定するステップをさらに含み、プロシージャ間支配候補は、プロシージャ間制御フローグラフにおいて一つより多い先行節を有する関数の入口であるノードを含み、該ノードは、レジューム・ノードの支配辺境内にあるか、または該ノードは、別のプロシージャ間支配候補の支配辺境内にある。
【００１０】
任意的に、この方法は、計算するステップが循環パスを進まないように、プロシージャ間制御フローグラフにブロッキング・ノードの集合を加えるステップをさらに含む。本発明の一部の実施形態によれば、組み合わせるステップは、各プロシージャ間支配候補についてのプロシージャ間支配節集合を並列に計算するステップを含む。
【００１１】
本発明の一部の実施形態によれば、この方法は、複数の関数の一つ以上に局所的変更を加えるステップと、変更された一つ以上の関数の影響を受けたプロシージャ間支配候補についてのみ、プロシージャ間支配節集合を再計算するステップと、影響を受けたノードだけを再接続するステップとをさらに含む。
【００１２】
本発明の一部の実施形態によれば、プロシージャ間支配グラフは、プロシージャ間支配グラフを生成するために複数のプロシージャ内支配節グラフを組み合わせるステップの中間の期間中に正しい支配関係性を表現する。
【００１３】
本発明の一部の実施形態によれば、この方法は、キャッシュされたデータが後の支配節の演算に利用可能であるように、計算されたプロシージャ間支配節集合のデータをキャッシュするステップをさらに含む。
【００１４】
本発明の一部の実施形態によれば、組み合わせるステップは、単一の呼び出しサイトを有する関数の呼び出しノードを該関数の入口ノードに接続するエッジを加えることにより、プロシージャ間支配グラフを生成するステップを含む。
【００１５】
本発明の一部の実施形態によれば、組み合わせるステップは、各関数出口ノードを該関数が戻りうる全てのレジューム・ノードに接続するエッジを加えることにより、プロシージャ間支配グラフを生成するステップを含む。
【００１６】
本発明の一部の実施形態によれば、この方法は、プロシージャ間支配グラフから余分のエッジを除去するステップをさらに含み、余分のエッジは、プロシージャ間支配グラフに既に存在するプロシージャ間エッジを集約する。
【００１７】
本発明の一部の実施形態によれば、複数の関数の一つ以上の関数呼び出しは、多相的である。
【００１８】
本発明の一部の実施形態によれば、プロシージャ内支配節グラフは、プロシージャ内支配節木である。
【００１９】
本発明の一部の実施形態によれば、コンピュータ可読媒体は、該コンピュータ化された方法を行うために適合されたコンピュータ実行可能命令を含む。
【００２０】
本発明の一部の実施形態の一態様によれば、複数の関連する関数からプロシージャ間支配グラフを計算するためのシステムが提供され、このシステムは、第一プロセッサと、該プロセッサと電気通信する第一メモリであって、該複数の関連する関数のプロシージャ間制御フローグラフを提供するためのモジュールと、ソフトウェア・プログラムのソースコードを受け取るためのモジュールであって、該ソースコードは、複数の関数を有する、モジュールと、各々が該複数の関数のうちの別個の関数についてのものである複数のプロシージャ内支配節グラフを特定するためのモジュールと、該複数の関数のノード間を論理的に接続するプロシージャ間支配グラフを生成するために、複数のプロシージャ内支配節グラフを組み合わせるためのモジュールと、プロシージャ間支配グラフを用いて、該複数の関数のうちの異なる関数のノード間の複数のプロシージャ間支配関係を特定するためのモジュールと、該複数のプロシージャ間支配関係にしたがってソフトウェア・プログラムを解析するためのモジュールとが格納されたメモリとを含む。
【００２１】
本発明の一部の実施形態によれば、このシステムは、第一プロセッサと電気通信する複数のプロセッサをさらに含み、第一メモリは、各プロシージャ間支配候補についてのプロシージャ間支配節集合を複数のプロセッサの間で並列に計算するためのモジュールを含む。
【００２２】
本発明の一部の実施形態によれば、このシステムは、ユーザが複数の関数の一つ以上に対する変更を入力できるように適合された一つ以上の入力ユニットをさらに含み、第一メモリは、変更された一つ以上の関数の影響を受けたプロシージャ間支配候補についてのみプロシージャ間支配節集合を再計算するためのモジュールを含む。
【００２３】
本発明の一部の実施形態によれば、このシステムは、第一プロセッサおよび第一メモリのうちの少なくとも一方と電気通信するキャッシュ・メモリをさらに含み、第一メモリは、キャッシュされたデータが後の支配節の演算に利用可能であるように、計算されたプロシージャ間支配節集合のデータをキャッシュ・メモリに格納するためのモジュールをさらに含む。
【００２４】
本発明の一部の実施形態の一態様によれば、複数の関連する関数からプロシージャ間支配グラフを計算するためのコンピュータ・プログラム製品であって、一つ以上のコンピュータ可読記憶媒体と、該一つ以上の記憶媒体の少なくとも一つに格納されたプログラム命令であって、ソフトウェア・プログラムのソースコードを受け取るためのプログラム命令であって、該ソースコードは、複数の関数を有する、プログラム命令と、各々が該複数の関数のうちの別個の関数についてのものである複数のプロシージャ内支配節グラフを特定するためのプログラム命令と、該複数の関数のノード間を論理的に接続するプロシージャ間支配グラフを生成するために、複数のプロシージャ内支配節グラフを組み合わせるためのプログラム命令と、該プロシージャ間支配グラフを用いて、該複数の関数のうちの異なる関数のノード間の複数のプロシージャ間支配関係を特定するためのプログラム命令と、該複数のプロシージャ間支配関係にしたがってソフトウェア・プログラムを解析するためのプログラム命令とを含む、プログラム命令とを含む、コンピュータ・プログラム製品が提供される。
【００２５】
本発明の一部の実施形態によれば、このプログラム製品は、各プロシージャ間支配候補についてのプロシージャ間支配節集合を並列に計算するためのプログラム命令をさらに含む。
【００２６】
本発明の一部の実施形態によれば、このプログラム製品は、変更された複数の関数のうちの一つ以上の影響を受けたプロシージャ間支配候補についてのみ、プロシージャ間支配節集合を再計算するためのプログラム命令をさらに含む。
【００２７】
別段の定めがない限り、本明細書において用いられる全ての技術的もしくは科学的用語またはその両方は、本発明が関係する技術の当業者により一般に理解されているのと同じ意味を有する。本明細書に記載したものと類似または等価の方法および材料は、本発明の実施形態の実行または検証において使用されてよいが、以下には例示的方法もしくは材料またはその両方が記載される。矛盾がある場合には、定義を含め本明細書が優先する。加えて、材料、方法および例は例示にすぎず、必ずしも制限を目的としたものではない。
【００２８】
本明細書には、本発明の一部の実施形態が、添付の図面を参照して単なる例として説明される。特に図面の詳細に関しては、図示された明細は例であり、本発明の実施形態の具体的説明を目的とすることを強調する。この点で、説明を図面とともに解釈すれば、本発明の実施形態がどのように実践できるかが当業者に明らかになる。
【図面の簡単な説明】
【００２９】
【図１】本発明の例示的実施形態による、プロシージャ間支配節を計算するためのコンピュータ・システムのブロック・ダイヤグラムである。
【図２】本発明の例示的実施形態による、プロシージャ間支配グラフを計算するコンピュータ化された方法のフローチャートである。
【図３】本発明の実施形態を説明するために使用されるプログラム例である。
【図４】本発明の例示的実施形態による、図３のプログラム例についてのプロシージャ間制御フローグラフである。
【図５】本発明の例示的実施形態による、図３のプログラム例について計算されたプロシージャ間支配グラフである。
【図６】図３のプログラム例の支配節の計算のグラフ表現である。
【図７】図３のプログラム例の支配節の計算のグラフ表現である。
【図８】図３のプログラム例の支配節の計算のグラフ表現である。
【図９】図９Ａ〜９Ｂは、本発明の例示的実施形態の理解を助けるために有用な実験結果の表であり、図９Ｃは、本発明の例示的実施形態の理解を助けるために有用な実験結果のグラフである。
【発明を実施するための形態】
【００３０】
本発明の一部の実施形態の一態様は、複数の関数を含むソフトウェア・プログラムのインクリメンタル解析もしくはオンデマンド解析またはその両方のためにプロシージャ内支配節グラフを用いるための、コンピュータ化された方法もしくはシステムもしくはコンピュータ・プログラム製品またはその全てに関する。このプロセスは、並列処理もしくはスケールアウトまたはその両方を都合よく可能にする。このプロセスは、プロシージャ内解析からプロシージャ間解析へ移るために必要な変更を都合よく減少させる。
【００３１】
例示的実施形態においては、ソフトウェア・プログラム・コードの複数の関数につき計算された複数のプロシージャ内支配節グラフが組み合わせられて、プロシージャ間支配グラフが形成される。任意的に、このプロシージャ間支配グラフが解析されて、例えばソフトウェア・プログラムの関数間の支配関係性が特定される。任意的に、特定された支配関係性を用いて、ソフトウェア・プログラムが解析される。
【００３２】
例示的実施形態においては、コンピュータ・プログラム・コードが解析されて、プロシージャ間制御フローグラフが構成される。任意的に、異なるプログラム関数につき、複数のプロシージャ内支配節グラフが構成される。任意的にまたは加えて、初期プロシージャ内支配節グラフが、初期プロシージャ間支配グラフに組み入れられる。任意的にまたは加えて、プロシージャ内支配節グラフのプロシージャ間支配候補が特定される。任意的にまたは加えて、プロシージャ間支配候補の支配節集合が演算される。任意的にまたは加えて、プロシージャ間支配候補と直接支配節との間にエッジが加えられる。任意的にまたは加えて、エッジはインクリメンタルに加えられる。
【００３３】
任意的に、エッジは、プログラム全体の解析を遂行せずに加えられる。例えばプログラム全体の解析が要求される方法と比較したときに、プロシージャ間支配グラフが比較的迅速に計算されうるのが好都合である。例えば数十万の基本ブロックを有するプログラムなど、大きなプログラムが迅速に解析されうるのが好都合である。
【００３４】
支配関係（および例えばその導関数、例えば制御依存関係）は、例えばコンパイラ最適化、プログラム・スライシング等の応用例、静的単一代入（ＳＳＡ；ｓｔａｔｉｃ  ｓｉｎｇｌｅ  ａｓｓｉｇｎｍｅｎｔ）形式の計算、もしくは制御依存に関係するその他の計算またはその全てにおいて都合よく使用される。
【００３５】
例示的実施形態では、ノード（例えば各ノード）の支配節の計算は、他のいずれのノードの計算からも独立している。任意的に、支配節の計算は、オンデマンドで、例えば必要に応じて行われる。
【００３６】
任意的に、支配節の計算は、例えば人間のユーザのプログラミング変更などによる局所的なプログラムの変更により影響を受けたノードにつき行われる。任意的に、計算は、他の影響を受けていないノードを再解析することを必要とせずに、例えばプログラム全体を解析することを必要とせずに行われる。
【００３７】
任意的に、支配節の計算は、例えば互いに電気通信する複数のプロセッサを使用して、並列に行われる。並列に計算を行うことは、直列に計算を行うことよりも比較的高速であるのが好都合である。
【００３８】
任意的に、プロシージャ間支配グラフは、インクリメンタルに構築される。任意的に、既存のプロシージャ間支配グラフにエッジが加えられる。任意的に、エッジの追加は、いずれの順序で生じてもよい。プロシージャ間支配グラフは、エッジのインクリメンタルな追加のステージの間に正しい関係性を表現するのが好都合である。
【００３９】
任意的に、既存のプロシージャ内支配節グラフもしくは木またはその両方から、プロシージャ間支配候補が特定される。任意的に、プロシージャ間支配候補だけが、プロシージャ間支配エッジを有しうるノードである。任意的に、プロシージャ間エッジを導くことにより、プロシージャ内支配節木が拡張される。
【００４０】
本明細書において用いられるところの、「支配」という用語は、単一の関数において、関数の制御フローグラフ（ＣＦＧ；ｃｏｎｔｒｏｌ−ｆｌｏｗ  ｇｒａｐｈ）のノードｕが、関数の入口からｖへの全てのパスがまずｕを通過しなければならない場合に、別のノードｖを支配すると称されることを意味する。
【００４１】
任意的に、支配の定義は、プロシージャ間の場合に拡張される（例えば前段落の支配の定義はプロシージャ内の場合をさす）。プロシージャ間の定義は、例えば関数ｆが関数ｇを（直接または間接的に）呼び出す場合にはｇが戻る前にｆが戻ることはできないなど、不適切にネストされることのできない、関数呼び出しのセマンティクスを維持するパスだけを考慮する。したがって関数の呼び出しと戻りが、適切にネストするように有効なプロシージャ間パス上で対をなしうる。加えて、初期ノードからのいずれの有効なパスも、マッチされていない呼び出しを有しうる（例えばＳｙｓｔｅｍ．ｅｘｉｔ（）等のメソッドによるプログラム終了を可能とする）が、マッチされていない戻りは有し得ない。
【００４２】
本明細書において用いられるところの、「平衡パス」という表現は、マッチされていない呼び出しまたは戻りを有しない有効なパスを意味する。本明細書においてプロシージャ間支配は、有効なパスのみに関して定義される。例えば図３のプログラム例では、対応する図４の制御フローパスにおいて、メインでのｆ１の呼び出しを通過し（７行目）、１５行目のｆ１の呼び出し後にｆ２に戻る無効なパスが存在する。このパスが支配計算において考慮されれば、正しい関係性、例えば６行目の条件がｆ２の入口を支配するという関係性の発見を妨げうる。
【００４３】
プロシージャ内の場合には、制御フローグラフの各ノードｖは、最初のノードを除き、ｖの厳密支配節であってｖの他の全ての厳密支配節により支配される、固有の直接支配節を有する。本明細書において用いられるところの、「ｖの厳密支配節」という表現は、ｖの支配節ｕ≠ｖを意味する。
【００４４】
プロシージャ内支配関係の表現の一例は、各ノードｖの親がその直接支配節である木である。本明細書において用いられるところの「ｉｄｏｍ（ｖ）」という用語は、直接支配節を意味する。しかし、プロシージャ間の場合は、固有の直接支配節は存在しないかもしれない。例えば図３のプログラムでは、ｆ２の中のｉｆ（ｃ）条件（１４行目）は、ｆ２の出口のプロシージャ内直接支配節である。関数ｆ３の出口も、ｆ２の出口の直接支配節である。ｆ２を出るにはｆ３を通過することが必要であり、ｆ２がｆ３を直接呼び出さない場合はｆ１を呼び出し、この呼び出しを出るには、ｆ２内の呼び出しまたはｆ１内の呼び出しからｆ３を通過することが必要である。したがってこの例ではこれらのいずれも他方を支配せず、ｆ３を全く呼び出すことなくこの条件を通過することが可能であり、ｆ２を呼び出すことなくｆ３を呼び出すことが可能である。この例は、プロシージャ間の場合の支配関係の表現はグラフとするとよいことを示す。
【００４５】
本明細書で用いられるところの「ｉｄｏｍ（ｖ）」という用語は、ｖを厳密に支配するが、ｖの他のいずれの厳密支配節も厳密に支配しない全てのノードの集合を意味する。
【００４６】
本明細書で用いられるところの「プロシージャ間支配候補」という表現は、ノードｖは、ｖがプロシージャ間制御フローグラフにおいて一つより多い先行節を有する関数の入口であり、ｖがレジューム・ノードの支配辺境内にあるかまたはｖが別のプロシージャ間支配候補の支配辺境内にある場合に、プロシージャ間支配候補であることを意味する。
【００４７】
本明細書において用いられるところの「支配辺境」という表現は、制御フローグラフのノードｘの支配辺境は、ｘがｙの先行節を支配するがｙを厳密に支配しないような、全ての制御フローグラフのノードｙの集合であることを意味する。
【００４８】
本発明の少なくとも一つの実施形態を詳細に説明する前に、本発明の応用は、以下の説明に記載されまたは図面もしくは実施例に示された構成要素の構成および配置もしくは方法またはそのいずれの詳細にも必ずしも限定されないことを理解されたい。本発明は、他の実施形態または様々な方法で実施されもしくは実行されることが可能である。
【００４９】
当業者には当然のことながら、本発明の態様は、システム、方法またはコンピュータ・プログラム製品として具現化されうる。したがって、本発明の態様は、本明細書においては全て一般的に「回路」、「モジュール」または「システム」と呼称しうる、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）またはソフトウェアとハードウェア態様を組み合わせた実施形態の形をとりうる。さらに、本発明の態様は、具現化されたコンピュータ可読プログラム・コードを有する一つ以上のコンピュータ可読媒体（単数または複数）において具現化されたコンピュータ・プログラム製品の形をとりうる。
【００５０】
一つ以上のコンピュータ可読媒体（単数または複数）の任意の組み合わせを利用しうる。コンピュータ可読媒体は、コンピュータ可読信号媒体またはコンピュータ可読記憶媒体であってよい。コンピュータ可読記憶媒体は、例えば電子、磁気、光、電磁、赤外線または半導体システム、装置、もしくはデバイスまたは以上の任意の適切な組み合わせでありうるがこれに限定されない。コンピュータ可読記憶媒体のより具体的な例（非網羅的リスト）には、一つ以上のワイヤを有する電気接続、携帯可能コンピュータ・ディスケット、ハードディスク、ランダム・アクセス・メモリ（ＲＡＭ；ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、読み取り専用メモリ（ＲＯＭ；ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、消去可能プログラム可能読み取り専用メモリ（ＥＰＲＯＭ；ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）またはフラッシュ・メモリ、光ファイバ、携帯可能コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ；ｃｏｍｐａｃｔ  ｄｉｓｃ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、光記憶デバイス、磁気記憶デバイス、または以上の任意の適切な組み合わせが含まれる。本文書の文脈では、コンピュータ可読記憶媒体は、命令実行システム、装置、またはデバイスによる使用またはこれらと接続しての使用のためのプログラムを含みまたは記憶することができる任意の有形媒体であればよい。
【００５１】
コンピュータ可読信号媒体は、例えばベースバンドにおいてまたは搬送波の一部として、具現化されたコンピュータ可読プログラム・コードを含む伝搬データ信号を含みうる。このような伝搬信号は、電磁、光、またはその任意の適切な組み合わせを含むがこれに限定されない様々な形態のいずれかをとりうる。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではなく、命令実行システム、装置、またはデバイスによる使用またはこれらと接続しての使用のためのプログラムを通信、伝搬、または伝達することができる任意のコンピュータ可読媒体であればよい。
【００５２】
コンピュータ可読媒体上に具現化されるプログラム・コードは、無線、有線、光ファイバ・ケーブル、ＲＦなど、または以上の任意の適切な組み合わせを含むがこれに限定されない任意の適切な媒体を使用して伝送されうる。
【００５３】
本発明の態様の動作を行うためのコンピュータ・プログラム・コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋などのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語または同様のプログラミング言語等の従来の手続き型プログラミング言語を含む、一つ以上のプログラミング言語の任意の組み合わせで記述されればよい。プログラム・コードは、完全にユーザのコンピュータ上で、部分的にユーザのコンピュータ上で、スタンドアロン型ソフトウェア・パッケージとして、部分的にユーザのコンピュータ上でおよび部分的にリモート・コンピュータ上で、または完全にリモート・コンピュータもしくはサーバ上で、実行されうる。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ；ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）またはワイド・エリア・ネットワーク（ＷＡＮ；ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）を含む任意のタイプのネットワークを通じてユーザのコンピュータに接続され、または（例えばインターネット・サービス・プロバイダを用いてインターネットを通じて）外部コンピュータに接続されればよい。
【００５４】
本発明の実施形態による方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート図もしくはブロック・ダイヤグラムまたはその両方を参照して、本発明の態様が後述される。当然のことながら、フローチャート図もしくはブロック・ダイヤグラムまたはその両方の各ブロック、およびフローチャート図もしくはブロック・ダイヤグラムまたはその両方のブロックの組み合わせは、コンピュータ・プログラム命令により実装されうる。これらのコンピュータ・プログラム命令は、コンピュータまたはその他のプログラム可能データ処理装置のプロセッサを介して実行される命令が、フローチャートもしくはブロック・ダイヤグラムまたはその両方のブロック（単数または複数）に指定された機能／行為を実装する手段を創出するように、汎用コンピュータ、専用コンピュータ、またはその他のプログラム可能データ処理装置のプロセッサに提供されて機械が生み出されうる。
【００５５】
これらのコンピュータ・プログラム命令は、コンピュータ可読媒体に記憶された命令が、フローチャートもしくはブロック・ダイヤグラムまたはその両方のブロック（単数または複数）に指定された機能／行為を実装する命令を含む製造物品を生み出すように、コンピュータ、その他のプログラム可能データ処理装置、またはその他のデバイスに特定の様式で機能するように指示しうるコンピュータ可読媒体に記憶されてもよい。
【００５６】
コンピュータ・プログラム命令は、コンピュータ、その他のプログラム可能装置、またはその他のデバイス上で一連の動作ステップを行わせて、コンピュータまたはその他のプログラム可能装置上で実行する命令が、フローチャートもしくはブロック・ダイヤグラムまたはその両方のブロック（単数または複数）に指定された機能／行為を実装するためのプロセスを提供するようなコンピュータ実装されたプロセスを生み出すために、コンピュータ、その他のプログラム可能データ処理装置、またはその他のデバイスにロードされてもよい。
【００５７】
次に、本発明の例示的実施形態によるプロシージャ間支配グラフを計算するためのシステム１００のブロック・ダイヤグラムである図１を参照する。
【００５８】
任意的に、システム１００は、例えばプロシージャ間グラフの少なくともいくつかの部分を並列に計算するために設けられた、互いに電気通信する一つ以上のコンピュータもしくはプロセッサまたはその両方を含む。任意的に、システム１００は、プログラム命令を実行するための第一プロセッサ１０２を含む。任意的に、システム１００は、例えば第二プロセッサ１０４もしくは第三プロセッサ１０６またはその両方など、一つ以上の追加のプロセッサを含む。
【００５９】
任意的に、システム１００は、外部デバイスとの電気通信を提供するための一つ以上のネットワーク・インタフェース１０８を含む。任意的に、ネットワーク・インタフェース１０８は、例えばインターネット接続である第一ネットワーク接続１１２などを通じて、一つ以上のリモート・コンピュータ１１０に対する接続を提供する。代わりにまたは加えて、ネットワーク・インタフェース１０８は、例えば有線もしくは無線イーサネット接続またはその両方である第二ネットワーク接続１１６などを通じて、一つ以上のローカル・コンピュータ１１４に対する接続を提供する。任意的に、プロセッサ１０２、１０４もしくは１０６またはその全ては、リモート・コンピュータ１１０もしくはローカル・コンピュータ１１４またはその両方と電気通信し、例えば並列計算もしくは他の記憶データの共有またはその両方を行うことが可能である。
【００６０】
例示的実施形態において、システム１００は、例えば読み取り専用メモリ、ランダム・アクセス・メモリなど、プログラム命令を格納するための第一メモリ１１８を含む。任意的に、システム１００は、例えば任意的にキャッシュ・メモリ１２０など、一つ以上の追加の記憶要素を含む。任意的に、キャッシュ・メモリ１２０は、例えばプロセッサ１０２により計算されたデータなどの計算されたデータを格納するために適合される。任意的に、メモリ１１８もしくは１２０またはその両方は、例えばＣＤ−ＲＯＭ、ＵＳＢキー、またはその他のタイプの「プラグイン」メモリなど、取り外し可能としてもよい。
【００６１】
例示的実施形態において、システム１００は、ユーザがデータを入力できるようにする一つ以上の入力ユニット１２２を含む。例えば、キーボード、タッチスクリーンもしくはマウスまたはその全てである。
【００６２】
例示的実施形態において、システム１００は、ユーザがデータを見ることができるようにする一つ以上の出力ユニット１２４を含む。例えば、モニタもしくはプリンタまたはその両方である。
【００６３】
例示的実施形態において、システム１００は、例えば壁ソケット用プラグもしくはバッテリまたはその両方など、一つ以上の電源１２６を含む。
【００６４】
例示的実施形態において、システム・バス１２８は、プロセッサ１０２  １０４  １０６、ネットワーク・インタフェース１０８、メモリ１１８  １２０、入力ユニット１２２もしくは出力ユニット１２４またはその両方の一つ以上の間でのデータ交換を可能にするために電気通信もしくは接続またはその両方を提供する。
【００６５】
任意的に、システム・バス１２８、ネットワーク・インタフェース１０８、プロセッサ１０２、１０４もしくは１０６またはその全部、メモリ１１８もしくは１２０またはその両方、入力ユニット１２２もしくは出力ユニット１２４またはその両方は、例えばラップトップまたはデスクトップなどのコンピュータ１３０に内蔵される。
【００６６】
図２は、本発明の例示的実施形態による、プロシージャ間支配グラフを演算するコンピュータ化された方法のフローチャートである。例示的実施形態において、プロシージャ間支配グラフは、例えば複数の関数を含むプログラム・ソースコードの、プロシージャ間支配関係を表現する。
【００６７】
コンピュータ化された方法は、例えば図１に関して記載したコンピュータ・システムにより行われうる。
【００６８】
例示的実施形態において、プロシージャ間支配グラフは、プログラムのプロシージャについてのプロシージャ内支配節木もしくはグラフまたはその両方を含み、例えばプロシージャ間支配グラフは、プロシージャ内支配節グラフの拡張である。任意的に、プロシージャについてのプロシージャ内支配節グラフは、サブグラフとして表現される。
【００６９】
例示的実施形態において、例えば呼び出された関数が戻らないときなど、レジューム・ノードが呼び出しノードから到達不能である場合には、呼び出しノードは次のレジューム・ノードへのエッジ接続を有しないこともある。
【００７０】
例示的実施形態において、プロシージャ間支配グラフはインクリメンタルに構築される。任意的に、プロシージャ間支配グラフは、例えば計算中に正しい支配関係性を表現する。
【００７１】
本方法は、大きなプログラムに並列もしくはオンデマンドで（例えば変更されたノードにつき）またはその両方で行われうるのが好都合である。本方法は、例えばプログラム全体の解析が要求される方法など、他の方法よりも比較的高速でありうるのが好都合である。ノードの小さな集合についてのみ情報が要求される場合には、完全な支配関係は必ずしも計算されないのが好都合である。影響を受けたノードだけが再解析されればよいのが好都合である。
【００７２】
本方法は、例えば以下のプログラム解析において都合よく用いられうる。
＊コンパイラ最適化：一つの関数もしくはノードまたはその両方が他の関数もしくはノードまたはその両方をどのように支配するかを理解するために、プロシージャ間支配グラフが用いられうる。冗長性が特定もしくは除去されまたはその両方が行われうる。例えば、Ｓ．Ｓ．Ｍｕｃｈｎｉｃｋ著“Ａｄｖａｎｃｅｄ  Ｃｏｍｐｉｌｅｒ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ”Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ，１９９７年に記載される通りである。
＊プログラム・テスト：プロシージャ間支配グラフにより表現される支配関係性を用いて、繰り返しを減少させるか、もしくはより有効なカバレッジを提供するか、またはその両方であるテストケースが設計されうる。例えば、Ｈ．Ａｇｒａｗａｌ著“Ｅｆｆｉｃｉｅｎｔ  ｃｏｖｅｒａｇｅ  ｔｅｓｔｉｎｇ  ｕｓｉｎｇ  ｇｌｏｂａｌ  ｄｏｍｉｎａｔｏｒ  ｇｒａｐｈｓ”Ｐｒｏｃ．Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｐｒｏｇｒａｍ  Ａｎａｌｙｓｉｓ  ｆｏｒ  Ｓｏｆｔｗａｒｅ  Ｔｏｏｌｓ  ａｎｄ  Ｅｎｇｉｎｅｅｒｉｎｇ，ＰＡＳＴＥ’９９，ｐ．１１−２０，１９９９年を参照して記載される通りである。
＊プログラム最適化：プロシージャ間支配グラフを用いて、デッド・コードもしくは到達不能コードまたはその両方が特定もしくは除去されまたはその両方が行われうる。例えばＳ．ＣａｌｍａｎおよびＪ．Ｚｈｕ著“Ｉｎｃｒｅａｓｉｎｇ  ｔｈｅ  ｓｃｏｐｅ  ａｎｄ  ｒｅｓｏｌｕｔｉｏｎ  ｏｆ  ｉｎｔｅｒｐｒｏｃｅｄｕｒａｌ  ｓｔａｔｉｃ  ｓｉｎｇｌｅ  ａｓｓｉｇｎｍｅｎｔ”Ｐｒｏｃ．１６ｔｈ  Ｉｎｔ’ｌ  Ｓｙｍｐ．Ｓｔａｔｉｃ  Ａｎａｌｙｓｉｓ，ＳＡＳ’０９，ｐ．１５４−１７０，２００９年を参照して記載される通りである。
＊プログラム・スライシング：プロシージャ間支配グラフを用いて、プログラムの自己完結部分がより大きなプログラムから独立して特定され解析されうる。例えば、Ｓ．Ｈｏｒｗｉｔｚ，Ｔ．ＲｅｐｓおよびＤ．Ｂｉｎｋｌｅｙ著“Ｉｎｔｅｒｐｒｏｃｅｄｕｒａｌ  ｓｌｉｃｉｎｇ  ｕｓｉｎｇ  ｄｅｐｅｎｄｅｎｃｅ  ｇｒａｐｈｓ”ＡＣＭ  Ｔｒａｎｓ．Ｐｒｏｇｒａｍ．Ｌａｎｇ．Ｓｙｓｔ．，１２（１）：２６−６０，１９９０年、もしくはＭ．ＳｈａｒｉｒおよびＡ．Ｐｎｕｅｌｉ著“Ｔｗｏ  ａｐｐｒｏａｃｈｅｓ  ｔｏ  ｉｎｔｅｒｐｒｏｃｅｄｕｒａｌ  ｄａｔａ  ｆｌｏｗ  ａｎａｌｙｓｉｓ”Ｓ．Ｓ．ＭｕｃｈｎｉｃｋおよびＮ．Ｄ．Ｊｏｎｅｓ編，Ｐｒｏｇｒａｍ  Ｆｌｏｗ  Ａｎａｌｙｓｉｓ：Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，ｐ．１８９−２３３．Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，１９８１年またはその両方を参照して記載される通りである。
【００７３】
任意的に、２０２で、一つ以上の初期化が行われる。
【００７４】
任意的に、ソフトウェア・プログラムのソースコードが受け取られ、このソースコードは複数の関数を有する。例えばソフトウェア・プログラムがプログラマにより手作業でコーディングされ、ソースコードがインターネットからダウンロードされ、もしくはソースコードがコンピュータ上のメモリに格納され、またはその全てが行われる。
【００７５】
例示的実施形態において、複数のプロシージャ内支配節グラフが特定される。代わりにまたは加えて、複数のプロシージャ内支配節木が提供される。任意的に、プロシージャ内支配節グラフの一つは、複数の関数のうちの一つの関数の表現である。例えば各関数、例えばプログラムを構成する複数の関数につき、グラフが提供される。
【００７６】
任意的に、プロシージャ内支配節木もしくはグラフまたはその両方は、例えば適切なアルゴリズムにより、例えば参照により全体として本明細書に組み込まれるＬｅｎｇａｕｅｒおよびＴａｒｊａｎ（Ｔ．ＬｅｎｇａｕｅｒおよびＲ．Ｅ．Ｔａｒｊａｎ著“Ａ  ｆａｓｔ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｆｉｎｄｉｎｇ  ｄｏｍｉｎａｔｏｒｓ  ｉｎ  ａ  ｆｌｏｗｇｒａｐｈ”ＡＣＭ  Ｔｒａｎｓ．Ｐｒｏｇｒａｍ．Ｌａｎｇ．Ｓｙｓｔ．，１（１）：１２１−１４１，１９７９年７月）に記載されるアルゴリズムにより、演算される。
【００７７】
例示的実施形態では、例えば、参照により全体として本明細書に組み込まれるＳｈａｒｉｒおよびＰｎｕｅｌｉ（Ｍ．ＳｈａｒｉｒおよびＡ．Ｐｎｕｅｌｉ著“Ｔｗｏ  ａｐｐｒｏａｃｈｅｓ  ｔｏ  ｉｎｔｅｒｐｒｏｃｅｄｕｒａｌ  ｄａｔａ  ｆｌｏｗ  ａｎａｌｙｓｉｓ”Ｓ．Ｓ．ＭｕｃｈｎｉｃｋおよびＮ．Ｄ．Ｊｏｎｅｓ編，Ｐｒｏｇｒａｍ  Ｆｌｏｗ  Ａｎａｌｙｓｉｓ：Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，ｐ．１８９−２３３．Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，１９８１年）もしくはＤｅ  Ｓｕｔｔｅｒら（Ｂ．Ｄｅ  Ｓｕｔｔｅｒ，Ｌ．Ｖａｎ  Ｐｕｔ，およびＫ．Ｄｅ  Ｂｏｓｓｃｈｅｒｅ著“Ａ  ｐｒａｃｔｉｃａｌ  ｉｎｔｅｒｐｒｏｃｅｄｕｒａｌ  ｄｏｍｉｎａｎｃｅ  ａｌｇｏｒｉｔｈｍ”ＡＣＭ  Ｔｒａｎｓ．Ｐｒｏｇｒａｍ．Ｌａｎｇ．Ｓｙｓｔ．，２９（４），２００７年８月）またはその両方のコール・ストリング・アプローチにおいて記載されるように、プロシージャ間制御フローグラフが提供される。
【００７８】
図１を参照すると、プロシージャ内支配節グラフもしくはプロシージャ間制御フローグラフまたはその両方は、例えばメモリ１１８に格納されることにより、ユーザによって入力ユニット１２２を通じて入力されることにより、プロセッサ１０２により（例えばプログラムのソースコードから）計算されることにより、もしくはリモート・コンピュータ１１０からインターネットからダウンロードされることにより、または以上の全てにより提供される。
【００７９】
例示的実施形態において、プロシージャ間支配グラフは、例えば本明細書に記載されるようにプロシージャ内支配節木からインクリメンタルに構築される。
【００８０】
例示的実施形態において、プロシージャ間制御フローグラフは、各プロシージャの標準的な制御フローグラフ、例えばプロシージャ内制御フローグラフを含む。任意的に、各プロシージャは、固有の入口ノードもしくは固有の出口ノードまたはその両方を有する。任意的に、各呼び出しサイトは、二つのノード、すなわち呼び出しノードおよびレジューム・ノードにより表現される。任意的に、呼び出しノードは、呼び出しエッジにより呼び出されたプロシージャの入口に接続され、もしくは、レジューム・ノードは、呼び出されたプロシージャの出口からの入力戻りエッジを有し、またはその両方である。任意的に、各呼び出しサイトの呼び出しエッジは、プロシージャ内エッジにより同じサイトのレジューム・ノードに接続される。
【００８１】
任意的に、入口ノードは、複数の入力呼び出しエッジを有する。任意的に、出口ノードは、複数の出力戻りエッジを有する。
【００８２】
任意的に、プログラム全体に対する入口点である固有のメイン・プロシージャが存在する。
【００８３】
任意的に、各呼び出しノードは、単一の既知の関数に関連する。あるいは、各呼び出しノードは、多相的メソッドもしくは関数ポインタまたはその両方に関連する。
【００８４】
任意的に、レジューム・ノードが呼び出しノードから到達不能な呼び出しからレジュームへのエッジが、例えば参照により全体として本明細書に組み込まれるＤｅ  Ｓｕｔｔｅｒら（Ｂ．Ｄｅ  Ｓｕｔｔｅｒ，Ｌ．Ｖａｎ  Ｐｕｔ，およびＫ．Ｄｅ  Ｂｏｓｓｃｈｅｒｅ著“Ａ  ｐｒａｃｔｉｃａｌ  ｉｎｔｅｒｐｒｏｃｅｄｕｒａｌ  ｄｏｍｉｎａｎｃｅ  ａｌｇｏｒｉｔｈｍ”ＡＣＭ  Ｔｒａｎｓ．Ｐｒｏｇｒａｍ．Ｌａｎｇ．Ｓｙｓｔ．，２９（４），２００７年８月）に記載されるようなコンテキスト・センシティブな深さ優先探索（ＤＦＳ；ｄｅｐｔｈ  ｆｉｒｓｔ  ｓｅａｒｃｈ）を用いて除去される。
【００８５】
例示的実施形態において、初期プロシージャ間支配グラフは、到達不能な呼び出しからレジュームへのエッジを有しないプロシージャ内支配節木を含む。任意的に、例えば前処理ステップで、到達不能ノードが特定される。
【００８６】
２０４で、プロシージャ内支配節グラフに、一つ以上のプロシージャ間支配エッジが加えられる。例示的実施形態において、プロシージャ間エッジは、複数のプロシージャ内支配節グラフを結合する。例示的実施形態では、エッジの追加によりプロシージャ間支配グラフの初期形態が形成される。
【００８７】
例示的実施形態では、複数のプロシージャ内支配節グラフが組み合わせられて、初期プロシージャ間支配グラフが生成される。任意的に、プロシージャ間支配グラフは、複数の関数のノード間を論理的に接続し、例えばグラフのエッジが論理接続を提供する。
【００８８】
任意的に、（例えばプロシージャ間制御フローグラフの）局所的解析だけを必要とするエッジが加えられる。
【００８９】
任意的に、単一の呼び出しサイトを有する関数につき、プロシージャ間支配エッジが加えられる。例えばある関数が単一の呼び出しサイトに関連する場合、そのサイトが関数の入口を支配する。代わりにまたは加えて、全ての戻りにつきプロシージャ間支配エッジが加えられる。例えば各関数出口ノードが、戻りうる全てのレジューム・ノードを支配する。
【００９０】
任意的に、プロシージャ間制御フローグラフからプロシージャ間支配グラフにエッジをコピーすることにより、エッジが加えられる。
【００９１】
任意的に、ブロッキング・ノードの集合が、プロシージャ間支配グラフに関連付けられる。代わりにまたは加えて、ブロッキング・ノードの集合は、プロシージャ間制御フローグラフに関連付けられる。任意的に、ブロッキング・ノードは、プロシージャ間制御フローグラフにおいて循環パスをたどることを防ぐ。
【００９２】
２０６で、プロシージャ間支配候補が特定される。
【００９３】
例示的実施形態において、全ての支配節がトレースされてプロシージャ間支配候補が特定され、このプロシージャ間支配候補につき新たなプロシージャ間支配節が発見されうる。任意的に、以前に発見された直接支配節がたどられる。任意的に、たどる間にプロシージャ間支配候補に到達すると制御フローグラフにおけるプロシージャ間支配候補の先行節がたどられる。任意的に、たどることにより未発見の支配節が見つけられる。
【００９４】
任意的に、支配辺境が計算される。支配辺境が計算されると、全てのプロシージャ間支配候補の集合が、線形時間アルゴリズムで都合よく計算されうる。
【００９５】
任意的に、ブロッキング・ノードの集合が各探索に関連付けられる。ブロッキング・ノードは、循環パスをたどることを都合よく防ぎうる。
【００９６】
２０８で、各プロシージャ間支配候補の支配節集合が、例えば後述のアルゴリズム２を用いて計算される。
【００９７】
任意的に、支配節集合の計算は、全てのプロシージャ間支配候補にわたる反復により演算される。
【００９８】
任意的に、一つ以上のエッジが導かれる。任意的に、導かれたエッジは大域解析を必要とする。
【００９９】
任意的に、一つの支配節集合の計算は、他の支配節集合の計算とは独立して行われる。
【０１００】
任意的に、２１０で、プロシージャ間支配候補の支配節集合の一つ以上の計算が並列に行われる。代わりにまたは加えて、支配節集合の計算は任意の順序で行われる。
【０１０１】
例えばコンピュータ内のローカル・プロセッサ（例えば図１のプロセッサ１０２、１０４もしくは１０６またはその全て）への分散により、他のローカル・コンピュータ（例えば図１のローカル・コンピュータ１１４）への分散により、もしくはリモート・コンピュータ（例えば図１のリモート・コンピュータ１１０）への分散により、またはその全てにより並列に計算が行われうる。
【０１０２】
利用可能な並列スレッドが多いほど、全体の演算がより高速で行われうるのが好都合である。
【０１０３】
任意的に、２１２で、ノードの支配節がオンデマンドで計算される。任意的に、プロシージャ間支配候補についての支配節が、任意のノードにつきオンデマンドで演算される。任意的に、例えば再帰的関数呼び出しにより、再帰的に演算が行われる。
【０１０４】
任意的に、２１４で、プロシージャ間支配グラフの計算からの少なくとも一部のデータがキャッシュされる。例えば、図１のキャッシュ・メモリ１２０に計算結果が格納される。任意的に、保存された計算を用いて、繰り返し計算が減少または防止される。
【０１０５】
任意的に、プロシージャ間支配候補についての支配節の計算の結果または一部の結果が、キャッシュ・メモリに保存される。任意的に、保存された計算された支配節を用いて、後の計算で、例えば同じプロシージャ間支配候補について支配節を再計算する計算での繰り返しが減少または防止される。代わりにまたは加えて、プロシージャ間支配候補につき計算されたプロシージャ間支配グラフのエッジの一部の結果の結果が保存される。
【０１０６】
任意的に、一つの計算の結果（例えば２０８の支配節集合）がキャッシュに保存され、例えば同じ完全計算または部分計算が繰り返されたであろう場合に即座に使用されうる。任意的に、キャッシュされた計算は別の演算で使用され、例えばプロシージャ間支配候補の支配節の演算が互いに独立して行われる際に、結果が再計算されるのではなく共有されうる。任意的に、保存されたデータを用いることにより、異なるプロシージャ間支配候補についての計算が絡み合わされる。
【０１０７】
任意的に、例えばアルゴリズム２に関して後述するように、ブロッカーがキャッシュされる。
【０１０８】
一つの計算の結果を別の計算で使用するために保存することにより、他のもしくは将来のまたはその両方の支配計算が都合よく防止または減少される。同じ計算の結果は既に利用可能であり、再計算される必要がないのが好都合である。
【０１０９】
２１６で、プロシージャ間支配グラフに一つ以上のエッジが加えられる。任意的に、導かれた（例えば方法２０８で導かれた）エッジが加えられる。任意的に、エッジは、プロシージャ間支配グラフにインクリメンタルに加えられる。プロシージャ間支配グラフは、エッジのインクリメンタルな追加の各ステージで正しい支配表現を表現するのが好都合である。
【０１１０】
任意的に、導かれたエッジは、プロシージャ間支配候補に加えられる。任意的に、プロシージャ間支配候補の直接支配節集合が拡張される。任意的に、導かれたエッジを加える計算は、グラフのノード毎に行われる。
【０１１１】
任意的に、２１８で、解析されているプログラムの一つ以上の関数に一つ以上の局所的変更が加えられる。例えばプログラマがプログラムのバグを修正することもしくはプログラマがプログラムに追加機能を加えることまたはその両方により、例えばソースコード・ラインが変更、削除もしくは追加されまたはその全てが行われる。例えばキーボード（例えば図１の入力ユニット１２２）を使用して変更をタイプするなど、例えばユーザがプログラム・ソースコードのラインを手作業で変更することにより、変更が加えられる。例えば別のプログラムにより自動的に、変更が加えられてもよい。
【０１１２】
任意的に、局所的変更が加えられた後、影響を受けた関数のプロシージャ間支配候補のプロシージャ間支配節集合が、例えばボックス２０８を再度参照することにより、再計算される。任意的に、影響を受けた支配候補だけが再解析され、プログラム全体の解析もしくは影響を受けていない関数の解析またはその両方が必要ない。
【０１１３】
任意的に、２２０で、一つ以上の追加の計算が行われる。例えば、プロシージャ間支配グラフの最終処理が行われる。あるいは、プロシージャ間支配グラフは完全である。
【０１１４】
任意的に、ｕ  ２  ｉｄｏｍ（ｖ）である全てのエッジ（ｕ；ｖ）からなるグラフは、有向非巡回グラフ（ＤＡＧ；ｄｉｒｅｃｔｅｄ  ａｃｙｃｌｉｃ  ｇｒａｐｈ）である。任意的に、グラフはプロシージャ内支配節木と同じ性質を有し、例えばグラフのパスは完全な支配関係を表現する。任意的に、本明細書に記載される方法は、このグラフに対する過大近似でありうるプロシージャ間支配グラフを計算する。任意的に、グラフは同じ性質を維持するが、既にグラフ中にあるいくつかのプロシージャ間エッジを集約するいくつかの追加のエッジを有してもよい。任意的に、これらの余分のエッジは、例えば追加の処理により除去される。
【０１１５】
本明細書において用いられるところの「集約パス」という表現は、以下の意味である、すなわち有効なパスｐ毎に、ｐの集約パスは、一つの呼び出しから対応する戻りへの全ての平衡パスを単一の呼び出しからレジュームへのエッジで置換することによりｐから導かれるパスｐ’であると定義される。集約パス上では、呼び出しノードから関数の入口への、もしくは関数の出口からレジューム・ノードへの、またはその両方のいずれのエッジもパス上でマッチされていない。
【０１１６】
任意的に、例えば後述のように多相性を扱うために加えられたノードなど、加えられたノードが除去される。
【０１１７】
ボックス２０２、２０４、２０６、２０８、２１０、２１２、２１４、２１６、２１８もしくは２２０またはその全てに記載された一つ以上の計算が、例えばメモリ（例えば図１のメモリ１１８）に格納された、例えば一つ以上のソフトウェア・モジュールにより行われる。
【０１１８】
任意的に、２２２で、ソフトウェア・プログラムが解析される。任意的に、解析は複数のプロシージャ間支配関係にしたがって行われる。解析は、例えばソフトウェアにより自動的に、スクリーン上の支配関係のグラフ表現を見ている人間により手作業で、もしくはソフトウェアと人間の組み合わせにより、またはその全てにより行われる。
【０１１９】
任意的に、プロシージャ間支配グラフを用いて、複数の関数のうちの異なる関数のノード間の複数のプロシージャ間支配関係が特定される。
【０１２０】
任意的に、複数のプロシージャ間支配関係は、さらなるプログラム解析において、例えばコンパイラ最適化、プログラム・テスト、プログラム最適化、プログラム・スライシングもしくは例えば本明細書に記載されるようなその他の応用例において、またはその全てにおいて使用される。
【０１２１】
任意的に、本方法もしくはシステムまたはその両方は、多相性をサポートするために拡張される。代わりにまたは加えて、各呼び出しサイトは、呼び出される関数を一意的に特定する。
【０１２２】
任意的に、プロシージャ間制御フローグラフにおける多相的な各呼び出しは、例えば利用可能な最良近似により決定される全ての可能な実装クラスを用いた、対象の動的型（もしくは最悪の場合には静的型の全ての実装サブクラスまたはその両方）に対する一連のテストとして表現される。
【０１２３】
任意的に、表現のために加えられた新たなノードは、元のプロシージャ間制御フローグラフには見られない。任意的に、加えられたノードは、後続の後処理ステップ、例えば図２のボックス２２０により除去される。
【０１２４】
任意的に、本方法は、関数ポインタを提供する言語で関数ポインタを扱うために用いられる。
【０１２５】
多相性に対応するための本方法もしくはシステムまたはその両方の拡張は、例えば特定のメソッド呼び出しのために実行されるコードがインボケーションの対象の型に依存するオブジェクト指向言語のために都合よく用いられる。他の情報を一切有しなければ、メソッドを実装する対象の静的型の全てのサブクラスが潜在的に呼び出されうる。しかし、静的解析（ポインタ解析を含む）を用いることで、呼び出されうる実装を狭めることが多くの場合に可能である。
【０１２６】
以下に示すアルゴリズム１は、本発明の例示的な実施形態による、図２に関して記載される方法の数学的表現の例示である。任意的に、アルゴリズム１は、プロシージャ内支配節木からプロシージャ間支配グラフをインクリメンタルに構築する。アルゴリズム１は例示的であり、必ずしも限定的ではなく、例えば本方法の他の実装も可能である。
【０１２７】
アルゴリズム１への入力は、ノードの集合Ｖに関するプロシージャ間制御フローグラフである。アルゴリズム１により産出される出力は、対応するプロシージャ間支配グラフである。
【０１２８】
アルゴリズム１：
１．［プロシージャ内エッジを加える］プロシージャ内支配節グラフもしくは木またはその両方を計算する；（例えばコンテキスト・センシティブなＤＦＳを用いて、レジューム・ノードが呼び出しノードから到達不能な全ての呼び出しからレジュームへのエッジを除去する）；グラフもしくは木またはその両方を組み合わせて、初期プロシージャ間支配グラフを形成する。
２．［呼び出しエッジを加える］単一の呼び出しサイトを有する関数毎に、プロシージャ間支配グラフに、呼び出しノードを関数の入口ノードに接続するエッジを加える。
３．［戻りエッジを加える］プロシージャ間支配グラフに、各関数出口ノードをそれが戻りうる全てのレジューム・ノードに接続するエッジを加える。
４．［導かれたエッジを加える］プロシージャ間支配候補（ＩＤＣ）ｖ∈ＩＤＣ毎に：
（ａ）Ｓ＝支配節（ｖ，φ）＼｛ｖ｝とする。
（ｂ）ｉｄｏｍ（ｖ）を、ｕがプロシージャ間支配グラフ後続節ｕ’∈Ｓを有しないような全ての要素ｕ∈Ｓの集合となるように設定する。
（ｃ）各ｕ∈ｉｄｏｍ（ｖ）につき、プロシージャ間支配グラフにエッジ（ｕ，ｖ）を加える。
【０１２９】
以下に示すアルゴリズム２は、本発明の例示的な実施形態による、アルゴリズム１のステップ４ａで用いられる支配節関数を行うための例示的アルゴリズムである。任意的に、アルゴリズム２は、ブロッカー集合Ｂを前提としてノードｖについて支配節集合を計算する。任意的に、アルゴリズム２は、ブロッカー・ノードの集合Ｂに関連して、部分的支配関係性を計算する。アルゴリズム２は例示的であり、必ずしも限定的ではなく、例えば方法の他の実装も可能である。
【０１３０】
アルゴリズム２は、任意的にプロシージャ間支配候補である入力ｖについて、プロシージャ間支配節を計算する。アルゴリズム２は、プロシージャ間支配グラフにおいて既存の支配エッジをたどる。アルゴリズム２がプロシージャ間支配候補の一つに到達すると、アルゴリズムは、プロシージャ間制御フローグラフにおけるその先行節の支配節の交点を計算する。この計算は、この探索中に既に訪問されたノードのブロッキング集合Ｂを任意的に用いることにより、プロシージャ間制御フローグラフにおける巡回閉路を無視する。
【０１３１】
アルゴリズム２：
支配節（ｖ，Ｂ）：
１：ｉｆ  ｖ∈ＩＤＣ  ｔｈｅｎ
２：  Ｒ←Ｖ
３：  Ｂ’＝Ｂ∪｛ｖ｝とする
４：  ｆｏｒ  プロシージャ間支配グラフにＢ’の要素からｒへのパスが存在しないようなｖのプロシージャ間制御フローグラフ先行節ｒ毎に  ｄｏ
５：    Ｓ＝支配節（ｒ，Ｂ’）とする
６：    Ｒ←Ｒ∩Ｓ
７：  ｅｎｄ  ｆｏｒ
８：  ｒｅｔｕｒｎ  Ｒ∪｛ｖ｝
９：ｅｌｓｅ
１０：  Ｐ←｛ｖ｝
１１：  ｆｏｒ  ｖのプロシージャ間支配グラフ先行節ｄ毎に  ｄｏ
１２：    Ｐ←Ｐ∪支配節（ｄ，Ｂ）
１３：  ｅｎｄ  ｆｏｒ
１４：  ｒｅｔｕｒｎ  Ｐ
１５：ｅｎｄ  ｉｆ
【０１３２】
任意的に、いずれの呼び出し支配節（ｖ；Ｂ）の結果も、例えば図１のキャッシュ・メモリ１２０に格納されるなど、キャッシュされる。代わりにまたは加えて、４行目でいくつかのパスをブロックするために実際に使用されたブロッカーの集合Ｂ’⊆Ｂがキャッシュされる。任意的に、（ｖ；Ｂ’）対についての結果がキャッシュされる。任意的に、これらの値は、ｐｄｏｍ（ｖ；Ｂ’）に等しい。任意的に、アルゴリズム２は、例えば１行目の再計算が減少されるように最適化される。
【０１３３】
本明細書で用いられるところの「ｐｄｏｍ（ｖ，Ｂ）」という用語は、Ｂのいずれの要素も含まない初期ノードからｖへのパスがいずれもｕを含むような全てのノードｕの部分的支配集合を意味する。
【０１３４】
任意的に、アルゴリズム２の１行目の後に以下の文が加えられる：
ｉｆ  キャッシュがＢ’⊆Ｂである呼び出し支配節（ｖ；Ｂ’）についての結果Ｒを含む  ｔｈｅｎ
ｒｅｔｕｒｎ  Ｒ
ｅｎｄ  ｉｆ
【０１３５】
代わりにまたは加えて、例えばアルゴリズム２がいずれかのブロッカーｂからノードｖへのプロシージャ間支配グラフのパスを発見した場合に、ブロッカーがキャッシュされる。任意的に、キャッシュされたデータは、ｖについてのブロッカーの後の計算で使用される。ブロッカーをキャッシュすることにより、後の計算が都合よく高速化される。
【０１３６】
図３は、本発明の例示的実施形態による、プロシージャ間支配グラフを計算するための本明細書に記載のシステムもしくは方法またはその両方を説明するために使用されるプログラムの例である。
【０１３７】
図４は、本発明の例示的実施形態による、図３のプログラム例のプロシージャ間制御フローグラフである。実線の矢印は、プロシージャ内データフローを表現する。破線の矢印は、呼び出しエッジもしくは戻りエッジまたはその両方を表現する。
【０１３８】
図５は、本発明の例示的実施形態による、図３のプログラム例の完全なプロシージャ間支配グラフである。プロシージャ間支配候補が、太枠で示される。プロシージャ間支配候補は、それぞれ複数の呼び出しサイトを有するｆ１およびｆ３の入口、ｆ２内の両レジューム・ノードの支配辺境内にあるｆ２の出口、およびｆ１内の三つのレジューム・ノードの支配辺境内にあるｆ１内のｆ４への呼び出しからなる。
【０１３９】
プロシージャ内支配節木の一部であるプロシージャ間支配グラフ・エッジは、図５において細い実線矢印を用いて示される。例えば（上述の）アルゴリズム１のステップ１において、もしくは図２のボックス２０４において、またはその両方において、これらのエッジが加えられる。
【０１４０】
呼び出しおよび戻りエッジは、破線として示される。これらのエッジは、例えばアルゴリズム１のステップ２もしくは３またはその両方において、もしくは図２のボックス２０４において、またはその全てにおいて、加えられる。
【０１４１】
加えられた導かれたエッジは、太い実線の矢印として示される。導かれたエッジは、例えばアルゴリズム１のステップ４において、もしくは図２のボックス２１６において、またはその両方において加えられる。任意的に、導かれたエッジは、プロシージャ間支配グラフに加えられる順序にしたがって番号付けされる。１番エッジは、プロシージャ間支配候補ノードｆ１−入口の処理中に加えられた。２番エッジは、プロシージャ間支配候補ノードｆ３−入口を処理する間に加えられた。３番エッジは、プロシージャ間支配候補ノードｆ２−出口を処理する間に加えられた。４とマークされた２つのエッジは、プロシージャ間支配候補ノードｆ４−呼び出しを処理する間に加えられた。
【０１４２】
図６〜８は、本発明の例示的な実施形態による、図３Ａのプログラム例のプロシージャ間支配グラフの計算における３つのステップを示す。アルゴリズム１およびアルゴリズム２を参照して、計算が論じられる。図６は、支配節（ｆ１−入口，φ）関数の計算のグラフ表現である。図７は、支配節（ｆ２−出口，φ）関数の計算のグラフ表現である。図８は、支配節（ｆ４−呼び出し，｛ｆ２−出口，ｆ１−レジューム３｝）関数の計算のグラフ表現である。
【０１４３】
支配節関数により訪問されるノードが、陰付きで示される。ブロッカーの背景には、斜線が付される。「×」マークは、プロシージャ間支配グラフにおいてブロッカーから到達可能であったために例えばアルゴリズム２の４行目でスキップされた、プロシージャ間制御フローグラフ先行節を指定する。
【０１４４】
次に、ノードｆ１−入口の解析中のプロシージャ間支配グラフの計算のグラフ表現である図６に注目する。このノードは、三つのプロシージャ間制御フローグラフ先行節、ｆ１−呼び出し１、ｆ１−呼び出し２、およびｆ１−呼び出し３を有する。最後の二つはプロシージャ間支配グラフにおいてｆ１−入口から到達可能であり、したがって結果はｆ１−呼び出し１とその単一のプロシージャ間支配グラフ祖先節すなわちメイン入口とを含み、これらが例えばアルゴリズム１のステップ４ａにおける集合Ｓの二つの要素である。ｆ１−呼び出し１はプロシージャ間支配グラフにおいてメイン入口から到達可能であるため、ｆ１−呼び出し１だけがｉｄｏｍ（ｆ１−入口）にあり、プロシージャ間支配グラフに１番エッジが加えられる。
【０１４５】
次に、ノードｆ２−出口の解析中のプロシージャ間支配グラフの計算のグラフ表現である図７に注目する。このノードは、二つのプロシージャ間制御フローグラフ先行節、ｆ３−レジューム２およびｆ１−レジューム３を有する。一例では、第一の再帰的呼び出しは、支配節（ｆ３−レジューム２；｛ｆ２−出口｝）である。この呼び出し中に訪問されるノードは、右半分が陰付きで示される。この呼び出しは、プロシージャ間支配グラフのエッジを、ｆ３−呼び出し２、ｉｆ（ｃ）、ｆ２−入口、ｆ２−呼び出し、ｉｆ（ｂ）、ｉｆ（ａ）、およびｆ１−入口へと逆にたどる。これはｉｄｏｍが既に計算されているプロシージャ間支配候補ノードであるが、アルゴリズム２が計算を繰り返す。この例では、アルゴリズムは最適化されている。すなわち、アルゴリズムは、そのような場合に支配節を再計算する代わりにプロシージャ間支配グラフのエッジをたどり続け、第一の再帰的呼び出しの結果にｆ１−呼び出し１およびメイン入口を加える。アルゴリズムはまた、プロシージャ間支配グラフのエッジをｆ３−レジューム２からｆ３−出口へ、それからｆ３−入口へ、そしてｆ３−入口を扱う間に加えられた２番エッジ（演算は示さない）を、既に訪問されているｉｆ（ａ）へたどる。
【０１４６】
第二の再帰的呼び出しは、支配節（ｆ１−レジューム３；｛ｆ２−出口｝）である。この呼び出し中に訪問されるノードは、図７において左半分が陰付きで示される。この呼び出しは、プロシージャ間支配グラフのエッジをｆ１−呼び出し３へたどり、ｉｆ（ｃ）への前の呼び出しと同じように、メイン入口に到達するまでたどり続ける。この時点で、ｆ１−入口につき前に計算されたプロシージャ間支配グラフ・エッジが使用される。
【０１４７】
アルゴリズムはまた、ｆ１−レジューム３から、プロシージャ間支配グラフのエッジをｆ１−出口へ、それからｆ４−レジューム、およびｆ４−呼び出しへとたどる。これには、再帰的呼び出し、支配節（ｆ４−呼び出し；｛ｆ２−出口；ｆ１−レジューム３｝）が必要である。図８は、この再帰的呼び出し中のプロシージャ間支配グラフの計算のグラフ表現である。ｆ４−呼び出しのプロシージャ間制御フローグラフ先行節は、ｆ１−レジューム２、ｆ２−レジューム、およびｆ３−レジューム１である。一番目のｆ１−レジューム２は、プロシージャ間支配グラフにおいてブロッカーｆ４−呼び出しから到達可能であり、二番目のｆ２−レジュームはｆ２−出口から到達可能である。したがってアルゴリズムは、プロシージャ間支配グラフのエッジをｆ３−レジューム１からｆ３−出口、ｆ３−入口、およびｉｆ（ａ）へとたどり、そこからは前と同様に続け、またｆ３−レジューム１からｆ３−呼び出し１およびｉｆ（ｂ）へもたどり、前と同様に続ける。この全てのデータが、第二の再帰的呼び出しの結果に加えられる。この再帰的呼び出しにより加えられる四つの新たなノードが、図７において左側により明るい陰を付けて示される。二つの呼び出しの交点の最小ノードは、ｉｆ（ｃ）およびｆ３−出口である。プロシージャ間支配グラフは、ｉｆ（ｃ）からｆ２−出口へのエッジを既に含むが、この呼び出しの結果として３番エッジがプロシージャ間支配グラフに加えられる。
【０１４８】
本発明者らは、例えば図２、アルゴリズム１もしくはアルゴリズム２またはその全てなどの本発明の例示的実施形態にしたがって構築されたアルゴリズムをテストした。図９Ａおよび９Ｂは、実験結果のテーブルであり、図９Ｃは実験結果のチャートである。
【０１４９】
テストされたアルゴリズムの実装は、アルゴリズム１もしくはアルゴリズム２またはその両方と異なる。アルゴリズム２の４行目で全てのブロックされたパスを探索する代わりに、再帰的呼び出しが続けられた。このような呼び出しがブロッカーに遭遇するたびに、失敗のマーカとして空集合を返す。このような失敗は、最終結果において無視される。別の修正は、ブロッカー対ではなくブロッカー集合を追跡する。
【０１５０】
いくつかのＪａｖａプロジェクトで、アルゴリズムがテストされた。実験から分かったことには以下が含まれる：
＊支配節関数に対して呼び出しが行われる順序および結果として生じるキャッシュの振る舞いが、全体的性能に大きく影響しうる。
＊順次的な深さ優先戦略は、ノードのヒューリスティックな順序付けを用いても、最悪の結果をもたらしうる。
＊イールド・ポイントを有する複数のスレッドを実行することにより、単一ＣＰＵ上でも性能が改善しうる。
＊追加のハードウェア・スレッドは、性能の大きな向上を提供しうる。
【０１５１】
図９Ａは、アルゴリズムがテストされたアプリケーションを集約したテーブルであり、いくつかは同じプロジェクトからのものである。全てが、オープンソースのプロジェクトである。ＲｅｍｏｔｅＳｅａｒｃｈａｂｌｅ、ＰｏｒｔｅｒＳｔｅｍｍｅｒ、およびＩｎｄｅｘＲｅａｄｅｒは、テキスト検索エンジン・ライブラリＬｕｃｅｎｅの一部であり、ＨＳＱＬＤＢおよびＤｅｒｂｙは、リレーショナル・データベース・エンジンであり、Ｃａｓａｎｄｒａは、ｎｏＳＱＬの分散ＤＢＭＳであり、ｄｕｍｐ、ｄｅｃｏｒａｔｅ、およびｏｐｔｉｍｉｚｅは、Ｊａｖａバイトコード・オプティマイザおよびクラス・リライタであるＢｌｏａｔの一部である。
【０１５２】
解析がｊａｒファイルのライブラリを含むため、コードの行の値は得られなかったが、いずれにしても支配節の計算との関連性がより高い統計は基本ブロックの数である。加えて、図９Ａは、各アプリケーションにおけるメソッドの合計数およびプロシージャ間支配候補ノードの数をリストする。基本ブロックには最大で一つのプロシージャ間支配候補ノードが存在しうるため、プロシージャ間支配候補ノードの数はプロシージャ間支配候補ノードを含む基本ブロックの数でもある。図９Ａから分かるように、この数は、基本ブロックの合計数の２〜８９％の間であり、最も大きな二つのアプリケーションでは３０％に近い。アルゴリズムの性能の重要な要因がプロシージャ間支配候補ノードの数でありうるため、このことは重要な意味を持ちうる。
【０１５３】
図９Ａおよび９Ｂは、様々な構成でのテスト・プロジェクトに対するアルゴリズムの実行時間を示す。「１スレッド」と名付けられた第一の構成は、ノードを順序付けするためにいくつかのヒューリスティクスを用いた単一スレッドでの実行時間を示す。三つの場合にアルゴリズムが１時間経過後に終わらず、それがこの欄にダッシュを用いてマークされている。他の欄は、プロシージャ間支配候補ノード毎に一つのスレッドを生成するアルゴリズムのバージョンについての結果を示しており、各スレッドが各支配節呼び出しの初めに生じ、４つのコアと８つのハードウェア・スレッドを有するＩｎｔｅｌ  ｉ７−２７２０ＱＭ２．２０ＧＨｚ  ＣＰＵ上で、１つ、２つ、４つ、または８つのハードウェア・スレッドを用いて実行したものである。図９Ａは、一回の実行の結果を示す。図９Ｂは、最も大きな三つのプロジェクトの各マルチ・スレッド構成での、四セットの実行の最小結果および最大結果を示す。図９Ｃは、（平均）マルチ・スレッド結果の高速化をグラフの形態で示す。示された時間は、プロシージャ間支配節アルゴリズムの計算についてだけのものであり、プロシージャ間制御フローグラフならびにプロシージャ内支配節および支配辺境を計算するのに必要な時間は除外している。プロシージャ間制御フローグラフは、ＷＡＬＡにより構築され、ＷＡＬＡのＺｅｒｏＯｎｅＣＦＡポインタ解析に基づく多相的呼び出しエッジを含んだ。多相的な呼び出しは、上述のように扱われる。
【０１５４】
図９Ｂで注目すべきは、実行時間の比較的大きな変動性である。これは、例えばキャッシュ最適化（例えば図２のボックス２１４に記載されるような）による様々なスレッド間の強い相互依存に起因しうる。グラフを深さ優先様式で探索するシングル・スレッドでの実行時には、この最適化が効力を生じる十分な機会がないかもしれず、例えば図９Ａの「１スレッド」および「１ＣＰＵ」の欄を比較することで分かるように、単一プロセッサ上で複数のスレッドを実行したときよりも性能が大幅に悪くなりうる。この影響は、大きなプログラムほど特に強いようである。しかし、これらの場合にマルチ・スレッドのバージョンがシングル・スレッドの性能に近づくほど変動性が大きいことは決してなかった。シングル・スレッドのバージョンは、最も大きな三つのプロジェクトに関していずれも一時間未満で終了しなかったが、単一ＣＰＵ上で実行するマルチ・スレッドのバージョンは、常に遅くとも数分以内に終わった。
【０１５５】
プロシージャ間支配候補ノードが処理される順序に対するこの依存は、高速化の結果にも影響しうる。高速化がプロセッサの数の差を上回るケースもあるが、これは、より多くのプロセッサによって、より多くのプロシージャ間支配候補ノードを並列に処理することが可能になり、それによりキャッシュが増え、最適化がより効果的になりうるという事実に起因しうる。
【０１５６】
上述の方法は、集積回路チップの製作において用いられる。
【０１５７】
図のフローチャートおよびブロック・ダイヤグラムは、本発明の様々な実施形態によるシステム、方法、およびコンピュータ・プログラム製品の可能な実施態様のアーキテクチャ、機能性および動作を例示する。この点に関して、フローチャートまたはブロック・ダイヤグラムの各ブロックは、指定される論理機能（単数または複数）を実装するための一つ以上の実行可能命令を含むモジュール、セグメントまたはコードの部分を表しうる。いくつかの代替的実装では、ブロックに記した機能は、図の順序以外で生じうることにも注意されたい。例えば、連続して示された二つのブロックは、実際には実質的に同時に実行されてもよいし、またはブロックは、時には関連する機能性に応じて逆順に実行されてもよい。ブロック・ダイヤグラムもしくはフローチャート図またはその両方の各ブロック、およびブロック・ダイヤグラムもしくはフローチャート図またはその両方のブロックの組み合わせが、指定される機能もしくは行為を行う専用ハードウェア・ベースのシステム、または専用ハードウェアとコンピュータ命令との組み合わせにより実装されうる点にも注意されたい。
【０１５８】
本発明の様々な実施形態の説明は、例示のために示されているが、網羅的であることも、または開示された実施形態に限定されることも意図されていない。多くの修正変更が、説明された実施形態の範囲および精神から逸脱することなく、通常の技術を有する当業者に明らかとなるであろう。本明細書において用いられる専門用語は、実施形態の原理、実際の応用例、または市場に見られる技術に対する技術的改善を最もよく解説するため、または通常の技術を有する他の当業者が本明細書に開示された実施形態を理解することを可能にするために選択されたものである。
【０１５９】
本出願から特許が満期になるまでの期間中、多くの関連するプロシージャ間支配節グラフ演算方法が開発されることが予想され、プロシージャ間支配節グラフ演算方法という用語の範囲は、先天的に全てのこのような新技術を含むことを意図する。
【０１６０】
本明細書において用いられるところの「約」という用語は、±１０％をさす。
【０１６１】
「備える」、「備えている」、「含む」、「含んでいる」、「有している」という用語およびそれらの活用形は、「含むが、それに限定されない」を意味する。この用語は、「からなる」および「から基本的になる」という用語を包含する。
【０１６２】
「から基本的になる」という表現は、組成物または方法が、追加の成分もしくはステップまたはその両方が請求された組成物または方法の基本的および新規な特徴を実質的に変更しない場合に限り、その追加の成分もしくはステップまたはその両方を含みうることを意味する。
【０１６３】
本明細書において用いられるところの単数形「ａ」、「ａｎ」、および「ｔｈｅ」は、文脈から別段の明示がない限り、複数の参照物を含む。例えば、「化合物」または「少なくとも一つの化合物」という用語は、複数の化合物を、それらの混合物を含めて含みうる。
【０１６４】
「例示的」という用語は、本明細書においては、「例、実例または例示として役立つこと」を意味するために使用される。「例示的」であるものとして記載されたいずれの実施形態も、必ずしも他の実施形態よりも好適または有利であるもの、もしくは他の実施形態の特徴を取り入れることを除外するもの、またはその両方と解釈されてはならない。
【０１６５】
「任意的に」という語は、本明細書においては、「いくつかの実施形態において提供され、他の実施形態においては提供されない」ことを意味するために使用される。本発明のいずれの特定の実施形態も、複数の「任意の」特徴を、このような特徴が矛盾しない限りにおいて含むことができる。
【０１６６】
本明細書の全体にわたって、本発明の様々な実施形態が範囲の形式で提示されることがある。範囲の形式での記載は、簡便および簡潔のためにすぎず、本発明の範囲に対する柔軟性のない限定として解釈されてはならないことを理解されたい。したがって、範囲の記載は、その範囲内の個々の数値だけでなく全ての可能な部分範囲を特に開示しているものと考えられなければならない。例えば１〜６の範囲の記載は、例えば１、２、３、４、５、および６など、その範囲内の個々の数だけでなく、１〜３、１〜４、１〜５、２〜４、２〜６、３〜６等の部分範囲を特に開示しているものと考えられなければならない。これは、範囲の幅に関係なく当てはまる。
【０１６７】
本明細書において数値の範囲が指示されたときは常に、指示された範囲内の任意の引用された数字（分数または整数）を含む意味である。第一の指示数と第二の指示数と「の間に範囲が及んでいる／及ぶ」、および第一の指示数「から」第二の指示数「までに範囲が及んでいる／及ぶ」という表現は、本明細書において互換可能に用いられ、第一および第二の指示数ならびにその間の全ての分数および整数を含む意味である。
【０１６８】
当然のことながら、明確のために別個の実施形態の文脈で記載されている本発明のある特徴は、単一の実施形態において組み合わせて提供されてもよい。反対に、簡潔のために単一の実施形態の文脈で記載されている本発明の様々な特徴は、個別に、または任意の適切な部分的組み合わせにおいて、または本発明の他の任意の記載された実施形態において適切であるように提供されてもよい。様々な実施形態の文脈で記載されたある特徴は、それらの要素なしでは実施形態が実施不能でない限り、それらの実施形態の必須の特徴と考えられてはならない。
【０１６９】
本発明の具体的実施形態とともに本発明が記載されているが、多くの代替、修正および変更形態が当業者に明らかとなることが明白である。したがって本発明は、添付の請求項の精神および広い範囲に含まれる全てのこのような代替、修正および変更形態を包含することが意図される。
【０１７０】
本明細書に記載の全ての刊行物、特許および特許出願は、個々の刊行物、特許または特許出願が参照により全体として本明細書に組み込まれるものと特に個別に指定されたのと同じ程度に、参照により全体として本明細書に組み込まれる。加えて、本明細書におけるいかなる参考文献の引用または特定も、このような参考文献が本発明に対する先行技術として利用可能であることの承認として解釈されてはならない。セクションの見出しが使用される限りにおいて、それらは必ずしも限定と解釈されてはならない。
【図１】
0006433497.tif 000002
【図２】
0006433497.tif 000003
【図３】
0006433497.tif 000004
【図４】
0006433497.tif 000005
【図５】
0006433497.tif 000006
【図６】
0006433497.tif 000007
【図７】
0006433497.tif 000008
【図８】
0006433497.tif 000009
【図９】
0006433497.tif 000010