(57)【要約】【解決手段】  プログラム解析のために別個のコアを活用するサンプリングベースのＤＢＲフレームワーク。フレームワークは、ハードウエア性能モニタと、別個の処理として実行するＤＢＲサービスと、クライアント処理内で実行するＤＢＲエージェントとを含む。ＤＢＲサービスは、ハードウエア性能モニタからサンプルを集約し、ホットサンプルの周囲のプログラム構造を推定することによって領域選択を行い、選択された領域上で変形を行い（例えば最適化）、そして置換コードを生成する。ＤＢＲエージェントは次いで置換コードを用いるためにクライアント処理をパッチする。【選択図】図２
2013504124.tif 000002
【特許請求の範囲】
【請求項１】
動的バイナリリライタ（ＤＢＲ）フレームワークであって、
１つ以上のクライアント処理をサンプリングするハードウエア性能モニタと、
別個の処理として実行するＤＢＲサービスと、
前記１つ以上のクライアント処理内で実行するＤＢＲエージェントと、を備え、
前記ＤＢＲエージェントは置換コードを用いるために前記１つ以上のクライアント処理をパッチし、前記置換コードはそれぞれの１つ以上のクライアント処理のオリジナルコードと機能的に等価である、ＤＢＲフレームワーク。
【請求項２】
前記ＤＢＲサービスは、前記ハードウエア性能モニタからのサンプルを集約し、ホットサンプルの周囲のプログラム構造を推定することによって領域選択を行い、前記選択された領域上で領域変形を行い、前記置換コードを生成する請求項１のＤＢＲフレームワーク。
【請求項３】
前記１つ以上のクライアント処理の起動に際して前記ＤＢＲエージェントは前記それぞれの１つ以上のクライアント処理のクライアント処理アドレス空間内へ自動的にロードされると共に初期化され、
前記ＤＢＲエージェントは置換コードをパッチすること及びアンパッチすること並びに前記１つ以上のクライアント処理に著しい追加的な資源要求を課することなく必要なシステムライブラリ使用を報告することを実行する請求項１のＤＢＲフレームワーク。
【請求項４】
前記ＤＢＲサービスを前記１つ以上のクライアント処理から切り離すことは、利用可能であれば１つ以上の別個のコアを利用する一方でメモリ使用を最小化すると共に前記１つ以上のクライアント処理内の共有ライブラリを回避しつつ前記ＤＢＲサービスが前記１つ以上のクライアント処理と同時に実行することを可能にし、
前記ＤＢＲサービスを前記１つ以上のクライアント処理から切り離すことは、当該ＤＢＲによって用いられるシステム資源が連携させられ得るように前記ＤＢＲサービスが多重クライアント処理を管理することを可能にする請求項１のＤＢＲフレームワーク。
【請求項５】
前記ＤＢＲサービスを前記１つ以上のクライアント処理から切り離すことは、管理され且つ必要に応じて新たな置換を除去し又は作成する前記クライアント処理のスナップショットを連続的に取り込むよう前記ＤＢＲサービスが動作することを可能にする請求項１のＤＢＲフレームワーク。
【請求項６】
前記ＤＢＲサービスはＤＢＲ制御スレッドを備え、前記ＤＢＲ制御スレッドは前記ＤＢＲエージェントとの通信を管理すると共に前記ＤＢＲサービスの側面を連携させる請求項１のＤＢＲフレームワーク。
【請求項７】
前記ＤＢＲサービスは１つ以上のワーカースレッドを備え、各ワーカースレッドは領域選択動作、領域変形動作及び置換コード生成動作をクライアント処理のために実行する請求項１のＤＢＲフレームワーク。
【請求項８】
前記ＤＢＲサービスは前記１つ以上のクライアント処理内でホットコードを決定するためのシステムを更に備え、前記システムは、
ホットコード発見動作を実行することと、
コード区分化動作を実行することと、
通り抜けのみ計算動作を実行することと、
ホット呼び出しインライン化動作を実行することと、
パッチ点選択動作を実行することと、
コード刈り込み動作を実行することと、のための命令を備える請求項１のＤＢＲフレームワーク。
【請求項９】
前記ホットコード発見動作は、いかなる静的プログラム情報をも必要とすることなく、頻繁に実行されるものとして既知のアドレスから開始して前方へクライアント処理のコードをディスアセンブルし、
任意の制御フローを含む制御フローグラフを提供するために前記クライアント処理の制御フローが辿られる請求項８のＤＢＲフレームワーク。
【請求項１０】
前記ホットコード発見動作は、エントリマッピングと命令境界及び重複コードシーケンスに関する情報を記録している位置構造とを用いて重複命令を効率的に検出し、
可変長命令を伴うアーキテクチャ上で実行している場合及び戻らない呼び出しを呼び出し規則が有し得る場合に重複命令が生じ得る請求項９のＤＢＲフレームワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理システムに関し、より特定的にはプログラムのモニタリング実行に関し、更に特定的には動的バイナリリライタに関する。
【背景技術】
【０００２】
クライアント処理において実行中のコンピュータアプリケーションプログラムをモニタリングする場合、モニタプログラムは、クライアント処理を分析してより頻繁に実行されるコード（即ちホットコード）の領域を決定する必要があるであろう。そのようなモニタリングは、アプリケーションのオリジナルソースコードが容易には修正され得ず又は再コンパイルされ得ない場合に、システムにおいて生じ得る。モニタにとって利用可能な唯一の情報がランタイム情報である場合、これらの領域を位置付けると共に構築することは挑戦的であり得る。
【０００３】
動的バイナリリライタ(dynamic binary rewriter)（ＤＢＲ）の特定の種類である動的バイナリオプティマイザ(dynamic binary optimizer)（ＤＢＯ）を用い、プログラムの実行をモニタリングすると共に頻繁に実行される（即ちホットな）コードを最適化して性能を改善することが知られている。既知のＤＢＯは一般的には２種類に分類され、即ち解釈ベースのＤＢＯとサンプリングベースのＤＢＯとである。解釈ベースのＤＢＯは、インタープリタ又はジャストインタイムコンパイラを活用してプログラムの動的命令を観察する。サンプリングベースのＤＢＯは、インタープリタを外し、そして低オーバーヘッドサンプリングベースの技術を用いてホットコードを識別する。既知のＤＢＯは変形(transformation)のためにホットトレース(hot traces)を選択する。トレースは、実行の単一エントランス多重エグジット手続き間パス(a single entrance, multiple exit interprocedural path of execution)である。
【０００４】
ＤＢＲは、いかなる静的プログラム情報をも必要とせずにＤＢＲがネイティブバイナリ上で動作する点を除いて、管理されたランタイム環境と同様である。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明に従い、プログラム解析のために別個のコアを活用するサンプリングベースのＤＢＲフレームワークが説明される。フレームワークは、ハードウエア性能モニタと、別個の処理として実行するＤＢＲサービスと、クライアント処理内で実行するＤＢＲエージェントとを含む。ＤＢＲサービスは、ハードウエア性能モニタからサンプルを集約し、ホットサンプルの周囲のプログラム構造を推定することによって領域選択を行い、選択された領域上で変形を行い（例えば最適化）、そして置換コードを生成する。ＤＢＲエージェントは次いで置換コードを用いるためにクライアント処理をパッチする。
【０００６】
ＤＢＲは従前の静的情報を必要とせずにネイティブバイナリ上で動作する。従って、ＤＢＲはソースコードが利用可能でないレガシーバイナリ又はライブラリを変形することができる。また、ランタイムで動作することによって、ＤＢＲはコンパイルタイムで利用可能ではないであろう変形機会(transformation opportunities)を活用することができる。例えばＤＢＲは、現在のプログラム入力の挙動に基づいて変形を実行することができ、プログラムを特定の基礎的なアーキテクチャに合わせることができ、そして動的にリンクされたライブラリにわたって変形を実行することができる。
【図面の簡単な説明】
【０００７】
添付の図面を参照することによって、当業者にとって、本発明はよりよく理解されるであろうし、またその多くの目的、特徴及び利点が明らかになるであろう。それぞれの図面を通して同じ参照番号の使用は同様の又は類似の要素を指定する。
【０００８】
【図１】図１は動的バイナリリライタを有するコンピュータシステムのシステムブロック図である。
【０００９】
【図２】図２はサービスベースの動的バイナリリライタフレームワークのブロック図である。
【００１０】
【図３】図３は動的バイナリリライタの領域選択動作の疑似コード表現を示す図である。
【００１１】
【図４】図４は例示的なクライアントプログラム上で動的バイナリリライタのホットコード発見動作を実行した結果のブロック図である。
【００１２】
【図５】図５は例示的なクライアントプログラム上で動的バイナリリライタのコード区分化動作を実行した結果のブロック図である。
【００１３】
【図６】図６は例示的なクライアントプログラム上で動的バイナリリライタのホット呼び出しインライン化動作を実行した結果のブロック図である。
【００１４】
【図７】図７は例示的なクライアントプログラム上で動的バイナリリライタのパッチ点選択動作を実行した結果のブロック図である。
【００１５】
【図８】図８は例示的なクライアントプログラム上で動的バイナリリライタのコード刈り取り動作を実行した結果のブロック図である。
【００１６】
【図９】図９は例示的なクライアントプログラム上で動的バイナリリライタの完全な領域選択動作を実行した結果のブロック図である。
【００１７】
【図１０】図１０はホットコード発見動作の疑似コード表現を示す図である。
【００１８】
【図１１】図１１はコード区分化動作の疑似コード表現を示す図である。
【００１９】
【図１２】図１２はパッチ点選択動作の疑似コード表現を示す図である。
【発明を実施するための形態】
【００２０】
図１を簡潔に参照すると、コンピュータシステム１００のシステムブロック図が示されている。コンピュータシステム１００は、プロセッサ１０２と、ディスプレイ、キーボード、マウス及び関連する制御器（各々はコンピュータシステム１００に遠隔的に結合されていてよい）等の入力／出力（Ｉ／Ｏ）デバイス１０４と、ランダムアクセスメモリ（ＲＡＭ）等の揮発性メモリ並びにハードディスク及びドライブ等の不揮発性メモリを含むメモリ１０６と、光学的なディスク及びドライブ並びに他のメモリデバイス等の他の記憶デバイス１０８と、種々の他のサブシステム１１０とを含み、これら全ては１つ以上のバス１１２を介して相互接続される。
【００２１】
コンピュータシステムはメモリ１０６内に記憶される動的バイナリリライタ１３０を更に含み、動的バイナリリライタ１３０は、プロセッサ１０２（又はプロセッサ内の若しくは離れてはいるがプロセッサに結合ているコア（図示せず））によって実行可能である。動的バイナリリライタ１３０は、プロセッサ１０２内に含まれるハードウエア性能モニタ（ＨＰＭ）１３２と相互作用する。１つの実施形態では、ハードウエア性能モニタ１３２は、命令ベースのサンプリング（ＩＢＳ）をサポートする。命令ベースのサンプリングは、アーキテクチャイベントを特定の命令に正確に帰属させる統計的サンプリング技術である。ある実施形態では、ＩＢＳは各サンプリングインターバルでのフェッチ段階の間に命令をタグ付けする。タグ付けされた命令の実行の間に生じる任意のアーキテクチャイベントは、ＨＰＭ生成のサンプルにおいて報告される。他の実施形態は、アーキテクチャイベントを特定の命令に帰属させると共にそれらのイベントを報告するために、他の方法を用いてよい。
【００２２】
図２を参照すると、サービスベースの動的バイナリリライタフレームワーク１３０のブロック図が示されている。より具体的には、ＤＢＲフレームワーク１３０はサンプリングベースの手法を用いる。サービスベースの動的バイナリリライタフレームワーク１３０は、ハードウエア性能モニタ１３２、ＤＢＲサービス処理２１２及び軽量ＤＢＲエージェント２１４を含む。ＤＢＲサービス処理２１２は別個の処理として実行され、そして軽量ＤＢＲエージェントはクライアント処理２２０内で実行される。ＨＰＭ１３２は低オーバーヘッドプロファイリングを提供する。ＤＢＲサービス処理２１２は、ＨＰＭ１３２からのサンプルを集約し、そして集約されたサンプルを解析して領域選択及び置換コード生成を行う。ＤＢＲエージェント２１４は次いでクライアント処理２２０をパッチして（２２１）置換コードを実行する。ＤＢＲサービス処理２１２をクライアント処理実行から切り離すことによって、方法はクライアント処理への性能影響を最小限にしながら相当量の解析を行う。
【００２３】
サービスベースの動的バイナリリライタフレームワーク２００は、サンプリングを用いてクライアント処理の実行に関する複数種類の情報を集める。幾つかの実施形態では、情報を集めるために命令ベースのサンプリングが用いられる。他の実施形態は他のサンプリング方法を用いてよい。より具体的には、複数種類の情報は、命令ポインタアドレス情報、分岐ディレクション情報を含み、また限定はされないがロード目標アドレス情報を始めとする追加的な情報を含んでいてもよい。命令ポインタ（ＩＰ）アドレス情報は、サンプルに関連付けられている命令のアドレスを含む。分岐ディレクション情報は、サンプル命令が条件付き分岐命令である場合における条件の値を含む。ロード目標アドレス情報は、サンプリングされた命令がロードされる場合におけるメモリロケーションのアドレスを含む。
【００２４】
ＤＢＲエージェント２１４は、クライアント処理内で実行される軽量共有ライブラリである。起動時にＤＢＲエージェント２１４は自動的にクライアント処理アドレス空間内へとロードされ、そして初期化される。初期化は、ＤＢＲエージェント２１４が動作しているクライアント処理２２０内に新たなスレッドを作成する。ＤＢＲエージェント２１４は、ＤＢＲサービス処理２１２との通信接続を構成し、そして置換コード２３２を保持する共有メモリ空間２３０を割り当てる。ＤＢＲエージェント２１４は、接続を管理しつつ、要求等のメッセージに応答して、ＤＢＲサービス処理２１２によって共有メモリ内に直接的に置かれた置換コードをパッチすると共にアンパッチする。ＤＢＲエージェント２１４はまた、注意を要するであろうライブラリ呼び出し（例えばスレッド作成及びページ保護の変化）をフックすること及びエラー処理（例えばＤＢＲサービス処理２１２との通信の喪失）を実行することを含む種々の雑タスクを行う。
【００２５】
ＤＢＲサービス処理２１２は、クライアント処理２２０とは別個の処理において動作し、そして幾つかの実施形態では、個々のプロセッサコア（多重コアシステム上の）上又は個々のプロセッサ（多重プロセッサシステム上の）上で実行されてよい。ＤＢＲサービス処理２１２をクライアント処理から切り離すことによって、ＤＢＲサービス処理２１２はクライアント処理２２０と同時に実行され得る。また、切り離すことによって、メモリ使用が最小化されると共にクライアント処理と共有されるライブラリが回避される。更に、切り離すことによって、単一のＤＢＲサービス処理が多重クライアント処理をサポートすると共にシステム全体範囲で資源を管理することが可能になる。
【００２６】
ＤＢＲサービス処理２１２は、ＤＢＲエージェントとの通信を管理すると共にＤＢＲサービスの種々の側面を連携させる制御スレッド２４０を含む。新たなクライアント処理が始まると、それぞれのＤＢＲエージェントがＤＢＲサービスに接続する。初期接続において、制御スレッドは、クライアント処理に関する情報及びＤＢＲエージェントによって作成される共有メモリ区域２３２に関する情報を取得する。制御スレッド２４０は、共有メモリ２３２アドレス空間をＤＢＲサービス処理２１２のアドレス空間へとマッピングする。制御スレッド２４０は、修正されるべきではないプログラムをクライアント処理が実行中であることを決定してよく、そしてＤＢＲ１３０による更なる処理を無効にすることができる。
【００２７】
制御スレッド２４０は、周期的に短期間だけＨＰＭ１３２をアクティブにしてプロファイルスナップショットを収集する。制御スレッド２４０はＨＰＭ１３２からのサンプルを受信し、そしてクライアント処理及びＩＰアドレスに基づいてサンプルを集約する。短期間だけＨＰＭ１３２をアクティブにすることによって、クライアント処理は、多くの時間をサンプル収集オーバーヘッドから解放されて実行可能な状態に置かれる。当該期間の長さを調節することによって、ＤＢＲ２１２は、サンプリングのオーバーヘッドを置換コード生成の利益とバランスさせることができる。ＨＰＭ１３２を間欠的にアクティブにすることによって、ＤＢＲ２１２は、クライアント処理プログラム実行において生じることがある位相転移に応答することができる。幾つかの実施形態では、サンプリングのオーバーヘッドは、ＨＰＭ１３２の周期的な使用よりはむしろ連続的な使用を可能にするのに十分なほどに低くてよい。
【００２８】
ＤＢＲサービス処理２１２はまたワーカースレッド２４２のプールを含み、これらワーカースレッド２４２は制御スレッド２４０によって作成される。プロファイルスナップショットが取り込まれた後、制御スレッド２４０は、全体的なシステム負荷に基づいて幾つのワーカースレッドが同時に展開され得るのかを決定する。制御スレッド２４０はまた、どのクライアント処理がどんな順序で修正されるべきか（もしあれば）を決定する。制御スレッド２４０は次いで、ワーカースレッドを開始し、そしてスリープ前で次のスナップショットインターバル迄それらが完了するのを待つ。制御スレッド２４０は置換コードの有効性を評価することもでき、また適切である場合には置換コードをアンパッチすることができる。例えば制御スレッド２４０は、置換コード内にあるスナップショットにおけるサンプルの割合をモニタリングすることができる。
【００２９】
ワーカースレッド２４２が一旦アクティブにされたならば、ワーカースレッドは、特定のクライアント処理に対して、領域選択と置換コードの生成とを行う。ワーカースレッド２４２は、制御スレッド２４０によって提供される機能を用いて、集約されたサンプルにアクセスし、クライアント処理アドレス空間を読み出し、置換コードをクライアント処理の共有メモリ内に置き、そしてパッチをインストールするようにＤＢＲエージェント２１４に通知する。領域選択及び置換コード生成が最初に行われた時点での状態に適合しないようなやり方でクライアント処理のアドレスマッピングが変更された場合には、置換コードは使用されない（例えば、参照されたコード又はデータが、アンロードされてしまったライブラリ内に含まれている、あるいはページ保護が更新されてしまっており、それらはもはやリードオンリでない）。ＤＢＲサービス処理２１２及びＤＢＲエージェント２１４は協働して、そのようなイベントが生じた場合に置換コードがインストールされないこと又はアンパッチされることを確実にする。
【００３０】
図３を参照すると、動的バイナリリライタ１３０の領域選択動作の疑似コード表現が示されている。より具体的には、ＤＢＲ１３０は、プログラムのいかなる静的予備知識なしにもホットコードの区域を識別するために、領域選択動作３００を組み込んでいる。ＤＢＲ領域選択動作３００は、その結果を中間表現(intermediate representation)（ＩＲ）において超領域(super-regions)（ＳＲ）として表現する。超領域は任意の制御フローを表現することができ、また多重入れ子ループ(multiple nested loops)及びスパン多重手続き境界(span multiple procedure boundaries)からのコードを含んでいてよい。超領域内では、ＩＲは制御フローを単一エントランス単一エグジット有向非巡回グラフ(single entrance, single exit directed acyclic graph)として表現する。
【００３１】
グラフのノードが基本ブロック（ＢＢ）であり、そしてエッジが制御フローエッジ（ＣＦＥ）である。各ＳＲは複数の基本ブロックを含む。より具体的には、各ＳＲは開始基本ブロック、末尾基本ブロック及びゼロ個以上の本体基本ブロックを含む。開始基本ブロックは、共通エントリ点を提供する疑似基本ブロックである。開始ブロックからエグジットしているエッジはエントリエッジと称され、そしてオリジナルクライアントコードから置換コードがエンターしていることを表す疑似エッジである。末尾基本ブロックは、共通エグジット点を提供する疑似基本ブロックである。末尾ブロックにエンターしているエッジはエグジットエッジと称され、そして置換コードをそのままにすること及びオリジナルクライアントコードにおける実行を継続していることを表す疑似エッジである。本体基本ブロックは、リアルプログラムコードを表す。本体基本ブロックは変形させられて置換コードを生成する。
【００３２】
領域選択動作３００によって生成される最終的な超領域においては、本体基本ブロックは、エントリエッジがパッチ点をその内部で定義する単一の接続要素(single connected component)を形成する（即ち置換コードをエンターするためにパッチされるクライアントプログラム内アドレス）。超領域の単一のエントリ及びエグジットは、それを従来のコンパイラ解析及び最適化に従わせる。
【００３３】
領域選択動作３００は、ホットコード発見動作(hot code discovery operation)を行うことによって開始する。次いで領域選択動作３００はコード区分化動作(code partitioning operation)を行う。次いで領域選択動作３００は、通り抜けのみ計算(fall through only computation)及びホット呼び出しインライン化動作(hot call inlining operation)を行う。次いで領域選択動作３００は、パッチ点選択動作(patch point selection operation)及びコード刈り込み動作(code pruning operation)を行う。
【００３４】
図４を参照すると、例示的なクライアントプログラム上で動的バイナリリライタ１３０のホットコード発見動作を実行した結果のブロック図が示されている。ホットコード発見動作は、集約されたＨＰＭサンプルをホットサンプル基本ブロックに対するシードアドレス(seed address)として用いる。ホットコード発見動作は、制御フローを辿りながら前方へとクライアントコードをディスアセンブルする(disassembles)。発見は、ホットである基本ブロックからの指定数の条件付きジャンプを投機的に試行することによって調節される(throttled by venturing)。結果は、ホット命令の周囲のクライアントプログラム構造を表現するように接続される基本ブロックのセットを含む単一の超領域である。
【００３５】
図５を参照すると、例示的なクライアントプログラム上で動的バイナリリライタ１３０のコード区分化動作を実行した結果のブロック図が示されている。コード区分化動作は、基本ブロック、及び単一の超領域制御フローグラフの各接続要素の制御フローエッジを別個の超領域内へ移動させる。コード区分化動作はまた、任意の必要なエントリエッジ及びエグジットエッジを追加して、別個の超領域の全ての基本ブロックを開始ブロック及び末尾ブロックポストが支配することを確実にする。
【００３６】
ホットコード発見動作は命令をディスアセンブルする一方で、ホットコード発見動作は、サンプル集約器を参照すると共に、作成される基本ブロック及び制御フローエッジ上でのサンプルカウントを記録する。後続へ通り抜けるのみの基本ブロックは明示的な分岐命令を有していないので、制御フローエッジ上には記録するのに利用可能なサンプルはない。そこで、通り抜けのみ計算動作（図３参照）によって、非通り抜けのみ制御フローエッジのカウントからカウントの近似が計算される。
【００３７】
図６を参照すると、例示的なクライアントプログラム上で動的バイナリリライタ１３０のホットコードインライン化動作を実行した結果のブロック図が示されている。ホット呼び出しインライン化動作は、任意のホット基本ブロックが呼び出し命令を含むかどうか、及び目標アドレスからの戻り命令が到達可能なその目標アドレスに対応する基本ブロックを伴う超領域があるかどうかを決定する。これらの条件が真である場合には、ホット呼び出しインライン化動作はルーチンをインライン化する。
【００３８】
図７を参照すると、例示的なクライアントプログラム上で動的バイナリリライタ１３０のパッチ点選択動作を実行した結果のブロック図が示されている。ホットコード発見動作によって作成される超領域内の全てではない基本ブロックがパッチされ得る。ＤＢＲ１３０のパッチ点選択動作は、ドミネータ(dominator)及びループ解析を用いて、各超領域に対して良好なパッチ点のセットを識別する。
【００３９】
図８を参照すると、例示的なクライアントプログラム上で動的バイナリリライタ１３０のコード刈り込み動作を実行した結果のブロック図が示されている。コード刈り込み動作では、ループを有していない超領域は小さすぎると見なされ、ループを有していない超領域又はパッチ点を有していない超領域は削除される。単に超領域からエグジットする任意のコールド(cold)末尾基本ブロックもまた、エントリエッジを変更するパッチ点選択動作において生じた任意の未到達の基本ブロックと共に削除される。
【００４０】
図９を参照すると、例示的なクライアントプログラム上で動的バイナリリライタ１３０の完全な領域選択動作３００を実行した結果のブロック図が示されている。作成された最終的な超領域が示されている。
【００４１】
図１０を参照すると、ホットコード発見動作の１つの実施形態の疑似コード表示が示されている。ＤＢＲ１３０においては、全ての静的プログラム情報（例えば記号テーブル及びデバッグ情報）を削り取られたバイナリを実行中であってよい。従ってホットコード発見動作は、この情報なしにプログラムの構造を動的に発見する。ＨＰＭ１３２が適切な情報を提供しないと、間接呼び出し、間接ジャンプ、及び戻り(returns)等の幾つかの制御フローが追従することは困難であり得る。正常な呼び出しでさえ、それらがいつも戻るのかについてをＤＢＲ１３０が確かではないであろうという理由で、困難性を提示し得る（例えばエグジットのようなルーチンを呼び出すこと）。コンパイラはこれらをルーチンのコードの末尾に置いてよく、ルーチンのデータ（例えばジャンプテーブル）が即座に追従する。
【００４２】
可変長命令セットアーキテクチャ（ＩＳＡ）（例えばｘ８６プロセッサアーキテクチャと同様のプロセッサアーキテクチャ内に存在し得るような）は、別の挑戦を提示する。既知の命令アドレスを与えられて、ＤＢＲ１３０は前方へとディスアセンブルすることができるのみである。可変長エンコーディングは、先の命令の開始を区別することを極めて困難にする。制御フローに関して正しくない前提が作られると、ＤＢＲ１３０は、リアル命令の中ほどにおけるバイトを結局はディスアセンブルすることになり得る。
【００４３】
そこで、集約されたＨＰＭサンプルによって識別されるホット命令で開始しているクライアントプログラムの制御フローをホットコード発見動作が探索する。それが作成する全ての基本ブロック及び制御フローエッジは、領域選択動作の間に割り当てられる単一の超領域、第１ｓｒ(first_sr)内に割り当てられる。
【００４４】
ホットコード発見動作が漸進的に探索するのに従って、動作は、基本ブロックの先頭である又は潜在的に先頭になり得る各クライアントアドレスに関する知見を追跡する。ホットコード発見動作はマッピングデータ構造と共にこれを行い、マッピングデータ構造は当該各アドレスに対する個々のエントリを含んでいる。アドレスがうまくディスアセンブルされた場合には、ホットコード発見動作は、作成される基本ブロックをそのサイズ及び命令境界と共に記憶する。アドレスが未だディスアセンブルされていない場合には、そのサイズが単一バイトであるものと一時的に仮定されると共に、既に作成され且つ当該アドレスを目標としている制御フローエッジのセットが記録される。これらの制御フローエッジは、末尾基本ブロックへのエグジットエッジとして当初作成されるが、アドレスがディスアセンブルされる場合又はされるとすれば、制御フローエッジは更新されてそれらの目標としての新たな基本ブロックを有することになる。また、アドレスがディスアセンブルされ得ないと決定される場合には、当該事実が記録されると共にそれに向かう全ての制御フローエッジは既存エッジのままである。マッピング構造は、各命令が一回だけディスアセンブルされることを確実にすると共に発見処理の漸進的性質をサポートする。
【００４５】
漸進的な探索を管理するためにワークリストがホットコード発見動作によって用いられ、ワークリストは、既に発見されている基本ブロックであってそれらの後続の制御フローが辿られることを必要とするであろう基本ブロックを含んでいる。基本ブロックが最初に作成されるとき、その基本ブロックは常にワークリスト上に置かれる。ホットコード発見動作は、ホットサンプルに対応するアドレスのセットに対するサンプル集約器にクエリすること(querying)によって開始する。これらのアドレスの各々に対して、ホットコード発見動作は、ＢＢ確保関数(ENSURE-BB function)を呼び出すことによって、基本ブロックがあることを確実にする。基本ブロックは、複数のサンプルを有する多重命令を含み得るので、開始(starts)は誤り(false)としてパスされる。このことは、基本ブロックは要求されているアドレスで開始することを必要としておらず、単に、要求されているアドレスを命令境界として含むことを必要としていることを表している。
【００４６】
次に、ワークリスト処理関数(function PROCESS-WORK-LIST)が呼び出され、この関数は、ワークリストが空になるまでワークリストから基本ブロックを取り込み続けると共に基本ブロックを処理する。基本ブロックを処理することは、その後続の制御フローエッジの各々が目標基本ブロックを確実に有するようにすることを備え、同時に更なる基本ブロックをワークリストに加えてよい。ホットコードからどれくらい離れたところで発見が探索し得るかを調節するために、各基本ブロックは、ホット起点ジャンプ数(jumps-from-hot)、つまりホットサンプル基本ブロックからそれが離れている条件付きジャンプの数でタグ付けされる。ホットサンプルを含む任意の基本ブロック又はそのような基本ブロックから無条件に到達可能なホットサンプルを含む任意の基本ブロックは、ホット起点ジャンプ数として０を有している。このようにホットサンプル基本ブロックに対しては、ｊｆｈは０をパスされる。後続の制御フローエッジは、それらがホット起点ジャンプ数の制限下にある場合にのみ辿られる。サンプリングの統計学的性質は、実際上はホットであるコードに公正な数のサンプルを得させない可能性がある。このことは、極めて小さい基本ブロックに対して特に問題である。ホット起点ジャンプ数メカニズムは、これらのアーティファクト(artifacts)を滑らかにする。ホット起点ジャンプ数メカニズムはまた、短いがそれほど頻繁には実行されない、ホットコードからの及びホットコードへ戻るパスがＳＲ内に含まれるようにすることに役立つ。これにより、超領域からエグジットすること及び置換コードの利益を失うことが回避される一方で、含まれている非ホットコードの量が制限される。
【００４７】
後続の制御フローエッジがエグジットエッジである場合には、制御フローエッジの目標アドレスに対してＢＢ確保関数が呼び出される。この場合、ソース基本ブロックはそのアドレスに移動している最中であるから、基本ブロックはそのアドレスで開始する必要がある。そうでない場合には、目標基本ブロック上でホット起点ジャンプ数セット関数(function SET-JUMPS-FROM-HOT)が呼び出される。供給されたホット起点ジャンプ数が基本ブロックの現在の値よりも少ない場合には、基本ブロックが更新されると共にワークリスト上へ戻される。これにより、より小さい値がその後続へと伝搬されることを可能にし、以前は限界を超えていた制御フローエッジの探索をもたらすであろう。
【００４８】
実際には未だ実行されていない追従制御フローパスは、命令ではないバイトがディスアセンブルされることを可能にする。これらのバイトは、幾つかの他の追従制御フローパスによって到達可能な実際の命令と重複してさえいるかもしれない。これに対処するために、マッピングは、同じアドレスを対象とする多重エントリが存在することを可能にする（唯一の規則はそれらが互いに切り離された(disjoint)命令境界を有していることである）。これを確実にするために、基本ブロックディスアセンブル関数(function DISASSEMBLE-BASIC-BLOCK)は、命令をディスアセンブルするときに次の命令のアドレスが既存のエントリの命令境界に一致するかどうかを簡単に決定する必要がある。
【００４９】
この決定は位置データ構造によって簡単に達成され、位置データ構造は、もしあればマッピングにおいて重複しているエントリに関する情報を記録し、重複しているエントリの範囲は、それが位置するアドレスを含む。また、もしあれば重複しているエントリのどれがその命令境界の１つ（命令境界切り離し要求によって最大で１つがあり得る）としてアドレスを有しているのかを、位置が記録する。これは整合エントリ(match entry)と称される（ホットコード発見動作における．エントリ(.entry)表記によってアクセスされる）。最後に、位置はまた、次のエントリに関する情報を記録する。次のエントリは、当該位置のアドレスより大きく且つ最小のアドレスを伴う１つである（この場合にも同じ理由により最大で１つがあり得る）。位置は、新たなアドレスに簡単に進められ得るし、またその記録された情報の全てを漸進的に更新する。
【００５０】
アドレスに対して重複しているエントリを計算することを容易にするために、エントリは、もしあればその親エントリ、即ち最小のアドレスの重複しているエントリを記録する。これにより、行われるべき（位置獲得関数(function GET-POSITION)によって行われるべき）検索は、重複コードに対する条件はまれであるという理由で、通常はゼロに収められる。逆に、エントリが生成され又は更新される場合（新ＢＢ関数(function NEW-BB)、エントリ併合関数(function MERGE-ENTRY)等によって）には、親エントリを経済的に計算するために必要な、そしてどの他のエントリがそれらの親エントリの更新を必要としているのかを決定するために必要な、重複しているエントリを含む位置が常に提供される。
【００５１】
ＢＢ確保関数は、エントリ発見関数(FIND-ENTRY)を用いて、アドレス(addr)を含むエントリが既にあるかどうかを決定する。当該アドレスで開始するエントリを戻すことをエントリ発見関数が要求された場合、エントリ発見関数は、位置獲得関数によって戻された位置をチェックして、基本ブロック（アドレスは既にディスアセンブルされていることを示している）を有する整合エントリをそれが有しているかどうかを決定する。そうである場合において、アドレスが基本ブロックの開始ではないときには、エントリ発見関数は、エントリ及び関連する基本ブロックを分割する。基本ブロックがワークリスト上にあった場合には、分割の下部に対応する新たな基本ブロックと交換され得る。何故ならば、基本ブロックはその後続を探索するためにワークリスト上にあり、また分割基本ブロックの上部に対する基本ブロックは通り抜けのみ制御フローエッジのみを有しており、そして探索を必要とする制御フローを今や有しているのは下部であるからである。
【００５２】
エントリ発見関数によってＢＢ確保関数へと返された位置がチェックされて、既存のエントリが既にアドレスを命令境界として有していることを表示している整合エントリをその位置が有しているかどうかが決定される。サポートされないものと整合エントリが標識付けされてしまっている場合には、当該アドレスで生成される基本ブロックはあり得ない。制御フローエッジの目標として呼び出された場合、制御フローエッジはエグジットエッジのままであろう。整合エントリが基本ブロックを有している場合には、エントリは既にディスアセンブルされているので更なるアクションは必要ない。しかし、ｊｆｈがより小さい場合に基本ブロックのホット起点ジャンプ数が更新されている場合には、その小さな値が伝搬され得るように、基本ブロックはワークリストへと戻されてよい。
【００５３】
この時点でＤＢＲ１３０は、事前にアドレス(addr)で開始してディスアセンブルされてしまった命令がないことを知る（さもなければ、それを含むエントリがあったことになる）。そこでＤＢＲ１３０はＢＢディスアセンブル関数(DISASSEMBLE-BB function)を呼び出し、この関数は命令をディスアセンブルすると共に任意の数の状態が存在するまで位置を前進させる。より具体的には、ＤＢＲ１３０は、命令をディスアセンブルし、そしてＤＢＲ１３０が制御転送命令に到達し、サポートされていない若しくは不正な命令に遭遇し、又は不存在の若しくは非リードオンリの実行可能なクライアントメモリにアクセスすることを試みるまで、位置を前進させる。加えて、幾つかの命令はそれら自身の基本ブロック内にあることが要求される。代替的には、ＤＢＲ１３０は、命令をディスアセンブルし、そして位置を前進させた後に、ＤＢＲ１３０が後続のエントリに到達し又は重複しているエントリの命令境界に同期したことのいずれかを表示する整合エントリを位置が有するまで、位置を前進させる。代替的には、ＤＢＲ１３０は、命令をディスアセンブルし、そしてＤＢＲ１３０がパッチ命令の一部である任意のバイトに遭遇するまで、位置を前進させる（共有メモリマネージャを調べることによって決定される）。パッチは１つのロケーションまで行くことができ、そしてＤＢＲ１３０が同じクライアントコードに対して置換コードの多重バージョンを生成することは、コードローカリティの有効性を低減するであろうから、望ましくない。制御スレッドは置換コードの有効性をモニタリングすると共にそれを選択して除去することができ、関連するクライアントコードが再び候補になることを可能にしている。
【００５４】
ＢＢディスアセンブル関数は、ＢＢの全ての制御フロー目標のアドレスと、全ての目標に対するサンプルカウントと、命令の全サンプルカウントと、サンプルを伴う最初の命令のアドレスと、最初のパッチ可能命令と、命令境界とを含む制御フローと共に、基本ブロックの最新の命令に追従するアドレスの位置を戻す。
【００５５】
制御フロー命令の目標アドレスは、多数の方法の１つによって決定される。（１）最新の命令が条件付きジャンプである場合には、ＢＢディスアセンブル関数はＨＰＭ分岐ディレクションサンプル情報を用いる。（２）メモリ間接制御転送に対しては、ＢＢディスアセンブル関数はリテラルアドレス(literal address)又はＨＰＭロード目標アドレスサンプル情報を必要に応じて用いる。ＢＢディスアセンブル関数はそれらのロケーションを読み出して可能な目標アドレスを見つける。（３）リードオンリメモリからロードする場合には、ＢＢディスアセンブル関数はアドレスを信頼し、そうでない場合には、ＢＢディスアセンブル関数は、命令が実行されてからロケーションが変更されている可能性があるという理由で、アドレスがサンプルを有しているときにだけそのアドレスを信頼する。（４）非リテラルリードオンリメモリ間接に対しては、ＢＢディスアセンブル関数はまた、他の目標があるであろうことを示す疑似的未知目標(pseudo-unknown-target)を含む。（５）レジスタ間接は、レジスタ間接コード発見関数(DISCOVER-REGISTER-INDIRECT-CODE function)によって取り扱われる。（６）目標アドレスを直接的に提供するＨＰＭ１３２が利用可能である場合には、ＢＢディスアセンブル関数は代わりにその情報を用いることができる。
【００５６】
尚、ＢＢディスアセンブル関数は任意の命令をディスアセンブルすることはできないであろう。この場合、ＢＢ確保関数は非サポート設定関数(SET-UNSUPPORTED function)を呼び出し、この関数は必要に応じてマッピング内にエントリを作成すると共にそのエントリを非サポートとして標識付ける。任意の係属中制御フローエッジはエグジットエッジのままである。
【００５７】
当該アドレスに整合エントリがあることを後続の位置が表示している場合、ＢＢ確保関数は、可エントリ併合関数(CAN-MERGE-ENTRY function)を呼び出して、まさにディスアセンブルされた命令をも含むように整合エントリが拡張され得るかどうかをチェックする。この状態は、リアル基本ブロックの中ほどにあるように発生したホットサンプルから後続のエントリが作成された場合に生じ得る。以下の全てが真である場合に併合が生じ得る。（１）制御フロー(control_flow)の値が、ディスアセンブルされた命令が通り抜けのみで終了したことを示している。（２）後続の位置が整合エントリを有している。（３）その整合エントリが後続の位置のアドレスで開始する。この条件は、重複しているエントリにＢＢディスアセンブル関数が同期した場合には当てはまらないであろう。当てはまる場合には、重複しているエントリは分割されなければならず、これはＢＢ確保関数が通り抜けのみ制御フローエッジを追加する場合に自動的に生じるはずである。（４）後続のエントリが、先行制御フローエッジを伴わない基本ブロックを有しており且つ自身の基本ブロック内にある必要のある命令を有していない。基本ブロックを伴わないエントリは、サポートされていないか又は係属中の制御フローエッジの目標として生成されているかのいずれかであるから、併合されない。
【００５８】
エントリ併合関数は、ポス．エントリ(pos.entry)がもし１つあればその値により指定されるマッピングエントリを削除することによって併合動作を行い、後続のエントリ及びそれに関連する基本ブロックを更新して新たなアドレスで開始し、そして更新された位置を戻す。そうでない場合には、新ＢＢ関数が呼び出されて、基本ブロックを作成すると共にポス．エントリによって指定されるマッピングエントリに基本ブロックを関連付け、必要であれば１つを作成する。いずれの場合にも、ホット起点ジャンプ数セット関数がＢＢ確保関数によって呼び出されて、基本ブロックのホット起点ジャンプ数を更新すると共に必要に応じて基本ブロックをワークリストへ追加する（このことは、新たな基本ブロックに対して、それらがデフォルトとして無限で作成されているという理由で、常に生じることになる）。ポス．エントリの値によって指定されるマッピングエントリが任意の係属中の制御フローエッジを有している場合には、制御フローエッジは全て更新されて、エグジットエッジである代わりに、新たに作成された基本ブロックに接続する。
【００５９】
制御フロー追加関数(ADD-CONTROL-FLOW function)は、新たな基本ブロックが作成された場合にＢＢ確保関数によって呼び出される。この関数は、基本ブロックの目標の各々に対して制御フローエッジを作成する。目標に対して基本ブロックを伴うエントリがある場合、制御フローエッジは単純にそれに接続し、そうでない場合には、エグジット制御フローエッジが末尾基本ブロックに向けて作成されると共に、係属中ＣＦＥ追加関数(ADD-PENDING-CFE function)が呼び出されて、目標アドレスに対するエントリの係属中制御フローエッジに制御フローエッジを付け加え、必要であれば１つを作成する。任意の未知の目標が末尾基本ブロックに接続され、未知の目標に対しては、それら目標がアドレスを有していないという理由で、エントリは作成されない。これらのエグジット制御フローエッジは、他の制御フローエッジによって明示的に表される以外に目標に向かう間接的な転送の結果を示している。
【００６０】
インラインホット呼び出し関数(INLINE-HOT-CALLS function)を容易にするために、呼び出しの制御フローは特別に表される。第一に、ＤＢＲ１３０は、呼び出し命令は戻るものであり且つその後の制御フローに追従することを常に前提とする。これにより、ＤＢＲ１３０はインライン化に必要な完全な制御フローグラフを確実に有する。尚、このことは実際上常に正くはないかもしれないが（例えば、戻ったことをコンパイラが知らないルーチン、又は呼び出しの後に置かれたリテラル引数データをスキップするように戻りアドレスを調節することによるような非標準的な方法で戻るルーチンへの呼び出し）、パッチ不能標識付け関数(MARK-UNPATCHABLE function)がこの問題を軽減する。第二に、ＤＢＲ１３０は、呼び出しから呼び出し目標基本ブロックへの制御フローを２つの制御フローエッジとして表し、１つは呼び出しから末尾基本ブロックへのものであり、もう１つは開始基本ブロックから呼び出し目標基本ブロックへのものである。これらの規則は、コード区分化関数(PARTITION-CODE function)が、異なるルーチンに対するコードを別個の超領域へと分離することを可能にし、インライナを支援する。
【００６１】
新ＣＦＥ関数(NEW-CFE function)及び新ＢＢ関数がこの問題に自動的に対処する。呼び出しエッジを作成することを新ＣＦＥ関数が依頼されている場合において、呼び出し目標基本ブロックが既に存在するときには、この関数は即座にエントリ制御フローエッジを作成する。そうでないときには、この関数はエントリを呼び出し目標として標識付け、そしてその作成は、新ＢＢ関数がそのエントリに対して基本ブロックを作成するまで（あるとすれば）延期される。戻り命令(return instructions)はエグジット制御フローエッジを単に有する。
【００６２】
ＤＢＲ１３０は、呼び出しを配置すると共に命令をそれら自身の基本ブロック内に戻して、インラインホット呼び出し関数がそれらの制御フローを修正し、それらを疑似命令へと変換し、又はそれらを削除するように機能することをより容易にする。カスケードされた間接制御フロー変形に関する間接制御フロー命令に対しても同様である。
【００６３】
間接コード発見関数(DISCOVER-INDIRECT-CODE function)は、ＢＢディスアセンブル関数によって発見されるものを超えて、間接制御転送命令に対する目標を推定することを試みる。間接コード発見関数は、手順基本ブロック(proceeding basic blocks)におけるものを含めて手順命令(proceeding instructions)を検査することによってこれを行う。ＢＢ発見関数は、当該時点において手順基本ブロックが未だ発見されていないであろうから、この検査を行うことができない。間接コード発見関数が成功すれば、目標を制御フロー追加(ADD-CONTROL-FLOW)へ渡す。これにより、より多くの基本ブロックをワークリストに追加することができるので、間接コード発見関数はワークリスト処理(PROCESS-WORK-LIST)を呼び出す。これら２つのステップを行うことは、更なるコードが発見されなくなるまで繰り返してなされてよい。
【００６４】
間接制御転送命令の目標を推定するために多数の戦略が用いられる。（１）索引付けられたメモリ間接に対しては、基本ブロック及びそれに先行する基本ブロック内の命令が検査されて、ジャンプテーブルが索引付けられているかどうかを決定する。このことは索引境界チェックコード(index bounds check code)によって認識される。テーブルのアドレスを決定するための試みもなされる（例えば、アクセスは絶対的又はＩＰ相対的な基本アドレスを用いてよい）。テーブルアドレス、索引範囲、及び用いられているアクセスサイズが知られて、テーブルがリードオンリメモリ内にあるかどうか、そしてもしそうであれば目標アドレスを得るために内容が読み出されるかどうかを確かめるためにチェックがなされる。この手法は、スイッチテーブルのために共通コンパイラによって生成されるコードイディオムを取り扱うことができる。（２）レジスタ間接に対しては、即時手順命令が検査されて、場合によっては先行する基本ブロックに戻り、レジスタを画定しているものを配置する。ロード命令である場合には上記（１）がチェックされてよく、そうでない場合には、目標はＢＢディスアセンブル関数によるのと同じようにして決定される。この手法は、間接呼び出しのために共通コンパイラによって生成されるコードイディオムを取り扱うことができる。分岐目標情報を直接的に提供するＨＰＭが利用可能である場合には、この戦略の代わりにＨＰＭが用いられ得る。
【００６５】
パッチ不能標識付け関数は、命令をパッチすることが、重複している命令に含まれるバイトを破損しないようにすることを確実にする。パッチ不能標識付け関数は、マッピングをウォーキングすること及び他のエントリと重複しているエントリに関連する全ての基本ブロックをパッチ不能であるとして標識付けることによってこれを行う。エントリの存在は、たとえそれがサポートされていない又はホット起点ジャンプ数限界を超えていることにより探索されないことが判明するとしても、当該アドレスへの制御転送が検出されたことを表すから、他のエントリが基本ブロックを有しているかどうかにかかわらず、このことは行われる。重複しているエントリを検出するために、親エントリ情報が用いられる。
【００６６】
加えて、パッチ不能標識付け関数は、既に実行されたと知られている基本ブロックから到達可能でない基本ブロックがある場合にそれらをパッチ不能であると標識付けることによって、実際には命令でないバイトをパッチすることを防止する。この動作は、サンプルを伴う命令を含む基本ブロックで開始して制御フローグラフをウォークし、そして後続の制御フローエッジを辿る。呼出し命令通り抜け制御フローエッジは、前述したように呼び出しは実際には戻らないので、無視される。この動作は、サンプルを伴う最初の命令に関する情報を提供するＢＢディスアセンブル関数によって、及びそれを命令境界情報からの助力と共に維持している他のエントリ動作によって支援される。制御フローグラフをウォークする前に、この動作は基本ブロックを３つのセットに区分化し、サンプルを有していない基本ブロック、一部はサンプルを有しているが最初の命令でのものではないブロックは実行されず、そして最初の命令でのサンプルを有しているブロックが実行される。当該一部の及び実行された基本ブロックの全てはワークリストに加えられる。ワークリスト上の基本ブロックが次いでこの動作で処理される。各基本ブロックは、それをワークリストから除去すること及びそれに続く制御フローエッジを辿ることによって処理される。呼び出し制御フローエッジが辿られる場合、対応する呼び出し目標基本ブロックが目標として用いられる。しかし、呼び出し通り抜け制御フローエッジは、呼び出しは実際には戻らないであろうことを理由として無視される。他の制御フローエッジに対しては、目標が直接的に用いられる。実行されなかったセット内に目標がある場合には、それは最初はなかったものであるから、実行されたセットへ移動させられると共にワークリストへ加えられ、当該一部のセット内にある場合には、最初の命令は今や幾つかの他の基本ブロックの実行された命令から到達可能であると知られているから、実行されたセットへと移動させられ、他の場合には、既に実行されたセット内にあるから無視されてよい。ワークリストが空になると、（１）実行されなかったセット内に残っている全ての基本ブロックはパッチ不能であると標識付けられ、そして（２）当該一部のセット内の全ての基本ブロックはサンプルを伴う最初の命令の直前に分割され、そして上部に対応する基本ブロックはパッチ不能であると標識付けられる。
【００６７】
一旦ホットコード発見が完了すると、マッピング構造は削除される。
【００６８】
図１１はコード区分化動作の疑似コード表現を示している。より具体的には、ＤＢＲ１３０は今や、基本ブロックのセット及びＤＢＲがそれらの間で発見した制御フローエッジからなる１つの大きな超領域を有している。この超領域は、ホットコードの独立した複数の区域に対応する多重独立接続のサブグラフを含む傾向がある。サブグラフ間には制御フローはないので、ＤＢＲ１３０はサブグラフのための置換コードを独立に生成することができ、より効率的である。
【００６９】
サブグラフを独立に処理することは、結果として各ホット区域に対してコードローカリティの利益をもたらす。この処理はまた、各ホット区域が別個に管理されることを可能にする（例えばホットでなくなる区域をパッチ不能にする一方でホットのままである区域を維持する）。また、異なるルーチンに対するコードが互いに切り離されたサブグラフ内にあるように、コード発見は呼び出しを丹念に表現する。インライナ経験則(inliner heuristics)は、それらがルーチン上で独立して動作し得る場合に、実行するインライン化の量を見積もることにおいて、より効果的である。
【００７０】
これらの理由により、ＤＢＲ１３０は、互いに切り離されたサブグラフ内へとコードを区分化し、そして各々を別個の超領域内に置く。従来のコンパイ解析（例えばドミネータ及びポストドミネータやループ入れ子(loop nesting)）をサポートするために、ＤＢＲ１３０はまた、全ての基本ブロックが開始基本ブロックから到達可能であることを確実にし且つ全ての基本ブロックが末尾基本ブロックに到達することができるのを確実にするために必要なエントリエッジ及びエグジットエッジを追加する。
【００７１】
より具体的には、コード区分化関数が先ず接続要素分離関数(SEPARATE-CONNECTED-COMPONENTS function)を呼び出し、この関数は、先行する及び後続の制御フローエッジの両方をシード基本ブロックからウォークすることによって各接続要素（ＣＣ）を識別し、エントリ制御フローエッジ及びエグジット制御フローエッジは無視する。各接続要素はそれ自身の超領域へと移動させられ、そして関連するエントリエッジ及びエグジットエッジが当該超領域の開始基本ブロック及び末尾基本ブロックに接続される。
【００７２】
次いでターミナル接続関数(CONNECT-TERMINALS function)が各超領域で呼び出される。この関数は先ず超領域の強く接続された要素（ＳＣＣ）を計算する。これらは最大のサブグラフであり、その内部では全ての基本ブロックが他の全ての基本ブロックから到達可能である。開始／末尾基本ブロックは、これらの基本ブロックは先行する／後続の制御フローエッジを有していないので他の基本ブロックを伴うサイクル内にはなくてよいという理由で、それら自身の強く接続された要素内に常にある。強く接続された要素は最大であるから、強く接続された要素間の制御フローはサイクルを形成し得ない。従って、別の強く接続された要素からの制御フローエッジを有していない強く接続された要素（開始／末尾の強く接続された要素を除く）のみが、他の全ての強く接続された要素はそれらから到達可能であるという理由で、開始基本ブロックに接続されることを必要としている（それら内の任意の基本ブロックは、それらがサイクルを形成するから、そうすることになる）。同様に、エグジットエッジは、別の強く接続された要素への制御フローエッジを有していない強く接続された要素に加えられることを必要とするのみである（この場合にも、任意の基本ブロックはそうすることになる）。エントリエッジ及びエグジットエッジの事前の存在は、追加的なそれらを加える必要性を未然に防ぐことになる。エグジットエッジを追加することは、クライアントコードが無限ループを実際に有している場合に追加されることをそれが必要とするだけであるから、稀である。
【００７３】
制御転送命令のみが、制御フローエッジサンプルカウントをセットするために用いられ得るＨＰＭサンプル情報を提供する。非制御転送命令を伴って終了する任意の基本ブロックは、サンプルカウントを有していない通り抜けのみ制御フローエッジを有することになる。通り抜けのみ計算関数(COMPUTE-FALL-THROUGH-ONLY function)は、これらのカウントのための近似を計算する。この関数は、通り抜けのみ制御フローエッジのみを含む最大のパスからなる通り抜けのみチェインを先ず作成する。重複しているコードが、同じ基本ブロックへ通り抜けることを多重の基本ブロックにさせる場合、１つを任意に選択し、そして他を無視する。より大きなアドレスを伴う命令へ通り抜けることのみが可能であるから、サイクルはないであろう。
【００７４】
先行するものとして開始基本ブロックを有していない全てのチェインに対して、通り抜けのみ計算関数は、先行する制御フローエッジカウントを加算すると共に非通り抜けの後続の制御フローエッジカウントを減算することによって後続の通り抜け制御フローエッジカウントを推定しながら、前方へ走査する。最大のチェインの頂点で開始することによって、通り抜けのみ計算関数は、任意の通り抜けの先行するものが、計算されたそのサンプルカウントを、それを使用する前に有したはずであることを決定するように機能する。
【００７５】
通り抜けのみ計算関数は疑似エントリエッジのためのサンプルカウントを有していないので、これらと共に開始するチェインは前方へ走査されることができない。その代わりに通り抜けのみ計算関数は、後続の制御フローエッジカウントを加算すると共に非通り抜けの先行する制御フローエッジカウントを減算することによって先行する通り抜け制御フローエッジカウントを推定しながら、これらのチェインを後方へ走査する。この場合にも、後続の通り抜けカウントはそれらが使われる前に計算される。エントリエッジ及びエグジットエッジの両方を有するチェインは異なっており、そして通り抜けのみ計算関数は単純に疑似制御フローエッジが０のカウントを有しているものとみなす。
【００７６】
インラインホット呼び出し関数は、呼び出し基本ブロックを呼び出しの目標である基本ブロックのクローン(clone)に接続する。クローン化は関連する呼び出し目標基本ブロックで開始し、そして戻り基本ブロックに至るまで制御フローを辿り、戻り基本ブロックは次いでオリジナル呼び出し基本ブロックの後続のものに接続される。超領域はホットコードのみを含むので、インライナはホットパスの部分的なインライン化を実際には実行している。呼び出されたルーチン内の任意の既存のエッジは、クローン化された基本ブロック内のエグジットエッジになる。
【００７７】
インラインホット呼び出し関数は、オリジナル呼び出し及びインライン化された戻り命令を、インライン化された呼び出し戻りアドレス変形によって後で拡張される疑似命令と交換する。この動作は呼び出し方法の最適化を可能にする。最悪のケースでは、リアル戻り命令を実行するクライアントコードに既存のエッジが戻る場合に、インライン化された呼び出し戻りアドレス変形は、オリジナルクライアントアドレスをスタックに積み上げてしまう。インライン化された呼び出し戻りアドレス変形が戻りアドレスを積み上げることを回避し得るとしても（既存のエッジがないことを理由として）、クローン化された基本ブロック内の全てのスタックアクセスオフセットを、インライン化された呼び出し戻りアドレス変形が適切に変化させ得る場合を除き、インライン化された呼び出し戻りアドレス変形は、スタック上にアドレスのための空白を残しておく必要が依然としてあるであろう。
【００７８】
クローン化された基本ブロックは、実際には特定の呼び出しサイトに対するオリジナルルーチンの特殊化である。従って、その特定のサイトから呼び出された場合にコードがルーチンを実際に実行していたとしたならば、クライアントコードがそれらに直接エンターすることのみが正当であろう。パッチ点は呼び出しコンテクストに関して不可知であり、また置換コード内の単一の宛先へ行くことができるのみであるから、最も安全なことはインライン化された基本ブロックをパッチしないことである。このことは、インライン化された全ての基本ブロックをパッチ不能として標識付けることによって達成される。尚、インライン化することは、オリジナルルーチン基本ブロックを削除しない。従って、パッチ点を有するルーチンの置換コードバージョンが生成され、そしてそれは、インライン化されたクローンが存在する場合にエンターすることができるこの特殊化されたバージョンである。
【００７９】
間接呼び出しに対しては、ホットコード発見は、既知の目標に対して多重の制御フローを作成する。インラインホット呼び出し関数はこれらの各々をインライン化し、そして呼び出しを疑似呼び出し宛先命令へと変換する。これは、間接制御フロー変形の一部として試験のカスケードへと変換される。
【００８０】
インラインホット呼び出し関数は、全ての超領域に対する呼び出しグラフを計算し、そして以下の要件の全てを満たす呼び出しサイトを繰り返しインライン化する。（１）呼び出し基本ブロックがホットである。インラインホット呼び出し関数は、サンプルカウントを用いてどの呼び出しがホットであり且つインライン化する価値があるのかを決定し、またインライン化されていない呼び出し（おそらくそれらがコールドパス上にあったことを理由として）を含むルーチンをインライン化することができる。（２）呼び出し基本ブロックを含むルーチンが依然として割当量上の経験則(budget heuristic)内にあること。インラインホット呼び出し関数は、それが実行中のコード拡張の量をモニタリングして、そしてコードローカリティの利益に悪影響を及ぼし得る又は共有メモリをオーバフローするであろう過剰なコード激増を回避する。個々のルーチンに対してそれら自身の別個の超領域内にコードを有することはこれを容易にし、各超領域はそれ自身の割当量を有している。（３）呼び出し目標基本ブロックが既知である（これは間接呼び出しの未知の目標ではない）。（４）呼び出し目標基本ブロックから少なくとも１つの戻り基本ブロックまでのパスがある。もしインラインホット呼び出し関数がクローン化された基本ブロックを呼び出し側に接続できてＤＢＲ１３０が完全な手順間ループを発見できるとすれば、唯一の価値あるインライン化である。多重エントリを伴うルーチンはサポートされ、そして各呼び出し目標基本ブロックはそれ自身の戻り基本ブロックのセットを有し得る。（５）呼び出されたルーチンはホット呼び出しサイトを有していない。呼び出しサイトを上流葉(leaves upwards)から処理することは、ルーチンがそれ自身上でインライン化を既に実行させた後にのみルーチンがインライン化されることを確実にする。また、このことは、呼び出しグラフ内にサイクルを形成し従って葉ではあり得ない再帰的ルーチンをインライン化すること（場合によっては相補的な）を回避する。
【００８１】
インラインホット呼び出し関数は、クローン化された基本ブロック及び制御フローエッジ上のカウントを呼び出し上のカウントと無矛盾であるようにスケーリングする。このことは、クローン化されたカウントがこの呼び出しサイトの実際の挙動を反映することを必ずしも結果としてもたらさないが、それは近似である。インラインホット呼び出し関数はまた、結果として生じるカウントが、それらがもはやこの呼び出しサイトによっては実行されないという事実を反映するように、クローン化されたカウントをオリジナル基本ブロック及び制御フローエッジから減じる。
【００８２】
プッシュされた戻りアドレスが置換コード内にあるであろうから、クライアント処理は置換コード内の呼び出し命令を実行してはならない。置換コード内で戻りアドレスをプッシュすることは２つの問題を有し、即ちハンドラを選択するときに戻りアドレスを検査する例外メカニズムをクライアントプログラムが使用しているであろうことと、置換コードはパッチ不能であろうからプッシュされた戻りアドレスの全てを見つけ且つ更新することが困難であろうことである。これを回避するために、インラインホット呼び出し関数は、インライン化されていない任意の呼び出し基本ブロックを削除する。呼び出し基本ブロックの先行する制御フローエッジは、それらを末尾基本ブロックに接続することによってエグジットエッジにされている。インラインホット呼び出し関数はターミナル接続関数を呼び出して、任意の必要なエントリ制御フローエッジを、呼び出し基本ブロック先行基本ブロックに加える。これにより、超領域が多重の接続要素を有することが可能になるが、このことはコード刈り込み関数(PRUNE-CODE function)により実行される区分化によって処理される。
【００８３】
図１２はパッチ点選択動作の疑似コード表現を示している。特定の種類の処理アーキテクチャのアーキテクチャ上の制約に起因して、クライアントコード内の全ての命令がパッチすることに適しているわけではないであろう。例えばｘ８６プロセッサアーキテクチャにおいては、１バイトオプコードとそれに続く４バイトオフセットからなる５バイト分岐命令が置換コードへの転送に用いられる。従って、５バイトより大きいクライアント命令のみがパッチされ得る。より小さい命令をパッチすることは２つ以上の命令を上書きすることを可能にし、即ちそれらの後続の命令の１つが分岐の目標であったとしたら、パッチはプログラムを破損するであろう。
【００８４】
更なる困難性は、多重プロセッサアーキテクチャ上で別のプロセッサによって同時に実行されているであろうコードを安全に修正する能力である。この問題は管理されたコードシステム（例えばJava（登録商標）仮想マシン）でも遭遇することがあり、また解決法が利用可能ではあるが、それらはパッチされ得るクライアント命令に対して付加的な制約を課し得る。ＡＭＤｘ８６プロセッサのための解決法は以下の通りである。（１）アラインされた８バイト境界をバイトが走査しない場合には、まさにそれらを書き込む。そうでない場合には、（２）２バイトの自己分岐命令を最初の２バイトに書き込む。自動的に、書き込みはアラインされた８バイト境界を走査しないはずである。（３）全てのプロセッサが先行する書き込みより前に開始されたそれらの命令フェッチをそれらがオリジナル命令をフェッチしているであろうときに完了していることを確実にするように、待つ。（４）次の３バイト（オフセットの最後の３バイト）を書き込む。（５）分岐オプコードとオフセットの最初のバイトとで最初の２バイトを再書き込みする。以上のように、このことは付加的な制約を加え、その制約の下、クライアント命令はＡＭＤ型ｘ８６アーキテクチャ上でパッチすることができる。他のアーキテクチャは同様の制約を有するであろう。
【００８５】
ホットコードはエンターするたびに何度も実行されるループから構成されていることが注目される。ループは大きいであろうし且つ多くのルーチンにわたって走査するであろうが、それ自身による直線的コードは実行するのに時間がかかるだけであるので、ホットではあり得ない。ＤＢＲ１３０発見動作は超領域（任意の制御フローを許容する）を作成し、従って完全なループを識別することが可能である。しかし、ＤＢＲ１３０はホットコードのみを探索するので、同時に実行されるが超領域の一部ではなく且つクライアントコードへとエグジットする複数のループ内に複数のパスが存在するであろう。そのようなパスがループの早期の繰り返しにおいて実行される傾向がある場合、制御はクライアントコードへと戻ることがあり、そこで制御はホットな超領域が次にエンターするまでそのままになることになる。従って、ＤＢＲ１３０がループのホットパスを識別することに成功したとしても、ＤＢＲ１３０は全てのループ繰り返しに対して超領域内には残っていないかもしれない。この問題に対する解決法はパッチをループ本体内に置くことであり、従ってそのようなパスが取られる場合、ループは次の繰り返しにおいて再エンターすることになる。そのようなパッチをループ内に加えることはまた、変形を制限する傾向があるかもしれない。
【００８６】
最後に、２つの他の制限がある。第一に、幾つかの基本ブロックはパッチされるべきではない（即ちインライナによってクローン化されたもの及びパッチ不能標識付け値によって識別されたもの）。第二にパッチを実装するコストはしばしば比較的高くなる（ページ保護を変更すると共にキャッシュをフラッシュするためのシステム呼び出しを必要とする）ので、ＤＢＲ１３０は各超領域内でパッチの数を最小化することが望ましい。
【００８７】
パッチ点選択関数(PATCH-POINT-SELECTION function)は、パッチされ得る命令で開始している基本ブロックのみを参照してエントリエッジを修正することによってこれらの挑戦に取り組むこと、及び超領域のループをカバーするパッチの最小のセットを見つけることを目指している。インライナは、完全なルーチンである超領域を多くの場合に必要とし、またパッチ化制限を負わないので、ＤＢＲ１３０はインライン化動作の後に選択を行う。
【００８８】
より具体的には、パッチ点選択関数は、ループ入れ子構造を計算することによって開始する。次いでパッチ点のセットが決定される。このことは基本ブロック粒度で行われ、パッチ可能基本ブロックの最初の命令が実際にパッチ可能であるかどうかに対して鈍感である。パッチ点選択関数は次いで、古いエントリエッジを除去し、パッチ可能な命令で開始していない任意のパッチ点基本ブロックを分割し、そしてそれらに対する新たなエントリエッジを作成する。このことは、まさにそれを必要としている基本ブロックに分割することを最小限にする。
【００８９】
概念的には、パッチ点選択関数は、パッチ可能な基本ブロックの完全なセットを決定し、次いでそのセット内の幾つかの他の基本ブロックから到達可能な任意の基本ブロックを除去することによって（両方を有する必要性はない）、このセットを最小化する。パッチ点選択関数は、ドミネータ関係(dominator relationship)を用いて到達可能性を決定することができる。しかし、ループに対しては、パッチ点選択関数は、同じループをポストドミネートするそのループ内の任意の基本ブロックに制御フローが到達し得ることをループの戻りエッジが確実にするという理由で、ポストドミネータ関係を用いることもできる。内側ループへパッチ化することはループに対する変形潜在性を限定することがあるので、外側ループ内で基本ブロックをパッチ化することが望ましい。これを達成するために、パッチ点選択関数は、最外側ループで開始するループ階層を処理する。
【００９０】
ループ階層のルートループ(root loop)は実際にはループではないが、入れ子ループを含むプレースホルダ(placeholder)である。これは、表されるべきループのシリーズをもたらすシーケンシャルコードで開始する超領域を可能にする。この理由で、パッチ点選択関数は、処理の間に２セットのパッチを維持しており、即ちループ内にないルートパッチと、ループ内にあるループパッチとである。ルートパッチと比較する場合には、ポストドミネータ関係は用いられない。
【００９１】
単一ループに対するパッチ基本ブロックのセットを識別するために、パッチ関数(PATCHES function)が用いられる。この関数は先ず、ループの本体に対する候補基本ブロックのセットを決定する。基本ブロックは、その基本ブロックがパッチ可能であり且つ既存のルートパッチ又はループパッチの１つから到達可能でない場合に、候補である。この関数は次いで、各メンバを各他のメンバと対比較し一方が他方から到達可能な場合に一方を除去することによって、この候補セットを最小化する。ループの基本ブロックを縦型検索(depth-first search)（ＤＦＳ）順で処理することによって、パッチ点選択関数は、相互に到達可能なループ内の２つの基本ブロックの早い方を選択する。このことは、いずれでも十分であるがより直感的な選択であるから、厳密には必要ではない。到達可能性はスーパーシード関数(SUPERCEDE function)によって決定され、この関数はドミネータ関係及びポストドミネータ関係を適切に用いる。
【００９２】
入れ子パッチ関数(NESTED-PATCHES function)は、ループをその入れ子ループトップダウンと共に処理するために用いられる。この関数は、当該ループ本体の基本ブロックをその子ループを調べるために再帰させる前に検査する。選択された任意のパッチは、任意の先行するループパッチとユニオン化されていないので、他の入れ子ループの候補に取って代わる(supercede)ように作用し得る。入れ子パッチ関数は、早いループが優遇されるようにＤＦＳ順で入れ子ループを処理する。遅い方の入れ子ループが早い方の入れ子ループに取って代わってもよいが、ＤＢＲ１３０はそれでもなお、到達不能ループ包囲の最初の繰り返しに置換コードがエンターされるように、早い方のパッチを有するであろう。
【００９３】
パッチ点選択関数は、入れ子パッチ関数がルートループに対してするのと同じような機能を本質的には実行する。この関数はパッチ関数をルートループに対して用いるが、ドミネータ関係のみを用いるように指定し、そして結果をルートパッチ内に置く。それは次いで入れ子パッチ関数をその入れ子にされた子の各々に対して用いる。しかし、ルートループはループではないから、この関数は任意の子ループパッチをルートパッチへ加える。
【００９４】
パッチ点動作は外側ループにパッチすることを目指しており、変形の利益になる。早期の繰り返しにおいて内側ループがエグジットエッジを辿る傾向がある場合、置換コードをインストールした後にもまだ入れ子ループはホットであろう。ホットコード発見は過去に既にインストールされたパッチは探索しないので、動作は入れ子ループをまさに発見する傾向にあり、入れ子ループは独立して変形されることになる。この一般的手法は修正（例えばループが任意のエグジットエッジを有しているかどうかを調べるために解析すること及びループを最内側から外に向かって処理することによる修正）の影響を受け易い。
【００９５】
ＤＢＲ１３０領域選択の最後のステップでは、コード刈り込み関数が、発見されなかったコードを刈り込む。１つの目標は、変形からの利益を得ることになるホットコードの超領域で終了することである。コード刈り込み関数は、パッチ点選択関数がエントリエッジを変更したときに生じた任意の到達不能基本ブロックを除去する。
【００９６】
コード刈り込み関数はまた、ホット基本ブロックには到達することができないが超領域から単にエグジットすることはできる任意のコールド末尾基本ブロックを刈り込む。これらは多くの場合、ホットコード発見のホット起点ジャンプ数調整メカニズムの結果である。それらはホットではなく、また常にクライアントコードへと戻し転送されるので、超領域内にそれらを含ませておく利益はなく、その代わりに置換コードが単純に早めにクライアントコードへと戻し転送されてしまうであろう。これらの基本ブロックを含ませておくことは、単により多くの動作をワーカースレッドにもたらし、また、このコードはコールドコードバッファ内に置かれることになるので、必要とされる追加的なジャンプをもたらし得る。それらは、全てのコールド基本ブロックをコールドセット内に置き且つ全てのホット基本ブロックをワークリスト上に置くことによって識別される。ワークリストの基本ブロックはそれらの全ての先行するものを検査することによって処理され、そしてコールドセット内のものはそれらがホット基本ブロックに到達することが可能であることを理由にワークリストへと加えられる。コールドセット内に残っている基本ブロックは削除されるが、それらの任意の先行する制御フローエッジであって、コールドセット内でない基本ブロックからの制御フローエッジは、エグジットエッジへと変更され、そして末尾基本ブロックに接続される。
【００９７】
接続要素分離関数を呼び出すこともまた、インライナ、パッチ点選択、及びコールド末尾基本ブロック除去によってなされた制御フロー変更に起因して、有益である。このことは、各超領域が単一接続要素のみを再び含むことを確実にし、従って後続の刈り込み作用によって個別に検査される。
【００９８】
多重の繰り返しを実行するループを含まない超領域は、パッチジャンプ及び戻りジャンプのコストがおそらくは任意の変形利益を上回るであろうから、変形からの利益を受けそうにない。ＤＢＲ１３０はループ入れ子を調べると共に制御フローエッジカウントを用いて、ループが繰り返される平均回数を見積もる。スレッショルドを超えるループを全く伴わない超領域は削除される（これは全くループを含まない超領域を含む）。最後にＤＢＲ１３０はまた、極めて小さい超領域を、改善され得るのに十分なコードをこれらの超領域が有しそうにないという理由で、削除する。
【００９９】
本発明は、言及されている利点の他そこにおける他の固有のものを達成するのに十分に適合させられている。本発明は、本発明の特定の実施形態を参照して描かれ、説明され、そして定義されてきたが、そのような参照は本発明での限定を暗示しておらず、そしてそのような限定は推測されるべきではない。本発明は、当業者において生じるであろうように、形態及び機能において多くの修正、変更、及び均等なものが可能である。描かれそして説明された実施形態は単に例であり、従って本発明の範囲を網羅するものではない。
【０１００】
例えば、他のプロセッサアーキテクチャ及びＨＰＭ実装が検討されていることが理解されるであろう。
【０１０１】
また例えば、上で論じられた実施形態は特定のタスクを行うソフトウエアモジュールを含む。ここで論じられるソフトウエアは、スクリプト、バッチ、又は他の実行可能なファイルを含んでいてよい。ソフトウエアモジュールは、機械可読な又はコンピュータ可読な記憶媒体、例えばディスクドライブに記憶されていてよい。本発明の実施形態に従うソフトウエアモジュールを記憶するために用いられる記憶デバイスは、例えば、磁気フロッピー（登録商標）ディスク、ハードディスク、又はＣＤ−ＲＯＭ若しくはＣＤ−Ｒ等の光ディスクであってよい。本発明の実施形態に従うファームウエア又はハードウエアモジュールを記憶するために用いられる記憶デバイスはまた、マイクロプロセッサ／メモリシステムに恒久的に、取り外し可能に、又は遠隔的に結合され得る半導体ベースのメモリを含んでいてよい。従ってモジュールは、コンピュータシステムを構成してモジュールの機能を実行するためにコンピュータシステム内に記憶されていてよい。ここで論じられるモジュールを記憶するために、他の新規なそして様々な種類のコンピュータ可読記憶媒体が用いられてよい。また、当業者であれば、複数のモジュールへの機能の分離が例示目的のためであることを認識するであろう。代替的な実施形態は、多重モジュールの機能を単一モジュール内へ併合してよいし、あるいは複数のモジュールの機能の代替的な分解を課してよい。例えば、サブモジュールを呼び出すためのソフトウエアモジュールは、各サブモジュールがその機能を実行すると共に制御を直接的に別のサブモジュールへ渡すように、分解されてよい。
【０１０２】
従って、本発明は、あらゆる点において均等なものの完全な認識を与える添付の特許請求の範囲の精神及び範囲によってのみ限定されることが意図されている。
【図１】
2013504124.tif 000003
【図２】
2013504124.tif 000004
【図３】
2013504124.tif 000005
【図４】
2013504124.tif 000006
【図５】
2013504124.tif 000007
【図６】
2013504124.tif 000008
【図７】
2013504124.tif 000009
【図８】
2013504124.tif 000010
【図９】
2013504124.tif 000011
【図１０】
2013504124.tif 000012
【図１１】
2013504124.tif 000013
【図１２】
2013504124.tif 000014
【国際調査報告】
2013504124.tif 000015
2013504124.tif 000016