(57)【要約】【課題】  プローブ挿入を最適化することによってプログラムを計装するための方法およびシステムを提供すること。【解決手段】  計装されたコード内へのプローブ挿入の数は、最適なプローブ挿入点を提供することによって減少される。コードの制御フローは、アークとブロックの関係と共に分析されて、ポスト支配木が構築される。最適なプローブ挿入点を提供する最適化マップが、ポスト支配木から生成される。プローブが挿入され、コードおよびプローブを表すバイナリを実行することによってデータが収集されると、そのデータは、最適化マップ、およびアークとブロックの関係上にオーバレイされて、コードカバレッジデータが提供される。【選択図】  図４
2005302028.tif 000002
【特許請求の範囲】
【請求項１】
プログラムの機能に関連するポスト支配木を調査するステップと、
前記ポスト支配木に従って前記プログラムへのプローブ挿入を決定するステップと、
前記プローブを前記プログラム内に挿入するステップと
を備えたことを特徴とするプログラムを計装するためのコンピュータによって実施される方法。
【請求項２】
前記プログラムに関連する制御フローグラフから前記ポスト支配木を生成するステップをさらに備えたことを特徴とする請求項１に記載のコンピュータによって実施される方法。
【請求項３】
前記プローブからデータが受信されるとき、前記データがアーク−ブロックマップ上にオーバレイされて、前記プログラムについてのアークおよびブロックのカバレッジデータを発見するように、前記制御フローグラフから前記アーク−ブロックマップを構築するステップをさらに備えたことを特徴とする請求項２に記載のコンピュータによって実施される方法。
【請求項４】
前記ポスト支配木に従って前記プローブに対応するエントリを含む最適化マップを構築するステップをさらに備えたことを特徴とする請求項１に記載のコンピュータによって実施される方法。
【請求項５】
前記プログラム内のバックエッジの位置に対応する第２のプローブ挿入が行われるように、前記バックエッジについて前記プログラムを調査し、前記バックエッジに対応するエントリを前記最適化マップに追加するステップをさらに備えたことを特徴とする請求項４に記載のコンピュータによって実施される方法。
【請求項６】
前記プログラム内の呼出しの位置に対応する第２のプローブ挿入が行われるように、前記呼出しについて前記プログラムを調査し、前記呼出しに対応するエントリを前記最適化マップに追加するステップをさらに備えたことを特徴とする請求項４に記載のコンピュータによって実施される方法。
【請求項７】
前記プログラム内の外部エントリポイントの位置に対応する第２のプローブ挿入が行われるように、前記外部エントリポイントについて前記プログラムを調査し、前記外部エントリポイントに対応するエントリを前記最適化マップに追加するステップをさらに備えたことを特徴とする請求項４に記載のコンピュータによって実施される方法。
【請求項８】
前記プローブから受信されたデータを前記最適化マップ上にオーバレイして、前記プローブについて前記プログラムのコードカバレッジデータを提供するアーク関係を決定するステップをさらに備えたことを特徴とする請求項４に記載のコンピュータによって実施される方法。
【請求項９】
前記プローブは、前記ポスト支配木内に存在する葉ノードに対応することを特徴とする請求項１に記載のコンピュータによって実施される方法。
【請求項１０】
プログラムを計装するためのコンピュータ実行可能命令を有するコンピュータ読取り可能媒体であって、
プログラムの機能に関連するポスト支配木を調査するステップと、
前記ポスト支配木に対応する、前記ポスト支配木内の葉ノードに対応するエントリを含む最適化マップを構築するステップと、
前記最適化マップの各エントリに対応するプローブを前記プログラム内に挿入するステップと
を備えたことを特徴とするコンピュータ読取り可能媒体。
【請求項１１】
前記プログラムに関連する制御フローグラフから前記ポスト支配木を生成するステップをさらに備えたことを特徴とする請求項１０に記載のコンピュータ読取り可能媒体。
【請求項１２】
データが前記プローブから受信されるとき、前記データがアーク−ブロックマップにオーバレイされて、前記プログラムのアークおよびブロックのカバレッジデータを発見するように、前記制御フローグラフから前記アーク−ブロックマップを構築するステップをさらに備えたことを特徴とする請求項１１に記載のコンピュータ読取り可能媒体。
【請求項１３】
前記プログラム内に挿入された前記プローブのうちのいくつかが、前記プログラム内のバックエッジの位置に対応して挿入されるように、前記バックエッジについて前記プログラムを調査し、前記バックエッジに対応するエントリを前記最適化マップに挿入するステップをさらに備えたことを特徴とする請求項１０に記載のコンピュータ読取り可能媒体。
【請求項１４】
前記プログラム内に挿入された前記プローブのうちのいくつかが前記プログラム内の呼出しの位置に対応して挿入されるように、前記呼出しについて前記プログラムを調査し、前記呼出しに対応するエントリを前記最適化マップに挿入するステップをさらに備えたことを特徴とする請求項１０に記載のコンピュータ読取り可能媒体。
【請求項１５】
前記プログラム内に挿入された前記プローブのうちのいくつかが前記プログラム内の外部エントリポイントの位置に対応して挿入されるように、前記外部エントリポイントについて前記プログラムを調査し、前記外部エントリポイントに対応するエントリを前記最適化マップに挿入するステップをさらに備えたことを特徴とする請求項１０に記載のコンピュータ読取り可能媒体。
【請求項１６】
前記プローブから受信されたデータを前記最適化マップにオーバレイして、前記プログラムのコードカバレッジデータを提供する、前記プローブのアーク関係を決定するステップをさらに備えたことを特徴とする請求項１０に記載のコンピュータ読取り可能媒体。
【請求項１７】
前記プログラムに対応する制御フローグラフを計算し、
前記制御フローグラフに対応するポスト支配木を構築し、
前記ポスト支配木内の葉ノードに対応するエントリを含む、前記ポスト支配木に対応する最適化マップを構築し、
前記最適化マップの各エントリに対応するプローブを前記プログラム内に挿入し、および
前記プログラムの実行後に前記プローブから受信されたデータを前記最適化マップ上にオーバレイして、前記プログラムのコードカバレッジデータを提供する
ように構成されたアプリケーションを有するコンピューティング装置を備えたことを特徴とするプログラムを計装するためのシステム。
【請求項１８】
前記アプリケーションは、前記プログラム内に挿入された前記プローブのうちのいくつかが前記プログラム内のバックエッジの位置に対応して挿入されるように、前記バックエッジについて前記プログラムを調査し、前記バックエッジに対応するエントリを前記最適化マップに追加するようにさらに構成されたことを特徴とする請求項１７に記載のシステム。
【請求項１９】
前記アプリケーションは、前記プログラム内に挿入された前記プローブのうちのいくつかが前記プログラム内の呼出しの位置に対応して挿入されるように、前記呼出しについて前記プログラムを調査し、前記呼出しに対応するエントリを前記最適化マップに追加するようにさらに構成されたことを特徴とする請求項１７に記載のシステム。
【請求項２０】
前記アプリケーションは、前記プログラム内に挿入された前記プローブのうちのいくつかが前記プログラム内の外部エントリポイントの位置に対応して挿入されるように、前記外部エントリポイントについて前記プログラムを調査し、前記外部エントリポイントに対応するエントリを前記最適化マップに追加するようにさらに構成されたことを特徴とする請求項１７に記載のシステム。
【請求項２１】
前記アプリケーションは、アークマップおよびブロックマップが前記制御フローグラフについてのアークとブロックの関係を相互参照するように、前記制御フローグラフにそれぞれが対応する前記アークマップおよびブロックマップを構築するようにさらに構成されたことを特徴とする請求項１７に記載のシステム。
【請求項２２】
前記アプリケーションは、最適化マップ上にオーバレイされた前記データを前記アークマップおよびブロックマップにオーバレイして、前記プログラムの前記コードカバレッジデータを洗練するようにさらに構成されたことを特徴とする請求項２１に記載のシステム。
【請求項２３】
コードのアークおよびブロックへのプローブマッピングの重複が回避されるように、前記プローブを前記ポスト支配木内に含むことを特徴とする請求項２１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プローブ挿入を最適化することによってプログラムを計装するための方法およびシステムに関する。
【背景技術】
【０００２】
カバレッジ分析は、一定した高品質の検証結果を保証するために多くのソフトウェア開発元によって採用されている方法である。コードカバレッジ（ｃｏｄｅ  ｃｏｖｅｒａｇｅ）分析ツールをインストールして、特定のプログラムのカバレッジ分析を提供することができる。カバレッジ分析ツールは、カバレッジ情報を取得するための範囲および方法が様々であり得る。
【０００３】
本質的にカバレッジ分析は、１組の目標のメトリックに対する設計のテストスィート（ｔｅｓｔ  ｓｕｉｔｅ）の測定に基づく。設計者は、その設計の段階、カバレッジ測定を行うコスト、および特定のメトリックの有用性を体験する設計グループの経験に基づいてメトリックを選択する。コードカバレッジのメトリックは、自動化されたツールを用いて比較的低いコストで実施され、また簡単明瞭な結果をもたらし得るので、多くの場合最初に使用されるものである。
【０００４】
コードカバレッジ計装の１つの方法は、プログラムのコードの論理フロー内の各ブロックまたはアーク（ａｒｃ）に「プローブ」を置くことを含む。「プローブ」は、コードに関するデータを記録する１組の命令である。たとえば、プローブは、分析のためにプログラムの特定の部分の使用データについて報告を出すことができる。プログラム内にプローブを置くことによって、プログラムを計装するための強力な方法がもたらされる。
【０００５】
追加データの収集のためにユーザがコードを増やす必要があるいかなる場合にも、パフォーマンスは関心事である。計装／プローブによって課されるオーバヘッドが、コードカバレッジ分析がもたらす利益より大きいことがある。提供されるカバレッジデータのレベルのため、プローブベースの分析のパフォーマンスコストは重大であり得る。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
パフォーマンスコストを改善しながらも、プローブベース分析によってもたらされる比較可能なレベルのデータを提供する、プログラムを計装するための方法が求められている。
【課題を解決するための手段】
【０００７】
本発明は、プローブ挿入を最適化することによってプログラムを計装するための方法およびシステムを提供する。プローブ挿入を最適化すると、コードカバレッジデータ収集のオーバヘッドを減らすことによって、計装されたコードのパフォーマンスが高まる。コードの制御フローは、アークとブロックの関係とともに分析されて、「ポスト支配木（ｐｏｓｔ−ｄｏｍｉｎａｔｏｒ  ｔｒｅｅ）」が構築される。ポスト支配点（ｐｏｓｔ−ｄｏｍｉｎａｔｏｒ）は、コードの第１のセクションとコードの第２のセクションの間の関係を指す。コードの第１セクションが、コードの第２セクションを実行することができる前に実行されなければならない場合、コードの第２セクションは、コードの第１セクションの「ポスト支配点」と称される。したがって、同じ例では、コードの第１セクションは、コードの第２セクションの「支配点」と称される。
【０００８】
計算されたポスト支配木においては、コードのプローブ挿入点は、最適化マップを生成することによって計算することができる。最適化マップは、コード内に挿入されるプローブの数を最小限に抑えながらも、完全なコードカバレッジ情報を取得するためのプローブ挿入点を提供する。プローブが挿入されると、コードのバイナリが実行されて、プローブ出力データを取得することができる。次いで、プローブ出力データは、最適化マップ上にオーバレイされて、プローブ出力データをプローブ位置に関連付けることができる。プローブ出力データを最適化マップにオーバレイすることにより、各プローブの関連するアークおよびブロックを用いてプローブ出力データを解決して、コードカバレッジデータを作成することができる。
【０００９】
次に本発明について、添付の図面を参照して以下により完全に述べる。この図面は、その一部を形成し、また図示することによって、本発明を実施するための具体的で、例示的な実施形態を示している。しかし、本発明は、多数の異なる形において実施することができ、また本明細書で述べる諸実施形態に限定されるものと解釈すべきではない。こうした実施形態は、本開示が徹底的で完全なものであり、また当業者に本発明の範囲を十分に伝えるものとなるように提供されている。本発明は、いくつかある中でも特に、方法または装置として実施され得る。したがって、本発明は、完全にハードウェアの実施形態を取ることも、完全にソフトウェアの実施形態を取ることも、またソフトウェアとハードウェアとの両側面を組み合わせた実施形態の形を取ることもある。したがって、以下の詳細な説明は、限定的な意味で取るべきでない。
【発明を実施するための最良の形態】
【００１０】
図１に、本発明を実施するためのシステム１００内に含まれ得る例示的なコンピューティング装置を示す。コンピューティング装置１００は、本発明に適用され得る一般的な操作環境を示している。非常に基本的な構成では、コンピューティング装置１００は一般に、少なくとも１つの処理装置１０２およびシステムメモリ１０４を含む。処理装置１０２は、既存の物理プロセッサ、設計のプロセッサ、一緒に動作する複数のプロセッサ、仮想プロセッサ、およびバイナリ実行可能命令を解釈することができる他の任意の装置またはソフトウェアを含む。厳密な構成、およびコンピューティング装置の種類によって、システムメモリ１０４は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭ、フラッシュメモリなど）、またその２つの何らかの組合せである場合もある。システムメモリ１０４は一般に、オペレーティングシステム１０５、１つまたは複数のプログラムモジュール１０６を含み、またプログラムデータ１０７を含み得る。図１に、この基本的な構成を、破線１０８内のこれらの構成要素によって示す。
【００１１】
コンピューティング装置１００は、追加の特徴または機能を含むこともできる。たとえば、コンピューティング装置１００は、たとえば磁気ディスク、光ディスク、テープなどの追加のデータ記憶装置（取外し可能および／または固定）をも含み得る。図１に、こうした追加の記憶装置を、取外し可能記憶装置１０９および固定の記憶装置１１０として示す。コンピュータ記憶媒体は、コンピュータ読取り可能命令、データ構造体、プログラムモジュールまたは他のデータなどの情報を記憶するために、任意の方法または技術で実装された揮発性および不揮発性、取外し可能および固定の媒体を含み得る。システムメモリ１０４、取外し可能記憶装置１０９および固定の記憶装置１１０はすべて、コンピュータ記憶媒体の例である。コンピュータ記憶媒体には、それだけに限らないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置または他の磁気記憶装置、あるいは所望の情報を格納するために使用することができ、またコンピューティング装置１００からアクセスすることができる他の任意の媒体が含まれる。こうした任意のコンピュータ記憶媒体が、コンピューティング装置１００の一部であり得る。コンピューティング装置１００は、キーボード、マウス、ペン、スタイラス、音声入力装置、タッチ入力装置などの入力装置１１２をも含み得る。表示装置、スピーカ、プリンタなどの他の出力装置１１４も含まれ得る。こうしたすべての装置は、当技術分野で知られており、ここでは詳細に論じる必要はない。
【００１２】
コンピューティング装置１００は、装置が、たとえばネットワークを介して他のコンピューティング装置１１８と通信できるようにする通信接続１１６を含むこともできる。通信接続１１６は、通信媒体の一例である。通信媒体は一般に、コンピュータ読取り可能命令、データ構造体、プログラムモジュール、または他のデータを搬送波や他の移送機構などの変調されたデータ信号の形で実施し、また任意の情報送達媒体を含む。用語「変調されたデータ信号」は、その特性の１つまたは複数が、信号に情報を符号化するようなやり方で設定されまたは変更された信号を意味する。限定するためではなく、例を挙げると、通信媒体は、有線ネットワークや直接有線接続などの有線媒体、音響、ＲＦ、赤外線および他の無線媒体などの無線媒体を含む。本明細書では、用語コンピュータ読取り可能媒体は、記憶媒体と通信媒体の両方を含む。
【００１３】
（プローブ最適化）
本発明は、一般に、プログラムを計装するときプローブ挿入を最適化するためのシステムおよび方法を対象とする。プローブは、コードカバレッジに関するデータなど、コードからデータを取り出すためにプログラム内に挿入される１組の命令を指す。プログラムを計装するための従来の方法は、制御フローグラフの各アークについてプローブを挿入することを必要としていた。しかし、プローブは、長さが指定されたビット数であり、プログラムに多数のプローブを挿入すると、プログラムの計装に対するオーバヘッドが増加する。プローブが挿入された状態でプログラムバイナリが実行される場合、プローブによって、バイナリの実行サイクルにかなりの時間量が追加され得る。本発明は、プローブ挿入点を最適化し、それによって、プログラム内に挿入されるプローブの数を減らし、プログラムの計装に対するオーバヘッドを減らす。実行するのに数週間かかる一部のプログラムテストスィートによっては、本発明によってもたらされるオーバヘッドの削減によって、かなりの時間の節約がもたらされ得る。
【００１４】
図２に、本発明による例示的な制御フローグラフおよびアーク−ブロックマップ（ａｒｃ  ｔｏ  ｂｌｏｃｋ  ｍａｐ）を示す。制御フローグラフ２１０は、プログラム実行フローの図を提供している。機能のブロックまたはノード（１、２、３、４、５、６など）は、アーク（Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆなど）によって示される順序で実行される。制御フローグラフ２１０は、プログラムのために計算された制御フローの一例であり、他の制御フローグラフは、遥かに複雑である場合がある。
【００１５】
制御フローグラフ２１０は、絵を用いてではなく、アークおよびブロックを表すデータエントリに従って表すこともできる。一例が、アーク−ブロックマップ２２０によって示されている。アーク−ブロックマップ２２０は、制御フローグラフ２１０内のそれぞれのアークについてのブロックまたはノードの関係を提供する。プログラムの処理の特定のパスに関するコードブロックは、アーク−ブロックマップ２２０を調べることによって解決することができる。
【００１６】
図示する例では、プログラムの実行は、プログラムの最後、ノード６に到達するために、ノード１から２つの異なるパスを取り得る。１つのパスでは、コードブロックの実行は、アークＢおよびＤを通って流れ、他のパスでは、アークＣおよびＥを通って流れる。制御フローグラフ２１０によって表されたプログラムのコードカバレッジデータを取得するために、プログラムの実行に使用可能な様々なパスが考慮される。ノード１から６までのパス内に含まれないプログラムの他の側面も同様に考慮される。たとえば、特定のプログラムは、「バックエッジ（ｂａｃｋ  ｅｄｇｅ）」と称されるものを含み得る。バックエッジは、Ｈで表され、ノードが別のノードと共依存の関係を有する場合に対応する。ノード４は、バックエッジのために、ノード２との共依存関係を有する。バックエッジは、ノード２を実行するにはノード４を実行しなければならないことを示している。しかし、通常の実行フローでは、ノード４を実行するにはノード２を実行しなければならない。したがって、ノード２とノード４は、バックエッジＨによって生成された共依存関係を有し得る。コードカバレッジのための一実施形態では、バックエッジは、プログラムの通常の範囲外の工程を表しているのでプローブされる。
【００１７】
プログラムフロー考察の別の側面は、関数呼出しまたはプログラムの他の部分に対する呼出しの存在である。呼出しは、アークＧで表される。アークＧに対応する呼出しは、ノード５０への呼出しを行い、関数２１５に、実行し、および場合によっては値を返すように指示する。コードカバレッジに関する一実施形態では、プログラムの他の部分または関数への呼出しは、通常、コードカバレッジデータがその呼出しを含むようにプローブされる。
【００１８】
プログラムの制御フロー考察の別の側面は、外部データのエントリポイントである。たとえば外部エントリポイント７５は、アークＪを越えてノード１にデータを提供する。外部エントリポイントは、コードブロック（ノード１など）が実行のために使用する、ユーザからの入力などの外部ソースからのデータの入口点を表す。コードカバレッジの一実施形態では、コードカバレッジデータがこうした外部のデータエントリを含むように、外部エントリポイントがプローブされる。
【００１９】
アーク−ブロックマップ２２０は、追加のパスから制御フローグラフ２１０まで、バックエッジ、呼出しおよび外部エントリポイントについてのエントリを含むように修正することができる。したがって、一実施形態では、プローブのエントリの最適化は、使用されるプローブの数を最小限に抑えながらも完全なコードカバレッジデータを収集することを含む。以下の図３〜５に、プログラム測定において使用されるプローブの数を最小限に抑えるための図式化された方法および工程を示す。
【００２０】
図３に、本発明による、図２の制御フローグラフおよびアーク−ブロックマップに対応する例示的なポスト支配木および最適化マップを示す。ポスト支配木３１０は、図２に示す制御フローグラフ２１０内のブロックおよびその関連アークについてのポスト支配関係を示している。ポスト支配点は、第１のコードブロックと第２のコードブロックの間の関係を指す。第１コードブロックが、第２コードブロックが実行され得る前に実行されなければならない場合、第２コードブロックは、第１コードブロックの「ポスト支配点」と称される。したがって、同じ例では、第１コードブロックは、第２コードブロックの「支配点」と称される。
【００２１】
ポスト支配木の計算を行うことによって、ポスト支配木内の「葉」であるコードブロックを決定する。葉は、ポスト支配木の終端、すなわち子を含まないノードを指す。その葉ブロックを実行するためには他のコードブロックを実行しなければならないが、他のコードブロックは、葉ノードの実行に依存しない。この例では、ポスト支配木３１０は、３つの葉、Ｘ、ＹおよびＺを含む。ノード６は、他のコードブロックがその実行に依存しないので、葉である。ノード３および４も同様に、ノード３および４の後に続くノード（ノード５および６など）を実行する前にこれらのノードが必ずしも実行されるとは限らないので、葉である。
【００２２】
ポスト支配木の他の葉が発見されると、最適化マップが生成される。最適化マップは、ポスト支配木の葉に対応するエントリ、および葉に到達するためにポスト支配木を介して通過されたアークを含む。この例では、最適化マップ３２０は、３つの葉ノード（Ｘ、Ｙ、Ｚ）についてのエントリ、および特定の各葉ノードに到達するために通過されたアーク（Ａ、Ｂ、Ｃ、Ｆなど）とのその関係を含む。プローブ挿入点をプログラムに関連するあらゆるアークではなく、最適化マップのエントリに対応する点に限定することによって、プログラムを計装するためのプローブ挿入が最適化される。
【００２３】
別の実施形態では、プログラムについて計算されたプローブが、ポスト支配木３１０内に挿入される。プローブをポスト支配木３１０内に挿入することによって、葉ノードの親ノードがトレースされるときに別のプローブに遭遇する場合、マッピングが停止し得るので、よりコンパクトなマッピングが提供される。したがって、プローブによって網羅されたとして既に示されたノードおよびアークもまた、別のプローブによっては網羅されない。バックエッジ、呼出し、および外部エントリポイントについて生成されたプローブもまた、ノードのマッピングをさらに洗練するためにツリー内に含められ得る。
【００２４】
図２および図３で、アークおよびブロックは、それぞれ文字および数字によって言及されているが、それぞれのアークおよびブロックを区別するためのすべての数字を含む、他の識別子を使用することもできる。
【００２５】
図４に、本発明による、プローブをプログラム内に最適に挿入することによってプログラムを計装する工程の例示的な操作フロー図を示す。工程４００は、計装のためにプログラムが選択される開始ブロック４０２で開始する。処理は、操作ブロック４０４で続行する。
【００２６】
操作ブロック４０４で、プログラムの制御フローグラフが計算される。制御フローグラフは、図２に示した制御フローグラフに類似し得る。制御フローグラフが生成されると、処理は、操作ブロック４０６に進む。
【００２７】
操作ブロック４０６で、制御フローグラフから、アーク−ブロックマップが構築される。一実施形態では、アーク−ブロックマップは、図２に示したアーク−ブロックマップに類似する。別の実施形態では、アーク−ブロックマップは、別個のメモリエントリである。それぞれのメモリエントリは、プログラムに対応するすべてのブロックおよびアークをリストする。ブロックのメモリエントリでは、特定のアークに対応するブロックに、その特定のアークに関するものとしてフラグが立てられる。アークのメモリエントリでは、それぞれのアークが、それに対応するブロックによってフラグが立てられる。したがって、アークまたはブロックについてのカバレッジデータに関する情報を取得することによって、関連するブロックおよびアークについてのカバレッジデータをそれぞれ解決できるように、アークとブロックが相互参照される。処理は、操作ブロック４０８で続行する。
【００２８】
操作ブロック４０８で、プログラムのためのポスト支配木が構築される。このポスト支配木は、図３で示したポスト支配木に類似するものでも、またポスト支配木を表すデータであってもよい。ポスト支配木が計算されると、処理は、操作ブロック４１０に移る。
【００２９】
操作ブロック４１０で、ポスト支配木に対応する最適化マップが構築される。最適化マップは、ポスト支配木の葉についてのエントリを含む。最適化マップは、プログラム内にプローブが挿入される対象となる他のエントリをも含む。ポスト支配木を構築するための工程について、下記の図５についての議論において説明する。最適化マップが計算されると、処理は、操作ブロック４１２に移る。
【００３０】
処理ブロック４１２で、最適化マップのエントリに対応するプローブがプログラム内に挿入される。プログラム内に挿入されるプローブの数は、プログラム全体についてのコードカバレッジデータを依然として提供しながらもプローブの数を減らすように最適化されている。処理は、ブロック４１４で続行する。
【００３１】
操作ブロック４１４で、プローブが挿入されているプログラムを表すバイナリが実行される。プログラムの実行中、プローブによって、実行時に使用されたプログラムの一部のデータが返される。処理は、操作ブロック４１６で続行する。
【００３２】
操作ブロック４１６で、バイナリが実行されている間、すなわちデータがプローブから返されると、戻されたデータは、最適化マップ上にオーバレイされる。最適化マップ上にデータをオーバレイすることによって、プローブをプログラムのアークに相関させる。つまり、最適化マップを使用して、コードの実行を意味するデータを返すプローブを、そのプローブに関連するアークに一致させる。最適化マップをオーバレイすることによって各プローブがその関連するアークに関連付けられると、処理は、操作ブロック４１８で続行する。
【００３３】
処理ブロック４１８で、最適化マップを使用して各プローブに関連付けられた各アークは、アーク−ブロックマッピングを使用して関連するブロックに再びマッピングされる。したがって、各プローブは、それらがコードの実行を報告している各ブロックにそれぞれ関連付けられる。ブロックレベルとアークレベルの両方にマッピングすることによって、そのプログラムのアークおよびブロックカバレッジデータが提供される。アークおよびブロックカバレッジデータによって、そのプログラムのコードカバレッジデータが提供される。コードカバレッジが提供されると、処理は最終ブロック４２０に進み、そこで処理４００が終了する。
【００３４】
図５に、本発明による、最適化マップを構築する工程の例示的な操作フロー図を示す。工程５００は入口ブロック５０２から入り、このブロック５０２で、図４で示した工程４００が、操作ブロック４１０に入る。処理は、操作ブロック５０４で続行する。
【００３５】
操作ブロック５０４で、前に計算されたポスト支配木の葉について、最適化マップ内にマップエントリが生成される。ポスト支配木のそれぞれの葉は、最適化マップ内のエントリをもたらす。したがって、最適化マップの各エントリは、プログラム内に挿入されるプローブをもたらす。制御フローグラフの各アークに相関するプローブではなく、ポスト支配木の葉に相関するこうしたプローブを挿入することによって、必要なプローブの数が大幅に削減される。最適化マップ内にポスト支配木の葉に対応するエントリが生成されると、処理は、判断ブロック５０６で続行する。
【００３６】
判断ブロック５０６で、プログラムの制御フローを介して、コードの実行フロー内にバックエッジが存在するか否かを判定するための別の受け渡しが行われる。上述のように、バックエッジは、プログラム内の２つ以上のコードブロックの間に共依存関係もたらす。バックエッジが存在しない場合、処理は判断ブロック５１０に進む。しかし、プログラム内にバックエッジが存在する場合、処理は操作ブロック５０８に移る。
【００３７】
操作ブロック５０８で、プログラムの実行フロー内に位置する各バックエッジを表すエントリが最適化マップに追加される。バックエッジは、プログラムの通常フロー外の工程段階を表し、したがってカバレッジ情報のためにプローブされる。それぞれのバックエッジについてエントリを最適化マップに追加することにより、発見された各バックエッジについてカバレッジデータが収集されるようにする。エントリが追加された後に、処理は、判断ブロック５１０で続行する。
【００３８】
判断ブロック５１０で、プログラムの制御フローを介して、コードの実行フロー内に任意の呼出しが存在するか否かを判定するための別の受け渡しが行われる。呼出しは、他の関数、またはコードの他の部分を実行させることができる。呼出しが存在しない場合、処理は判断ブロック５１４に進む。しかし、呼出しがプログラム内に存在する場合、処理は操作ブロック５１２に進む。
【００３９】
操作ブロック５１２で、プログラムの実行フロー内に位置する各呼出しを表すエントリが最適化マップに追加される。呼出しは、プログラムの通常フロー外の工程段階を表し、したがってカバレッジ情報のためにプローブされる。それぞれの呼出しについて最適化マップにエントリを追加することにより、発見された各呼出しについて、カバレッジデータが収集されるようにする。エントリが追加された後に、処理は判断ブロック５１４で続行する。
【００４０】
判断ブロック５１４で、プログラムの制御フローを介して、コードの実行フロー内に任意の外部エントリポイントが存在するか否かを判定するための別の受け渡しが行われる。一実施形態において外部エントリポイントは、コードの通常の実行パスの外部にあり、ポスト支配木内の葉で表されない。外部エントリポイントが存在しない場合、処理は、戻りブロック５１８に進み、そこで処理５００は、図４に示す操作ブロック４１２に戻る。しかし、プログラムに関して外部エントリポイントが存在する場合、処理は操作ブロック５１６に進む。
【００４１】
操作ブロック５１６で、プログラムの実行フロー内に位置する各外部エントリポイントを表すエントリが最適化マップに追加される。上述のように、外部エントリポイントは、プログラムの通常フロー外の工程段階を表し、したがってカバレッジ情報のためにプローブされる。それぞれの外部エントリポイントについて最適化マップにエントリを追加することによって、発見された各外部エントリポイントについて、カバレッジデータが収集されるようにする。エントリが追加された後に、処理は終了ブロック５１８に進み、そこで処理５００は図４に示す操作ブロック４１２に戻る。
【００４２】
上記の明細、例およびデータは、本発明の構成の製品および使用についての完全な説明を提供している。本発明の趣旨および範囲から逸脱せずに、本発明の多くの実施形態が作られ得るので、本発明は、添付の特許請求の範囲に帰属する。
【図面の簡単な説明】
【００４３】
【図１】本発明の例示的な一実施形態で使用することができる例示的なコンピューティング装置の図である。
【図２】本発明による例示的な制御フローグラフおよびアーク−ブロックマップの図である。
【図３】本発明による、図２の制御フローグラフおよびアーク−ブロックマップに対応する例示的なポスト支配木および最適化マップの図である。
【図４】本発明による、プローブをプログラム内に最適化に挿入することによってプログラムを計装する工程の例示的な操作フロー図である。
【図５】本発明による、最適化マップを構築する工程の例示的な操作フロー図である。
【符号の説明】
【００４４】
１０８  基本的な構成
１〜６、５０  ノード
Ａ〜Ｊ  アーク
Ｘ〜Ｚ  葉ノード
【図１】
2005302028.tif 000003
【図２】
2005302028.tif 000004
【図３】
2005302028.tif 000005
【図４】
2005302028.tif 000006
【図５】
2005302028.tif 000007
【外国語明細書】
2005302028000001.pdf