(57)【特許請求の範囲】
【請求項１】
コンピュータが、
トランスレータの第１のインスタンスを使用して、対象コードの第１部分をターゲット・コードの部分に変換するステップと、
前記ターゲット・コードの前記部分を共有コード・キャッシュ内にキャッシングするステップであって、前記コンピュータが前記ターゲット・コードの部分をキャッシュするために共有コード・キャッシュを備えている、前記キャッシングするステップと、
前記トランスレータの第２のインスタンスを使用して、前記対象コードの第２部分をターゲット・コードに変換するステップであって、前記ターゲット・コードの前記キャッシングされた部分と前記対象コードの前記第２部分との間の互換性検出時にターゲット・コードの前記キャッシングされた部分を取り出すことを含み、前記共用コード・キャッシュは、前記第１のインスタンスで変換されたターゲット・コードを前記第２のインスタンスで再利用することを可能にし、前記互換性がないことに応じて、前記対象コードの前記第２の部分が前記ターゲット・コードに変換され、一方、前記互換性があることに応じて、前記ターゲット・コードの前記キャッシングされた部分が実行される、前記変換するステップと
を実行することを含み、
前記互換性検出が、前記対象コードの前記第１部分に関連付けられたキャッシュ・キーと前記対象コードの前記第２部分に関連付けられたキャッシュ・キーとの比較によって判定され、
前記キャッシュ・キーが、（１）前記対象コードを含む実行可能ファイルのファイル名、（２）前記対象コードの前記第１の部分及び前記第２の部分それぞれの対象コード・シーケンス命令の位置、（３）前記実行可能ファイルの最終変更時刻、（４）前記トランスレータの前記第１及び前記第２それぞれのインスタンスのバージョン番号、並びに（５）前記対象コード・シーケンス命令がロードされた対象メモリ・アドレス、
である、前記方法。
【請求項２】
コンピュータが、
トランスレータの第１のインスタンスを用意するステップであって、前記第１のインスタンスは対象コードの第１部分をターゲット・コードの部分に変換する、前記用意するステップと、
前記ターゲット・コードの前記部分を前記共有コード・キャッシュ内にキャッシングするステップであって、前記コンピュータが前記ターゲット・コードの部分をキャッシュするために共有コード・キャッシュを備えている、前記キャッシングするステップと、
前記トランスレータの第２のインスタンスを用意するステップであって、前記第２のインスタンスは前記対象コードの第２部分をターゲット・コードに変換し、前記対象コードの前記第２部分を前記ターゲット・コードに前記変換することは、前記ターゲット・コードの前記キャッシングされた部分と前記対象コードの前記第２部分との間の互換性検出時にターゲット・コードの前記キャッシングされた部分を取り出すことを含み、前記共用コード・キャッシュは、前記第１のインスタンスで変換されたターゲット・コードを前記第２のインスタンスで再利用することを可能にし、前記互換性がないことに応じて、前記対象コードの前記第２の部分が前記ターゲット・コードに変換され、一方、前記互換性があることに応じて、前記ターゲット・コードの前記キャッシングされた部分が実行される、前記用意するステップと
を実行することを含み、
前記互換性検出が、前記対象コードの前記第１部分に関連付けられたキャッシュ・キーと前記対象コードの前記第２部分に関連付けられたキャッシュ・キーとの比較によって判定され、
前記キャッシュ・キーが、（１）前記対象コードを含む実行可能ファイルのファイル名、（２）前記対象コードの前記第１の部分及び前記第２の部分それぞれの対象コード・シーケンス命令の位置、（３）前記実行可能ファイルの最終変更時刻、（４）前記トランスレータの前記第１及び前記第２それぞれのインスタンスのバージョン番号、並びに（５）前記対象コード・シーケンス命令がロードされた対象メモリ・アドレス、
である、前記方法。
【請求項３】
前記コンピュータが、
前記ターゲット・コードの前記部分を共有コード・キャッシュへコピーするステップと、
前記トランスレータの前記第２のインスタンスによる使用のために、前記共有コード・キャッシュから前記ターゲット・コードの前記コピーされた部分を取り出すステップと
を実行することをさらに含む、請求項１又は２に記載の方法。
【請求項４】
前記コンピュータが、
前記トランスレータの前記第１のインスタンスによって生成されたターゲット・コードの複数の前記部分のうちから静的ターゲット・コードの１以上の部分を識別するステップであって、前記静的ターゲット・コードは静的に生成された対象コードから得られる、前記識別するステップと、
前記識別された静的ターゲットの１以上の部分をキャッシュするステップと
を実行することをさらに含む、請求項３に記載の方法。
【請求項５】
前記コンピュータが、
前記トランスレータの前記第１のインスタンスによって生成されたターゲット・コードの複数の前記部分のうちから動的ターゲット・コードの１以上の部分を識別するステップであって、前記動的ターゲット・コードは動的に生成された対象コードから得られる、前記識別するステップと、
前記識別された動的ターゲットの１以上の部分を破棄するステップと
を実行することをさらに含む、請求項４に記載の方法。
【請求項６】
前記コンピュータが、
前記共有コード・キャッシュを最適化するステップをさらに実行する、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
自己書き換えコードの変換がキャッシングされない、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
ターゲット・コードの前記キャッシングされた部分が、トランスレータの変換の基礎単位である基本ブロックを含む変換されたコードを含む、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
ターゲット・コードの前記キャッシングされた部分が、１つ以上の前記基本ブロックを含む変換されたコードおよびその各々の後継者リストを含む、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
前記対象コードの前記第１部分が第１プログラムの一部であり、前記対象コードの前記第２部分が第２プログラムの一部である、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
前記ターゲット・コードの前記部分が、前記第１プログラムの変換の終わりにキャッシングされる、請求項１０に記載の方法。
【請求項１２】
前記ターゲット・コードを実行するステップをさらに含む、請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
ターゲット・プロセッサと前記ターゲット・プロセッサに接続されたメモリを有するコンピュータであって、前記ターゲット・プロセッサが、
トランスレータの第１のインスタンスを使用して、対象コードの第１部分をターゲット・コードの部分に変換すること、
前記ターゲット・コードの前記部分を共有コード・キャッシュ内にキャッシングすること、ここで、前記コンピュータが前記ターゲット・コードの部分をキャッシュするために共有コード・キャッシュを備えており、
前記トランスレータの第２のインスタンスを使用して、前記対象コードの第２部分をターゲット・コードに変換することであって、前記ターゲット・コードの前記キャッシングされた部分と前記対象コードの前記第２部分との間の互換性検出時にターゲット・コードの前記キャッシングされた部分を取り出すことを含み、前記共用コード・キャッシュは、前記第１のインスタンスで変換されたターゲット・コードを前記第２のインスタンスで再利用することを可能にし、前記互換性がないことに応じて、前記対象コードの前記第２の部分が前記ターゲット・コードに変換され、一方、前記互換性があることに応じて、前記ターゲット・コードの前記キャッシングされた部分が実行される、前記変換すること
を実行し、
前記互換性検出が、前記対象コードの前記第１部分に関連付けられたキャッシュ・キーと前記対象コードの前記第２部分に関連付けられたキャッシュ・キーとの比較によって判定され、
前記キャッシュ・キーが、（１）前記対象コードを含む実行可能ファイルのファイル名、（２）前記対象コードの前記第１の部分及び前記第２の部分それぞれの対象コード・シーケンス命令の位置、（３）前記実行可能ファイルの最終変更時刻、（４）前記トランスレータの前記第１及び前記第２それぞれのインスタンスのバージョン番号、並びに（５）前記対象コード・シーケンス命令がロードされた対象メモリ・アドレス、
である、前記コンピュータ。
【請求項１４】
ターゲット・プロセッサと前記ターゲット・プロセッサに接続されたメモリを有するコンピュータであって、前記ターゲット・プロセッサが、
トランスレータの第１のインスタンスを用意することであって、前記第１のインスタンスは対象コードの第１部分をターゲット・コードの部分に変換する、前記用意すること、
前記ターゲット・コードの前記部分を共有コード・キャッシュ内にキャッシングすること、ここで、前記コンピュータが前記ターゲット・コードの部分をキャッシュするために共有コード・キャッシュを備えており、
前記トランスレータの第２のインスタンスを用意することであって、前記第２のインスタンスは前記対象コードの第２部分をターゲット・コードに変換し、前記対象コードの前記第２部分を前記ターゲット・コードに前記変換することは、ターゲット・コードの前記キャッシングされた部分と前記対象コードの前記第２部分との間の互換性検出時にターゲット・コードの前記キャッシングされた部分を取り出すことを含み、前記共用コード・キャッシュは、前記第１のインスタンスで変換されたターゲット・コードを前記第２のインスタンスで再利用することを可能にし、前記互換性がないことに応じて、前記対象コードの前記第２の部分が前記ターゲット・コードに変換され、一方、前記互換性があることに応じて、前記ターゲット・コードの前記キャッシングされた部分が実行される、前記用意すること
を実行し、
前記互換性検出が、前記対象コードの前記第１部分に関連付けられたキャッシュ・キーと前記対象コードの前記第２部分に関連付けられたキャッシュ・キーとの比較によって判定され、
前記キャッシュ・キーが、（１）前記対象コードを含む実行可能ファイルのファイル名、（２）前記対象コードの前記第１の部分及び前記第２の部分それぞれの対象コード・シーケンス命令の位置、（３）前記実行可能ファイルの最終変更時刻、（４）前記トランスレータの前記第１及び前記第２それぞれのインスタンスのバージョン番号、並びに（５）前記対象コード・シーケンス命令がロードされた対象メモリ・アドレス、
である、前記コンピュータ。
【請求項１５】
対象プログラム・コードをターゲット・コードに変換するトランスレータ・コードを保管するプログラム記憶媒体であって、コンピュータに、請求項１〜１２のいずれか一項に記載の方法の各ステップを実行させる前記トランスレータ・コードを保管するプログラム記憶媒体。
【請求項１６】
対象プログラム・コードをターゲット・コードに変換するトランスレータ・コードであって、コンピュータに、請求項１〜１２のいずれか一項に記載の方法の各ステップを実行させる前記トランスレータ・コード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にはコンピュータおよびコンピュータ・ソフトウェアの分野に関し、具体的には、たとえばコード・トランスレータ（以下、変換器ともいう）（ｃｏｄｅ  ｔｒａｎｓｌａｔｏｒ）、エミュレータ、およびアクセラレータで有用な、プログラム・コード変換の方法および装置に関する。
【背景技術】
【０００２】
組込みＣＰＵおよび非組込みＣＰＵの両方で、動作を「加速」できるか、ユーザが気付かずに関連するソフトウェアにアクセスすることが可能な、よりよい費用対効果を示すことができる多数のプロセッサに「変換」され得る多数のソフトウェアを含む、有力な命令セット・アーキテクチャ（ＩＳＡ）がある。そのＩＳＡにロックされ、性能またはマーケット・リーチ（ｍａｒｋｅｔ  ｒｅａｃｈ）において進化することが不可能な有力なＣＰＵアーキテクチャもある。そのようなアーキテクチャは、「Ｓｙｎｔｈｅｔｉｃ  ＣＰＵ」コアーキテクチャから利益を得るはずである。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
プログラム・コード変換の方法および装置は、そのような加速機能、変換機能、およびコアーキテクチャ機能を容易にし、たとえば、ＷＯ  ００／２２５２１、名称「プログラム・コード変換（Ｐｒｏｇｒａｍ  Ｃｏｄｅ  Ｃｏｎｖｅｒｓｉｏｎ）」で処理される。
【課題を解決するための手段】
【０００４】
本発明によって、添付請求項に示された装置および方法が提供される。本発明の好ましい特徴は、従属請求項および下記の説明から明白になる。
次に、本発明による種々の実施形態に従って実現可能な種々の態様および利益を要約する。これは、当業者が後に続く詳細な設計議論を迅速に理解するのを容易にするための概論として提供され、いかなる形でも添付された請求項の範囲を制限することを意図していない。
【０００５】
これを理解した上で、本発明人は、以下で特に、対象プログラム・コードのターゲット・コードへの変換に使用するランタイム・変換器に関連して有用である、プログラム・コード変換を促進する技法を開示する。具体的には、再利用のために対象コード変換を保管する共用コード・キャッシュ機構を提供する。一実施形態で、ある変換器インスタンスによって生成される対象コードは、後続の変換器インスタンスによる再利用のためにキャッシングされる。そのような機構の種々の他の実装、実施形態、および機能強化をさらに提供する。
【０００６】
添付図面は好ましい実施形態を示すものであり、本明細書に援用されその一部を構成する。
【発明を実施するための最良の形態】
【０００７】
図１から８は、以下で、プログラム・コード変換に有用な方法、装置、およびプログラム・コードを示す。図９に、たとえば図１〜８に示されたものなどのプログラム・コード変換システムに有用な、共用コード・キャッシング技法の種々の態様を示す。
【０００８】
図１に、複数のソフトウェア・コンポーネント１９、２０、および２１を保管し、基本ブロック・キャッシュ２３、グローバル・レジスタ・ストア２７、および変換される対象コード１７を含む作業ストレージを提供するメモリと共に、ターゲット・レジスタ１５を含むターゲット・プロセッサ１３を示す。ソフトウェア・コンポーネントに、動作システム２０、変換器コード１９、および変換されたコード２１が含まれる。変換器コード１９は、たとえば、あるＩＳＡの対象コードを別のＩＳＡの変換されたコードに変換するエミュレータとして、またはそれぞれが同一ＩＳＡの対象コードを変換されたコードに変換するアクセラレータとして機能することが可能である。
【０００９】
変換器１９すなわち、変換器を実装したソース・コードのコンパイルされたバージョンおよび変換されたコード２１すなわち、変換器１９によって作られた対象コード１７の変換は、たとえば通常はマイクロプロセッサまたは他の適当なコンピュータであるターゲット・プロセッサ１３で動作するＵＮＩＸ（登録商標）など、オペレーティング・システム２０と共に動作する。図１に示された構造が、例示にすぎないことと、たとえば、本発明によるソフトウェア、方法、および工程を、オペレーティング・システムの中またはその下に常駐するコードで実装することが可能であることを諒解されたい。対象コード、変換器コード、オペレーティング・システム、およびストレージ機構は、当業者に既知のように、種々のタイプのうちののいずれかとすることができる。
【００１０】
図１による装置では、プログラム・コード変換が、ランタイムに、変換されたコード２１が動作している間に動的に実行されることが好ましい。変換器１９は、変換されたプログラム２１とインラインで動作する。変換工程の実行パスは、対象コード１７のブロックを変換されたコード２１に変換する変換器コード１９を実行するステップと、その後、その変換されたコードのブロックを実行するステップと、を含む制御ループであり、変換されたコードの各ブロックの終りに、変換器コード１９に制御を返す命令が含まれる。言い換えると、変換のステップおよびその後の対象コードを実行するステップが組み合わされ、対象プログラム１７の一部だけがある時に変換され、第１基本ブロックの変換されたコードが、後続基本ブロックの変換の前に実行される。変換器の変換の基礎単位は基本ブロックであり、これは、変換器１９が、一時に１ブロックずつ対象コード１７を変換することを意味する。基本ブロックは、正確に１つの入口点および正確に１つの出口点を有するコードのセクションと形式的に定義され、これによって、ブロック・コードが単一制御パスに制限される。この理由から、基本ブロックは、制御フローの基礎単位である。
【００１１】
変換されたコード２１を生成する工程で、中間表現（「ＩＲ」）ツリーが、対象命令シーケンスに基づいて生成される。ＩＲツリーは、対象プログラムによって計算される式および対象プログラムによって実行される動作の抽象表現である。その後に、変換されたコード２１が、ＩＲツリーに基づいて生成される。
【００１２】
本明細書に記載のＩＲノードの集合を口語表現で「ツリー」と称する。形式的には、そのような構造は実際にはツリーではなく有向非巡回グラフ（ＤＡＧ）であることに留意されたい。ツリーの形式的な定義は、各ノードが少なくとも１つの親を有することを必要とする。本明細書に記載の実施形態では、ＩＲ生成中に共通部分式消去を使用するので、ノードはしばしば複数の親を有する。たとえば、フラグに影響する命令の結果のＩＲが、宛先対象レジスタおよびフラグ結果パラメータに対応する２つの抽象レジスタによって参照される場合がある。
【００１３】
たとえば、対象命令「ａｄｄ  ％ｒ１，％ｒ２，％ｒ３」は、対象レジスタ％ｒ２および％ｒ３の内容の加算を実行し、結果を対象レジスタ％ｒ１に保管する。したがって、この命令は、抽象式「％ｒ１＝％ｒ２＋％ｒ３」に対応する。この例に、命令オペランド％ｒ２および％ｒ３を表す２つの部分式を含む加算式を伴う抽象レジスタ％ｒ１の定義が含まれる。対象プログラム１７の文脈で、これらの部分式は、他の以前の対象命令に対応することが可能であり、あるいは、即値定数値などの現在の命令の詳細を表す場合がある。
【００１４】
「ａｄｄ」命令が解析される時に、加算の抽象算術演算子に対応する新しい「＋」ＩＲノードが生成される。「＋」ＩＲノードは、オペランド（ＩＲ内で部分式ツリーとして表され、しばしば対象レジスタに保持される）を表す他のＩＲノードへの参照を保管する。「＋」ノード自体は、それが値を定義する対象レジスタ（％ｒ１の抽象レジスタ、命令の宛先レジスタ）によって参照される。たとえば、図２０の中央右部分に、Ｘ８６命令「ａｄｄ  ％ｅｃｘ，％ｅｄｘ」に対応するＩＲツリーを示す。
【００１５】
当業者が諒解するように、１実施形態で、変換器１９は、Ｃ＋＋などのオブジェクト指向プログラミング言語を使用して実装される。たとえば、ＩＲノードは、Ｃ＋＋オブジェクトとして実装され、他のノードへの参照は、これらの他のノードに対応するＣ＋＋オブジェクトへのＣ＋＋参照として実装される。したがって、ＩＲツリーは、お互いへの種々の参照を含むＩＲノード・オブジェクトの集合として実装される。
【００１６】
さらに、議論している実施形態では、ＩＲ生成が、抽象レジスタの組を使用する。これらの抽象レジスタは、対象アーキテクチャの特定の特徴に対応する。たとえば、対象アーキテクチャの物理レジスタ（「対象レジスタ」）ごとに独自の抽象レジスタがある。同様に、対象アーキテクチャに存在する条件コード・フラグごとに独自の抽象レジスタがある。抽象レジスタは、ＩＲ生成中にＩＲツリーのプレースホルダとして働く。たとえば、対象命令シーケンス内の所与の点での対象レジスタ％ｒ２の値は、対象レジスタ％ｒ２の抽象レジスタに関連する特定のＩＲ式ツリーによって表される。１実施形態で、抽象レジスタは、特定のＩＲツリーのルート・ノード・オブジェクトへのＣ＋＋参照を介してそのツリーに関連するＣ＋＋オブジェクトとして実装される。
【００１７】
上で説明した例の命令ストリームでは、変換器が、「ａｄｄ」命令に先立つ対象命令を解析しながら、既に％ｒ２および％ｒ３の値に対応するＩＲツリーを生成済みである。言い換えると、％ｒ２および％ｒ３の値を計算する部分式が、既にＩＲツリーとして表されている。「ａｄｄ  ％ｒ１，％ｒ２，％ｒ３」命令のＩＲツリーを生成する時に、新しい「＋」ノードに、％ｒ２および％ｒ３のＩＲサブツリーへの参照が含まれる。
【００１８】
抽象レジスタの実行は、変換器コード１９および変換されたコード２１の両方のコンポーネントの間で分割される。変換器１９内で、「抽象レジスタ」は、ＩＲ生成の過程で使用されるプレースホルダであり、抽象レジスタは、特定の抽象レジスタが対応する対象レジスタの値を計算するＩＲツリーに関連する。したがって、変換器内の抽象レジスタは、ＩＲノード・オブジェクト（すなわち、ＩＲツリー）への参照を含むＣ＋＋オブジェクトとして実行することが可能である。抽象レジスタ・セットによって参照されるすべてのＩＲツリーの集合を、作業ＩＲフォレストと称する（「フォレスト」なのは、それぞれが１つのＩＲツリーを参照する複数の抽象レジスタ・ルートを含むからである）。作業ＩＲフォレストは、対象コード内の特定の点での対象プログラムの抽象動作のスナップショットを表す。
【００１９】
変換されたコード２１内で、「抽象レジスタ」は、それとの間で対象レジスタ値が実際のターゲット・レジスタと同期化される、グローバル・レジスタ・ストア内の特定の位置である。その代わりに、値がグローバル・レジスタ・ストアからロード済みである時に、変換されたコード２１内の抽象レジスタを、レジスタ・ストアに保存される前に、変換されたコード２１の実行中に対象レジスタ値を一時的に保持するターゲット・レジスタ１５と理解することができる。
【００２０】
上で説明したプログラム変換の例を、図２に示す。図２には、ｘ８６命令の２つの基本ブロックの変換と、変換の工程で生成される対応するＩＲツリーが示されている。図２の左側は、変換中の変換器１９の実行パスを示す。ステップ１５１で、変換器１９は、対象コードの第１の基本ブロック１５３をターゲット・コード２１に変換し、その後、ステップ１５５で、そのターゲット・コード２１を実行する。ターゲット・コード２１が実行を終了した時に、ステップ１５７で、制御が変換器１９に返され、変換器は、対象コード１７の次の基本ブロック１５９をターゲット・コード２１に変換し、ステップ１６１でそのターゲット・コード２１を実行し、以下同様である。
【００２１】
対象コードの第１の基本ブロック１５３をターゲット・コードに変換する過程で、変換器１９は、その基本ブロック１５３に基づいてＩＲツリー１６３を生成する。この場合に、ＩＲツリー１６３は、フラグに影響する命令であるソース命令「ａｄｄ  ％ｅｃｘ，％ｅｄｘ」から生成される。ＩＲツリー１６３を生成する過程で、この命令によって次の４つの抽象レジスタが定義される：宛先抽象レジスタ％ｅｃｘ  １６７、第１のフラグに影響する命令パラメータ１６９、第２のフラグに影響する命令パラメータ１７１、およびフラグに影響する命令の結果１７３。「ａｄｄ」命令に対応するＩＲツリーは、「＋」演算子１７５（すなわち、算術加算）であり、そのオペランドは、対象レジスタ％ｅｃｘ  １７７および％ｅｄｘ  １７９である。
【００２２】
したがって、第１の基本ブロック１５３のエミュレーションは、フラグに影響する命令のパラメータおよび結果を保管することによって、フラグを保留状態にする。フラグに影響する命令は、「ａｄｄ  ％ｅｃｘ，％ｅｄｘ」である。この命令のパラメータは、エミュレートされた対象レジスタ％ｅｃｘ  １７７および％ｅｄｘ  １７９の現在の値である。対象レジスタ使用１７７および１７９の前の「＠」記号は、この特定の対象レジスタが現在の基本ブロックによって前にロードされていないので、対象レジスタの値が、グローバル・レジスタ・ストアから、すなわちそれぞれ％ｅｃｘおよび％ｅｄｘに対応する位置から取り出されることを示す。これらのパラメータ値は、その後、第１および第２のフラグ・パラメータ抽象レジスタ１６９および１７１に保管される。加算演算１７５の結果は、フラグ結果抽象レジスタ１７３に保管される。
【００２３】
ＩＲツリーを生成した後に、対応するターゲット・コード２１が、そのＩＲに基づいて生成される。包括的なＩＲからターゲット・コード２１を生成する工程は、当技術分野でよく理解されている。ターゲット・コードは、フラグ結果１７３ならびにフラグ・パラメータ１６９および１７１に関するものを含む抽象レジスタをグローバル・レジスタ・ストア２７に保存するために、変換されたブロックの末尾に挿入される。ターゲット・コードを生成した後に、これを実行する、ステップ１５５。
【００２４】
図２に、組み入れられた変換および実行の例が示されている。変換器１９が、まず、第１の基本ブロック１５３の対象命令１７に基づいて変換されたコード２１を生成し、その後、基本ブロック１５３の変換されたコードが、実行される。第１の基本ブロック１５３の終りに、変換されたコード２１は制御を変換器１９に返し、変換器１９は第２の基本ブロック１５９を変換する。第２の基本ブロックの変換されたコード２１が、その後１６１で実行される。第２の基本ブロック１５９の実行の終りに、変換されたコードは制御を変換器１９に返し、変換器１９は次の基本ブロックを変換し、以下同様である。
【００２５】
したがって、変換器１９の下で動作する対象プログラムは、インターリーブされた形で実行される２つの異なるタイプのコードすなわち、変換器コード１９および変換されたコード２１を有する。変換器コード１９は、変換器１９の高水準ソース・コード実行に基づいて、ランタイムの前にコンパイラによって生成される。変換されたコード２１は、変換されるプログラムの対象コード１７に基づいて、ランタイム全体を通じて変換器コード１９によって生成される。
【００２６】
対象プロセッサ状態の表現は、同様に、変換器１９コンポーネントと変換されたコード２１コンポーネントの間で分割される。変換器１９は、変数および／またはオブジェクトなど、種々の明示的プログラミング言語デバイスに対象プロセッサ状態を保管し、変換器をコンパイルするのに使用されるコンパイラが、状態および動作をターゲット・コードでどのように実行するかを決定する。変換されたコード２１は、比べると、対象プロセッサ状態をターゲット・レジスタおよびメモリ位置に暗黙のうちに保管し、これらは、変換されたコード２１のターゲット命令によって直接に操作される。
【００２７】
たとえば、グローバル・レジスタ・ストア２７の低水準表現は、単に、割り振られたメモリの領域である。これは、変換されたコード２１が、画定されたメモリ領域と種々のターゲット・レジスタの間で保存し、復元することによって、抽象レジスタを見、これと相互作用する形である。しかし、変換器１９のソース・コードでは、グローバル・レジスタ・ストア２７が、高水準でアクセス可能であり、操作可能であるデータ配列またはオブジェクトである。変換されたコード２１に関して、単純に、高水準表現がない。
【００２８】
いくつかの場合に、静的であるか変換器１９内で静的に判定可能である対象プロセッサの状態は、動的に計算されるのではなく、変換されたコード２１に直接に符号化される。たとえば、変換器１９は、最後のフラグに影響する命令の命令タイプに特殊化された変換されたコード２１を生成することが可能であり、これは、最後のフラグに影響する命令の命令タイプが変化した場合に、変換器が、同一の基本ブロックについて異なるターゲット・コードを生成することを意味する。
【００２９】
変換器１９に、各基本ブロック変換に対応するデータ構造が含まれ、これは、後で説明するように、拡張基本ブロック、アイソブロック（ｉｓｏｂｌｏｃｋ）、グループ・ブロック、およびキャッシングされた変換状態最適化を特に容易にする。図３に、基本ブロック・データ構造３０を示すが、これには、対象アドレス３１、ターゲット・コード・ポインタ３３（すなわち、変換されたコードのターゲット・アドレス）、変換ヒント３４、入口条件（ｅｎｔｒｙ  ｃｏｎｄｉｔｉｏｎ）および出口条件（ｅｘｉｔ  ｃｏｎｄｉｔｉｏｎ）３５、プロファイリング・メトリック３７、先祖および後継者の基本ブロックのデータ構造への参照３８および３９、ならびに入口レジスタ・マップ４０が含まれる。図３に、さらに、対象アドレスによってインデクシングされる、基本ブロック・データ構造の集合、たとえば３０、４１、４２、４３、４４、…である基本ブロック・キャッシュ２３が示されている。１実施形態で、特定の変換された基本ブロックに対応するデータを、Ｃ＋＋オブジェクトに保管することが可能である。変換器は、基本ブロックが変換される時に新しい基本ブロック・オブジェクトを作成する。
【００３０】
基本ブロックの対象アドレス３１は、対象プログラム１７のメモリ空間内のその基本ブロックの先頭アドレスであり、これは、対象プログラム１７が対象アーキテクチャで実行されている場合にその基本ブロックが配置されるメモリ位置を意味する。これを、対象開始アドレスとも称する。各基本ブロックは、対象アドレスの範囲（対象命令ごとに１つ）に対応するが、対象開始アドレスは、基本ブロック内の第１の命令の対象アドレスである。
【００３１】
基本ブロックのターゲット・アドレス３３は、ターゲット・プログラム内の変換されたコード２１のメモリ位置（開始アドレス）である。ターゲット・アドレス３３を、ターゲット・コード・ポインタまたはターゲット開始アドレスとも称する。変換されたブロックを実行するために、変換器１９は、変換されたコードを呼び出す（これに制御を転送する）ために間接参照（ｄｅｒｅｆｅｒｅｎｃｅ）される関数ポインタとしてターゲット・アドレスを扱う。
【００３２】
基本ブロック・データ構造３０、４１、４２、４３、…は、基本ブロック・キャッシュ２３に保管され、この基本ブロック・キャッシュ２３は、対象アドレスによって編成された基本ブロック・オブジェクトのリポジトリである。基本ブロックの変換されたコードは、実行を終了した時に、変換器１９に制御を返し、その基本ブロックの宛先（後継者）対象アドレス３１の値も変換器に返す。後継者基本ブロックが既に変換されているかどうかを判定するために、変換器１９は、宛先対象アドレス３１を、基本ブロック・キャッシュ２３内の基本ブロックの対象アドレス３１（すなわち、既に変換されているもの）と比較する。まだ変換されていない基本ブロックは、変換され、その後、実行される。既に変換されている（かつ、下で説明する互換の入口条件を有する）基本ブロックは、単純に実行される。経時的に、出会った多数の基本ブロックが、既に変換されているようになり、これによって、増分的変換コストが減る。したがって、変換器１９は、経時的に、ますます少ないブロックが変換を必要とするので、より高速になる。
拡張基本ブロック
例示的実施形態に従って適用される最適化の１つが、「拡張基本ブロック」と称する技法によってコード生成のスコープを広げることである。基本ブロックＡが、１つの後継者ブロック（たとえば、基本ブロックＢ）だけを有する場合に、変換器が、Ｂの対象アドレスを静的に判定する（Ａが復号される時に）ことが可能である場合がある。その場合に、基本ブロックＡおよびＢは、拡張基本ブロックと称する単一のブロック（Ａ’）に組み合わされる。言い換えると、拡張基本ブロック機構は、宛先が静的に判定可能である無条件ジャンプに適用することが可能であり、ジャンプが条件ジャンプであるか、宛先を静的に反適することが不可能な場合には、別々の基本ブロックを形成しなければならない。拡張基本ブロックは、それでも形式的には基本ブロックとすることが可能である。というのは、ＡからＢへの介在するジャンプが除去された後に、ブロックＡ’のコードが、単一の制御フローだけを有し、したがって、ＡＢ境界で同期化が不要であるからである。
【００３３】
Ａが、Ｂを含む複数の可能な後継者を有する場合であっても、Ｂが実際の後継者であり、Ｂのアドレスが静的に判定可能である特定の実行について、拡張基本ブロックを使用して、ＡをＢに拡張することが可能である。
【００３４】
静的に判定可能なアドレスとは、変換器が復号時に判定可能なアドレスである。ブロックのＩＲフォレストの構成中に、ＩＲツリーが、宛先対象アドレスについて構成され、この宛先対象アドレスは、宛先アドレス抽象レジスタに関連する。宛先アドレスＩＲツリーの値が静的に判定可能である（すなわち、動的なまたはランタイムの対象レジスタ値に依存しない）場合に、後継者ブロックは、静的に判定可能である。たとえば、無条件ジャンプ命令の場合に、宛先アドレス（すなわち、後継者ブロックの対象開始アドレス）は、ジャンプ命令自体で暗示され、ジャンプ命令の対象アドレスとジャンプ命令に符号化されたオフセットの合計が、宛先アドレスと等しい。同様に、定数畳み込み（たとえば、Ｘ＋（２＋３）＝＞Ｘ＋５）および式畳み込み（たとえば、（Ｘ＊５）＊１０＝＞Ｘ＊５０）の最適化が、そうでなければ「動的」な宛先アドレスが静的に判定可能になることを引き起こす場合がある。したがって、宛先アドレスの計算は、宛先アドレスＩＲから定数値を抽出することからなる。
【００３５】
拡張基本ブロックＡ’を作成する時に、変換器は、その後、ＩＲ生成、最適化、およびコード生成を実行する時に、このＡ’を他の基本ブロックと同様に扱う。コード生成アルゴリズムが、より大きいスコープ（すなわち、組み合わされた基本ブロックＡおよびＢのコード）で動作しているので、変換器１９は、より最適なコードを生成することが可能である。
【００３６】
当業者が諒解するように、復号は、対象コードから個々の対象命令を抽出する工程である。対象コードは、未フォーマット・バイト・ストリーム（すなわち、メモリ内のバイトの集合）として保管される。可変長命令を有する対象アーキテクチャ（たとえば、Ｘ８６）の場合に、復号は、まず、命令境界の識別を必要とし、固定長命令アーキテクチャの場合に、命令境界の識別は自明である（たとえば、ＭＩＰＳで、すべての４バイトが１つの命令である）。次に、対象命令フォーマットを所与の命令を構成するバイトに適用して、命令データ（すなわち、命令タイプ、オペランド・レジスタ数、即値フィールド値、およびその命令に符号化された他のすべての情報）を抽出する。アーキテクチャの命令フォーマットを使用して未フォーマット・バイト・ストリームから既知のアーキテクチャの機械命令を復号する工程は、当技術分野で周知である。
【００３７】
図４に、拡張基本ブロックの作成を示す。拡張基本ブロックになる資格を有する構成基本ブロックの組は、第１の資格のある基本ブロック（Ａ）が復号される時に検出される。変換器１９は、Ａの後継者（Ｂ）が静的に判定可能であることを検出した場合に５１、Ｂの開始アドレスを計算し５３、その後、Ｂの開始アドレスで復号工程を再開する。Ｂの後継者（Ｃ）が、静的に判定可能であると判定される場合に５５、復号工程は、Ｃの開始アドレスに進行し、以下同様である。もちろん、後継者ブロックが静的に判定可能でない場合には、通常の変換および実行が再開される６１、６３、６５。
【００３８】
すべての基本ブロックの復号中に、作業ＩＲフォレストに、現在のブロックの後継者の対象アドレス３１（すなわち、宛先対象アドレス。変換器は、宛先アドレス用の専用抽象レジスタを有する）を計算するためのＩＲツリーが含まれる。拡張基本ブロックの場合に、介在するジャンプが除去されるという事実を補償するために、各新しい構成基本ブロックが復号工程によって同化される時に、そのブロックの対象アドレスを計算するためのＩＲツリーが、枝刈りされる５４（図４）。言い換えると、変換器１９がＢのアドレスを静的に計算し、復号がＢの開始アドレスで再開される時に、Ｂの対象アドレス３１（Ａを復号する過程で構成された）の動的計算に対応するＩＲツリーが枝刈りされ、復号がＣの開始アドレスに進行する時に、Ｃの対象アドレスに対応するＩＲツリーが枝刈りされ５９、以下同様である。ＩＲツリーの「枝刈り」は、宛先アドレス抽象レジスタが依存し、他の抽象レジスタが依存しないすべてのＩＲノードを除去することを意味する。言い換えると、枝刈りは、ＩＲツリーと宛先アドレス・レジスタの間のリンクを破壊するが、同一ＩＲツリーへの他のすべてのリンクが、影響を受けない。いくつかの場合に、枝刈りされたＩＲツリーに、別の抽象レジスタも依存する場合があり、その場合に、そのＩＲツリーは、対象プログラムの実行セマンティクスを保存するために残される。
【００３９】
コード爆発を避けるために（伝統的に、そのようなコード特殊化技法に対する緩和要因）、変換器は、拡張基本ブロックをある最大個数の対象命令までに制限する。１実施形態で、拡張基本ブロックは、最大２００個の対象命令までに制限される。
アイソブロック
図示の実施形態で実装されるもう１つの最適化が、いわゆる「アイソブロッキング」である。この技法によれば、基本ブロックの変換が、互換性リストに基づいてパラメータ化または特殊化され、この互換性リストは、対象プロセッサ状態および変換器状態を記述する変数条件の組である。互換性リストは、異なるアーキテクチャ的特徴を考慮に入れるために、対象アーキテクチャごとに異なる。特定の基本ブロック変換の入口および出口での互換性条件の実際の値を、それぞれ入口条件および出口条件と称する。
【００４０】
実行が、既に変換されているが前の変換の入口条件が現在の作業条件（すなわち、前のブロックの出口条件）と異なる基本ブロックに達した場合に、その基本ブロックを、今回は現在の作業条件に基づいて、もう一度変換しなければならない。その結果は、同一の対象コード基本ブロックが、複数のターゲット・コード変換によって表されることである。同一の基本ブロックのこれらの異なる変換を、アイソブロックと称する。
【００４１】
アイソブロックをサポートするために、各基本ブロック変換に関連するデータに、１組の入口条件３５および１組の出口条件３６（図３）が含まれる。１実施形態で、基本ブロック・キャッシュ２３が、まず対象アドレス３１によって、次に入口条件３５、３６（図３）によって編成される。もう１つの実施形態で、変換器が対象アドレス３１について基本ブロック・キャッシュ２３に照会する時に、その照会が、複数の変換された基本ブロック（アイソブロック）を返すことが可能である。
【００４２】
図５に、アイソブロックの使用を示す。第１の変換されたブロックの実行の終りに、変換されたコード２１は、次のブロック（すなわち後継者）の対象アドレスを計算し、返す７１。次に、制御が、破線７３によって示されているように、変換器１９に返される。変換器１９では、基本ブロック・キャッシュ２３が、返された対象アドレス３１を使用して照会される、ステップ７５。基本ブロック・キャッシュは、同一の対象アドレス３１を有する０個、１個、または複数の基本ブロック・データ構造を返すことが可能である。基本ブロック・キャッシュ２３が、０個のデータ構造を返す（この基本ブロックがまだ変換されていないことを意味する）場合に、その基本ブロックを、変換器１９によって変換しなければならない、ステップ７７。基本ブロック・キャッシュ２３によって返された各データ構造が、対象コードの同一の基本ブロックの異なる変換（アイソブロック）に対応する。判断菱形７９に示されているように、現在の出口条件（第１の変換されたブロックの）が、基本ブロック・キャッシュ２３によって返されたデータ構造のどれの入口条件とも一致しない場合に、その基本ブロックを、やはり、今回はこの出口条件に基づいてパラメータ化して、変換しなければならない、ステップ８１。現在の出口条件が、基本ブロック・キャッシュ２３によって返されたデータ構造のいずれかの入口条件と一致する場合には、変換は、互換であり、再変換なしで実行することが可能である、ステップ８３。図示の実施形態では、変換器１９が、関数ポインタとしてターゲット・アドレスを間接参照することによって、互換の変換されたブロックを実行する。
【００４３】
上で注記したように、基本ブロック変換は、互換性リストに基づいてパラメータ化されることが好ましい。例示的な互換性リストを、これからＸ８６アーキテクチャおよびＰｏｗｅｒＰＣアーキテクチャの両方について説明する。
【００４４】
Ｘ８６アーキテクチャ用の例示的な互換性リストに、（１）対象レジスタのレイジイ伝搬（ｌａｚｙ  ｐｒｏｐａｇａｔｉｏｎ）、（２）オーバーラップする抽象レジスタ、（３）保留中の条件コード・フラグに影響する命令のタイプ、（４）条件コード・フラグに影響する命令パラメータのレイジイ伝搬、（５）文字列コピー動作の方向、（６）対象プロセッサの浮動小数点ユニット（ＦＰＵ）モード、および（７）セグメント・レジスタの変更の表現が含まれる。
【００４５】
Ｘ８６アーキテクチャの互換性リストに、レジスタ・エイリアシングとも称する、変換器による対象レジスタのすべてのレイジイ伝搬の表現が含まれる。レジスタ・エイリアシングは、基本ブロック境界で２つの対象レジスタに同一の値が含まれることを変換器が知っている時に発生する。対象レジスタ値が同一のままである限り、対応する抽象レジスタの１つだけが、これをグローバル・レジスタ・ストアに保存することによって同期化される。保存された対象レジスタが上書きされるまでは、保存されていないレジスタへの参照は、単純に、保存されたレジスタを使用するかコピーする（ｍｏｖｅ命令を介して）。これによって、変換されたコードでの２つのメモリ・アクセス（保存＋復元）が回避される。
【００４６】
Ｘ８６アーキテクチャ用の互換性リストに、オーバーラップする抽象レジスタのどれが現在定義されているかの表現が含まれる。いくつかの場合に、対象アーキテクチャに、変換器が複数のオーバーラップする抽象レジスタを使用して表現する複数のオーバーラップする対象レジスタが含まれる。たとえば、可変幅対象レジスタは、アクセス・サイズごとに１つの複数のオーバーラップする抽象レジスタを使用して表現される。たとえば、Ｘ８６「ＥＡＸ」レジスタは、それぞれが対応する抽象レジスタを有する、ＥＡＸ（ビット３１…０）、ＡＸ（ビット１５…０）、ＡＨ（ビット１５…８）、およびＡＬ（ビット７…０）という対象レジスタのいずれかを使用してアクセスすることが可能である。
【００４７】
Ｘ８６アーキテクチャ用の互換性リストに、整数条件コード・フラグおよび浮動小数点条件コード・フラグごとに、フラグ値が正規化または保留中のどちらであるかと、保留中の場合に保留中のフラグに影響する命令のタイプの表現が含まれる。
【００４８】
Ｘ８６アーキテクチャ用の互換性リストに、条件コード・フラグに影響する命令パラメータのレジスタ・エイリアシングの表現が含まれる（一部の対象レジスタが、まだフラグに影響する命令パラメータの値を保持する場合、または第２パラメータの値が第１パラメータと同一である場合に）。この互換性リストに、第２パラメータが小さい定数（すなわち、即値命令候補）であるかどうかと、そうである場合にその値の表現も含まれる。
【００４９】
Ｘ８６アーキテクチャ用の互換性リストに、対象プログラムの文字列コピー動作の現在の方向の表現が含まれる。この条件フィールドは、文字列コピー動作がメモリ内で上向きまたは下向きのどちらに移動するかを示す。これは、関数の方向引数の変換をパラメータ化することによって、「ｓｔｒｃｐｙ（）」関数呼び出しのコード特殊化をサポートする。
【００５０】
Ｘ８６アーキテクチャ用の互換性リストに、対象プロセッサのＦＰＵモードの表現が含まれる。このＦＰＵモードは、対象浮動小数点命令が３２ビット・モードまたは６４ビット・モードのどちらで動作しているかを示す。
【００５１】
Ｘ８６アーキテクチャ用の互換性リストに、セグメント・レジスタの変更の表現が含まれる。すべてのＸ８６命令メモリ参照は、６つのメモリ・セグメント・レジスタすなわち、ＣＳ（コード・セグメント）、ＤＳ（データ・セグメント）、ＳＳ（スタック・セグメント）、ＥＳ（エクストラ・データ・セグメント）、ＦＳ（汎用セグメント）、およびＧＳ（汎用セグメント）のうちの１つに基づく。通常の状況では、アプリケーションは、セグメント・レジスタを変更しない。したがって、コード生成は、デフォルトで、セグメント・レジスタ値が一定のままであるという仮定に基づいて特殊化される。しかし、プログラムがそのセグメント・レジスタを変更することが可能であり、その場合に、対応するセグメント・レジスタ互換性ビットがセットされ、これによって、変換器が、適当なセグメント・レジスタの動的値を使用する一般化されたメモリ・アクセス用のコードを生成するようになる。
【００５２】
ＰｏｗｅｒＰＣアーキテクチャ用の互換性リストの例示的実施形態に、（１）マングリングされたレジスタ（ｍａｎｇｌｅｄ  ｒｅｇｉｓｔｅｒ）、（２）リンク値伝搬、（３）保留中の条件コード・フラグに影響する命令のタイプ、（４）条件コード・フラグに影響する命令パラメータのレイジイ伝搬、（５）条件コード・フラグ値エイリアシング、および（６）サマリ・オーバーフロー・フラグ同期化状態の表現が含まれる。
【００５３】
ＰｏｗｅｒＰＣアーキテクチャ用の互換性リストに、マングリングされたレジスタの表現が含まれる。対象コードに、ベース・アドレスについて対象レジスタを使用する複数の連続するメモリ・アクセスが含まれる場合に、変換器は、これらのメモリ・アクセスを、マングリングされたターゲット・レジスタを使用して変換することが可能である。対象プログラム・データが、ターゲット・メモリ内で、対象メモリ内にあるときと同一のアドレスに配置されていない場合には、変換器は、対象コードによって計算されたメモリ・アドレスのすべてにターゲット・オフセットを含めなければならない。対象レジスタには対象ベース・アドレスが含まれるが、マングリングされたターゲット・レジスタには、その対象ベース・アドレスに対応するターゲット・アドレス（すなわち、対象ベース・アドレス＋ターゲット・オフセット）が含まれる。レジスタ・マングリングを用いると、マングリングされたレジスタに保管されたターゲット・ベース・アドレスに直接に対象コード・オフセットを適用することによって、メモリ・アクセスをより効率的に変換することが可能である。比べると、マングリングされたレジスタの機構がなければ、このシナリオは、空間と実行時間の両方を犠牲にして、メモリ・アクセスごとにターゲット・コードの追加の操作を必要とする。この互換性リストは、マングリングされる場合にどの抽象レジスタがマングリングされるかを示す。
【００５４】
ＰｏｗｅｒＰＣアーキテクチャ用の互換性リストに、リンク値伝搬の表現が含まれる。葉関数（すなわち、他の関数を呼び出さない関数）について、関数本体を、呼び出し／リターン場所に拡張することが可能である（上で述べた拡張基本ブロック機構と同様に）。したがって、関数本体およびその関数のリターンに続くコードが、一緒に変換される。これを、関数リターン特殊化とも称する。というのは、そのような変換は、関数のリターン場所からのコードを含み、したがって、関数のリターン場所に基づく特殊化であるからである。特定のブロック変換がリンク値伝搬を使用したかどうかが、出口条件に反映される。したがって、変換器は、その変換がリンク値伝搬を使用したブロックに出会った時に、現在のリターン場所が前のリターン場所と同一であるかどうかを評価しなければならない。関数は、呼び出された位置と同一の位置にリターンし、したがって、呼び出し場所とリターン場所は、効果的に同一である（１つまたは２つの命令だけオフセットしている）。したがって、変換器は、めいめいの呼び出し場所を比較することによって、リターン場所が同一であるかどうかを判定することが可能であり、これは、めいめいの先祖ブロック（関数本体の前の実行および現在の実行の）の対象アドレスを比較することと同等である。したがって、リンク値伝搬をサポートする実施形態では、各基本ブロック変換に関連するデータに、先祖ブロック変換への参照（または先祖ブロックの対象アドレスの他の表現）が含まれる。
【００５５】
ＰｏｗｅｒＰＣアーキテクチャ用の互換性リストに、整数条件コード・フラグおよび浮動小数点条件コード・フラグごとに、フラグ値が正規化または保留中のどちらであるかと、保留中の場合に保留中のフラグに影響する命令のタイプの表現が含まれる。
【００５６】
ＰｏｗｅｒＰＣアーキテクチャ用の互換性リストに、フラグに影響する命令パラメータのレジスタ・エイリアシングの表現が含まれる（フラグに影響する命令パラメータが、対象レジスタ内でライブである場合、または第２パラメータの値が第１パラメータと同一である場合に）。この互換性リストに、第２パラメータが小さい定数（すなわち、即値命令候補）であるかどうかと、そうである場合にその値の表現も含まれる。
【００５７】
ＰｏｗｅｒＰＣアーキテクチャ用の互換性リストに、ＰｏｗｅｒＰＣ条件コード・フラグ値のレジスタ・エイリアシングの表現が含まれる。ＰｏｗｅｒＰＣアーキテクチャには、ＰｏｗｅｒＰＣフラグの組全体を汎用（対象）レジスタに明示的にロードする命令が含まれる。対象レジスタ内の対象フラグ値のこの明示的表現は、変換器の条件コード・フラグ・エミュレーション最適化に干渉する。この互換性リストに、フラグ値が対象レジスタ内でライブであるかどうかと、そうである場合にどのレジスタがそれであるかの表現が含まれる。ＩＲ生成中に、そのような対象レジスタがフラグ値を保持している間のその対象レジスタへの参照が、対応する抽象レジスタへの参照に変換される。この機構は、対象フラグ値を明示的に計算し、ターゲット・レジスタに保管する必要をなくし、これによって、変換器が、標準的な条件コード・フラグ最適化を適用することが可能になる。
【００５８】
ＰｏｗｅｒＰＣアーキテクチャ用の互換性リストに、サマリ・オーバーフロー同期化の表現が含まれる。このフィールドは、８つのサマリ・オーバーフロー条件ビットのどれが、現在グローバル・サマリ・オーバーフロー・ビットを有するかを示す。ＰｏｗｅｒＰＣの８つの条件フィールドのうちの１つが更新される時に、グローバル・サマリ・ビットがセットされているならば、これが、特定の条件コード・フィールド内の対応するサマリ・オーバーフロー・ビットにコピーされる。
変換ヒント
例示的な実施形態で実装されるもう１つの最適化は、図３の基本ブロック・データ構造の変換ヒント３４を使用する。この最適化は、特定の基本ブロックに固有であるが、そのブロックのすべての変換について同一である静的基本ブロック・データがあることの認識から進行する。静的データのうちで計算が高価であるいくつかのタイプについて、変換器が、対応するブロックへの第１の変換中にデータを１回計算し、その後、同一ブロックの将来の変換のためにその結果を保管することがより効率的である。このデータは、同一ブロックのすべての変換について同一なので、パラメータ化された変換を行わず、したがって、形式的にはブロックの互換性リスト（上で述べた）の一部ではない。しかし、高価な静的データは、それでも、各基本ブロック変換に関連するデータに保管される。というのは、このデータを再計算するよりも保存することがより安価であるからである。同一ブロックの後の変換で、変換器１９が前の変換を再利用することが不可能な場合であっても、変換器１９は、これらの「変換ヒント」（すなわち、キャッシングされた静的データ）を利用して、第２のおよびそれ以降の変換の変換コストを減らすことが可能である。
【００５９】
１実施形態で、各基本ブロック変換に関連するデータに、変換ヒントが含まれ、この変換ヒントは、そのブロックの第１の変換中に１回計算され、その後、各後続の変換時にコピーされる（または参照される）。
【００６０】
たとえば、Ｃ＋＋で実装された変換器１９で、変換ヒントを、Ｃ＋＋オブジェクトとして実装することが可能であり、この場合に、同一ブロックの異なる変換に対応する基本ブロック・オブジェクトは、それぞれ、同一の変換ヒント・オブジェクトへの参照を保管するはずである。その代わりに、Ｃ＋＋で実装された変換器で、基本ブロック・キャッシュ２３に、対象基本ブロックごとに（変換ごとではなく）１つの基本ブロック・オブジェクトを含めることが可能であり、そのようなオブジェクトのそれぞれが、対応する変換ヒントへの参照を含むか保持し、そのような基本ブロック・オブジェクトに、入口条件によって編成されたそのブロックの異なる変換に対応する変換オブジェクトへの複数の参照も含まれる。
【００６１】
Ｘ８６アーキテクチャの例示的変換ヒントに、（１）初期命令プレフィックスおよび（２）初期リピート・プレフィックスの表現が含まれる。Ｘ８６アーキテクチャのそのような変換ヒントに、特に、ブロック内の第１の命令が何個のプレフィクスを有するかの表現が含まれる。一部のＸ８６命令は、その命令の動作を変更するプレフィックスを有する。このアーキテクチャ的特徴は、Ｘ８６命令ストリームの復号を困難に（すなわち高価に）する。初期プレフィックスの個数がブロックの第１の復号中に判定されたならば、その値を、変換器１９が変換ヒントとして保管し、その結果、同一ブロックの後続変換が、それを改めて判定する必要がなくなる。
【００６２】
Ｘ８６アーキテクチャの変換ヒントに、さらに、ブロック内の第１の命令がリピート・プレフィックスを有するかどうかの表現が含まれる。文字列演算などの一部のＸ８６命令は、プロセッサにその命令を複数回実行するように指示するリピート・プレフィックスを有する。変換ヒントは、そのようなプレフィックスが存在するかどうかと、そうである場合にその値を示す。
【００６３】
１実施形態で、各基本ブロックに関連する変換ヒントに、さらに、その基本ブロックに対応するＩＲフォレスト全体が含まれる。これによって、効果的に、フロントエンドによって実行される復号およびＩＲ生成のすべてがキャッシングされる。もう１つの実施形態で、変換ヒントに、最適化される前に存在したＩＲフォレストが含まれる。もう１つの実施形態で、変換されたプログラムのメモリ・リソースを節約するために、ＩＲフォレストが、変換ヒントとしてキャッシングされない。
グループ・ブロック
例示的な変換器実施形態で実装されるもう１つの最適化は、各変換された基本ブロックの実行の終りにすべての抽象レジスタを同期化する必要から生じるプログラム・オーバーヘッドをなくすことを対象とする。この最適化を、グループ・ブロック最適化と称する。
【００６４】
上で述べたように、基本ブロック・モード（たとえば、図２）で、状態は、すべての変換されたコード・シーケンスからアクセス可能なメモリ領域すなわちグローバル・レジスタ・ストア２７を使用して、ある基本ブロックから次の基本ブロックに渡される。グローバル・レジスタ・ストア２７は、抽象レジスタのリポジトリであり、この抽象レジスタのそれぞれが、特定の対象レジスタまたは他の対象アーキテクチャ特徴に対応し、その値をエミュレートする。変換されたコード２１の実行中に、抽象レジスタは、ターゲット・レジスタに保持され、その結果、これらが命令に参加することが可能になる。変換器コード２１の実行中に、抽象レジスタ値は、グローバル・レジスタ・ストア２７またはターゲット・レジスタ１５に保管される。
【００６５】
したがって、図２に示されたものなどの基本ブロック・モードでは、２つの理由すなわち（１）制御が変換器コード１９に戻り、これによってすべてのターゲット・レジスタが潜在的に上書きされ、（２）コード生成が１時に１つの基本ブロックだけを見るので、すべての抽象レジスタがライブであり（すなわち、後続基本ブロックで使用される）、したがって保存されなければならないことを変換器１９が仮定しなければならないので、すべての抽象レジスタが、各基本ブロックの終りに同期化されなければならない。グループ・ブロック最適化機構の目標は、複数の基本ブロックを連続する全体として変換することによって、頻繁にまたがれる基本ブロック境界にまたがる同期化を減らすことである。複数の基本ブロックを一緒に変換することによって、ブロック境界での同期化を、削除されない場合でも減らすことが可能になる。
【００６６】
グループ・ブロック構成は、現在のブロックのプロファイリング・メトリックがトリガ閾値に達した時にトリガされる。このブロックを、トリガ・ブロックと称する。構成は、次のステップ（図６）に分割することが可能である：（１）メンバ・ブロックの選択７１、（２）メンバ・ブロックの順序付け７３、（３）グローバル・デッド・コード除去７５、（４）グローバル・レジスタ割振り７７、および（５）コード生成７９。最初のステップ７１は、トリガ・ブロックから開始し、包含閾値および最大メンバ限度によって調整されるプログラムの制御フロー・グラフの深さ優先検索（ＤＦＳ）トラバーサルを実行することによって、グループ・ブロックに含まれるブロックの組を識別する。第２ステップ７３は、ブロックの組を順序付け、グループ・ブロックを通るクリティカル・パスを識別して、同期化コードを最小にし、分岐を減らす効率的なコード・レイアウトを可能にする。第３および第４のステップ７５および７７は、最適化を実行する。最後のステップ７９は、すべてのメンバ・ブロックのコードを順番に生成し、効率的なレジスタ割振りを有する効率的なコード・レイアウトを作る。
【００６７】
グループ・ブロックの構成およびそれからのターゲット・コードの生成で、変換器コード１９は、図６に示されたステップを実装する。変換器１９が、以前に変換された基本ブロックに出会った時に、そのブロックを実行する前に、変換器１９は、そのブロックのプロファイリング・メトリック３７（図３）を、トリガ閾値に対して検査する。変換器１９は、基本ブロックのプロファイリング・メトリック３７がトリガ閾値を超える時に、グループ・ブロック作成を開始する。変換器１９は、トリガ・ブロックから開始し、包含閾値および最大メンバ限度によって調整される制御フロー・グラフのトラバーサルによって、グループ・ブロックのメンバを識別する。次に、変換器１９は、メンバ・ブロックの順序付けを作成し、これは、そのグループ・ブロックを通るクリティカル・パスを識別する。次に、変換器１９は、グローバル・デッド・コード除去を実行し、変換器１９は、各ブロックに対応するＩＲを使用して、各メンバ・ブロックのレジスタ・ライブネス情報を収集する。次に、変換器１９は、アーキテクチャ固有ポリシに従ってグローバル・レジスタ割振りを実行し、このアーキテクチャ固有ポリシは、すべてのメンバ・ブロックの均一なレジスタ・マッピングの部分的な組を定義する。最後に、変換器１９は、グローバル・レジスタ割振り制約と一貫する順序で、レジスタ・ライブネス分析を使用して、各メンバ・ブロックのターゲット・コードを順番に生成する。
【００６８】
上で注記したように、各基本ブロックに関連するデータに、プロファイリング・メトリック３７が含まれる。１実施形態で、プロファイリング・メトリック３７は、実行カウントであり、これは、変換器１９が、特定の基本ブロックが実行された回数をカウントすることを意味し、この実施形態では、プロファイリング・メトリック３７が、整数カウント・フィールド（カウンタ）として表される。もう１つの実施形態で、プロファイリング・メトリック３７は、実行時間であり、これは、変換器１９が、それぞれハードウェア・タイマまたはソフトウェア・タイマを起動し、停止させるコードを基本ブロックの始めと終りに埋め込むことによるなど、特定の基本ブロックのすべての実行の実行時間のランニング集計を保つことを意味し、この実施形態では、プロファイリング・メトリック３７が、集計実行時間のある表現（タイマ）を使用する。もう１つの実施形態で、変換器１９が、基本ブロックごとに複数のタイプのプロファイリング・メトリック３７を保管する。もう１つの実施形態で、変換器１９は、異なる制御パスについて別個のプロファイリング・データが維持されるように、各先祖基本ブロックおよび／または各後継者基本ブロックに対応する、基本ブロックごとに複数の組のプロファイリング・メトリック３７を保管する。各変換器・サイクル（すなわち、変換されたコード２１の実行の間の変換器コード１９の実行）に、適当な基本ブロックのプロファイリング・メトリック３７が更新される。
【００６９】
グループ・ブロックをサポートする実施形態で、各基本ブロックに関連するデータに、さらに、既知の先祖および後継者の基本ブロック・オブジェクトへの参照３８および３９が含まれる。これらの参照は、全体で、すべての前に実行された基本ブロックの制御フロー・グラフを構成する。グループ・ブロック形成中に、変換器１９は、この制御フロー・グラフをトラバースして、形成中のグループ・ブロックにどの基本ブロックを含めるかを決定する。
【００７０】
例示的実施形態でのグループ・ブロック形成は、３つの閾値すなわち、トリガ閾値、包含閾値、および最大メンバ限度に基づく。トリガ閾値および包含閾値は、各基本ブロックのプロファイリング・メトリック３７を参照する。各変換器・サイクルに、次の基本ブロックのプロファイリング・メトリック３７が、トリガ閾値と比較される。メトリック３７が、トリガ閾値を満足する場合に、グループ・ブロック形成が開始される。次に、包含閾値を使用して、そのグループ・ブロックに含める後継者基本ブロックを識別することによって、グループ・ブロックのスコープを決定する。最大メンバ限度は、１つのグループ・ブロックに含まれる基本ブロックの個数の上限を定義する。
【００７１】
基本ブロックＡについてトリガ閾値に達した時に、新しいグループ・ブロックが、トリガ・ブロックとしてＡを用いて形成される。次に、変換器１９は、定義トラバーサルすなわち、制御フロー・グラフ内のＡの後継者のトラバーサルを開始して、含めるべき他のメンバ・ブロックを識別する。トラバーサルが所与の基本ブロックに達した時に、そのプロファイリング・メトリック３７が、包含閾値と比較される。メトリック３７が、包含閾値を満足する場合に、その基本ブロックが、包含についてマークされ、トラバーサルが、そのブロックの後継者に継続される。ブロックのメトリック３７が、包含閾値未満の場合には、そのブロックは、除外され、その後継者は、トラバースされない。トラバーサルが終了した（すなわち、すべてのパスが、除外されるブロックに達したか含まれるブロックにサイクル・バックした、または最大メンバ限度に達した）時に、変換器１９は、含まれた基本ブロックのすべてに基づいて新しいグループ・ブロックを構成する。
【００７２】
アイソブロックおよびグループ・ブロックを使用する実施形態で、制御フロー・グラフは、アイソブロックのグラフであり、これは、同一対象ブロックの異なるアイソブロックが、グループ・ブロック作成において異なるブロックとして扱われることを意味する。したがって、同一対象ブロックの異なるアイソブロックのプロファイリング・メトリックは、集計されない。
【００７３】
もう１つの実施形態で、アイソブロックは、基本ブロック変換では使用されないが、グループ・ブロック変換で使用され、これは、非グループ基本ブロック変換が一般化されている（入口条件に対して特殊化されない）ことを意味する。この実施形態では、基本ブロックのプロファイリング・メトリックが、各実行の入口条件によって成分に分けられ、別個のプロファイリング情報が、理論的アイソブロックごとに（すなわち、入口条件の別個の組ごとに）維持される。この実施形態では、各基本ブロックに関連するデータに、プロファイリング・リストが含まれ、このプロファイリング・リストの各メンバは、（１）入口条件の組、（２）対応するプロファイリング・メトリック、および（３）対応する後継者ブロックのリストを含む３項目の組である。このデータは、実際の基本ブロック変換が入口条件に対して特殊化されない場合であっても、基本ブロックの入口条件の組ごとにプロファイリング情報および制御パス情報を維持する。この実施形態では、トリガ閾値が、基本ブロックのプロファイリング・メトリック・リスト内の各プロファイリング・メトリックと比較される。制御フロー・グラフをトラバースする時には、所与の基本ブロックのプロファイリング・リスト内の各要素が、制御フロー・グラフ内の別々のノードとして扱われる。したがって、包含閾値は、ブロックのプロファイリング・リスト内の各プロファイリング・メトリックと比較される。この実施形態では、グループ・ブロックが、ホット対象ブロックの特定のホット・アイソブロック（特定の入口条件に特殊化される）について作成されるが、この同一の対象ブロックの他のアイソブロックは、これらのブロックの一般（非アイソブロック）変換を使用して実行される。
【００７４】
定義トラバーサルの後に、変換器１９は、順序付けトラバーサル、ステップ７３；図６を実行して、メンバ・ブロックを変換する順序を決定する。メンバ・ブロックの順序は、変換されたコード２１の命令キャッシュ挙動（ホット・パスが連続的でなければならない）およびメンバ・ブロック境界での同期化の必要（同期化は、ホット・パスに沿って最小化されなければならない）の両方に影響する。１実施形態で、変換器１９は、実行カウントによって順序付けられた順序付き深さ優先検索（ＤＦＳ）アルゴリズムを使用して順序付けトラバーサルを実行する。トラバーサルは、最大の実行カウントを有するメンバ・ブロックで開始される。トラバースされるメンバ・ブロックが複数の後継者を有する場合に、最大の実行カウントを有する後継者が、最初にトラバースされる。
【００７５】
当業者は、グループ・ブロックが、内部制御分岐、複数の入口点、および／または複数の出口点を有する場合があるので、形式的な基本ブロックでないことを諒解するであろう。
【００７６】
グループ・ブロックが形成されたならば、本明細書で「グローバル・デッド・コード除去」と称するさらなる最適化を適用することが可能である。そのようなグローバル・デッド・コード除去は、ライブネス分析の技法を使用する。グローバル・デッド・コード除去は、基本ブロックのグループにまたがってＩＲから冗長な作業を除去する工程である。一般に、対象プロセッサ状態を、変換スコープ境界で同期化しなければならない。対象レジスタなどの値は、その定義で始まり、再定義（上書き）の前の最後の使用で終わるコードの範囲について「ライブ」といわれ、したがって、値（たとえば、ＩＲ生成の文脈での一時値、コード生成の文脈でのターゲット・レジスタ、または変換の文脈での対象レジスタ）の使用および定義の分析を、当技術分野でライブネス分析と称する。変換器がデータおよび状態の使用（読取）および定義（書込）に関して有する知識（すなわち、ライブネス分析）のどれであっても、その変換スコープに制限され、プログラムの残りは、未知である。具体的に言うと、変換器は、どの対象レジスタが変換のスコープの外部（たとえば、後継者基本ブロック内）で使用されるかを知らないので、すべてのレジスタが使用されると仮定しなければならない。したがって、所与の基本ブロック内で変更されたすべての対象レジスタの値（定義）を、その将来の使用の可能性に備えて、その基本ブロックの終りに保存（グローバル・レジスタ・ストア２７に保管）しなければならない。同様に、所与の基本ブロック内で値が使用されるすべての対象レジスタをその基本ブロックの始めに復元（グローバル・レジスタ・ストア２７からロード）しなければならない、すなわち、基本ブロックの変換されたコードは、その基本ブロック内での最初の使用の前に、所与の対象レジスタを復元しなければならない。
【００７７】
ＩＲ生成の一般的な機構に、「ローカル」デッド・コード除去の暗黙の形が含まれ、そのスコープは、１回にＩＲノードの小さいグループだけに局所化されている。たとえば、対象コード内の共通部分式Ａは、式ツリーＡ自体の複数のインスタンスではなく、複数の親ノードを有するＡの単一のＩＲツリーによって表される。「除去」は、１つのＩＲノードが複数の親ノードへのリンクを有することが可能であるという事実に潜在的に含まれる。同様に、ＩＲプレースホルダとしての抽象レジスタの使用は、デッド・コード除去の暗黙の形である。所与の基本ブロックの対象コードが、特定の対象レジスタを絶対に定義しない場合に、そのブロックのＩＲ生成の終りに、その対象レジスタに対応する抽象レジスタは、空のＩＲツリーを参照する。コード生成フェーズは、このシナリオで、適当な抽象レジスタをグローバル・レジスタ・ストアと同期化する必要がないことを認識する。したがって、ローカル・デッド・コード除去は、ＩＲ生成フェーズに潜在的に含まれ、ＩＲノードが作成される時に増分的に行われる。
【００７８】
ローカル・デッド・コード除去と対照的に、「グローバル」デッド・コード除去アルゴリズムは、基本ブロックのＩＲ式フォレスト全体に適用される。例示的実施形態によるグローバル・デッド・コード除去は、ライブネス分析を必要とし、これは、ライブ領域とデッド領域を識別するための、グループ・ブロック内の各基本ブロックのスコープ内の対象レジスタ使用（読取）および対象レジスタ定義（書込）の分析を意味する。ＩＲは、デッド領域を除去するために変換され、これによって、ターゲット・コードによって実行されなければならない作業の量が減る。たとえば、対象コード内の所与の点で、変換器１９が、特定の対象レジスタが次の使用の前に定義（上書き）されることを認識または検出した場合に、その対象レジスタは、その先取りする定義までのコード内のすべての点で、デッドといわれる。ＩＲに関して、定義されたが再定義の前に一度も使用されない対象レジスタは、ターゲット・コードを作ることさえなく、ＩＲフェーズで除去可能なデッド・コードである。ターゲット・コード生成に関して、デッドであるターゲット・レジスタは、スピル（ｓｐｉｌｌｉｎｇ）なしで、他の一時レジスタ値または対象レジスタ値に使用することが可能である。
【００７９】
グループ・ブロック・グローバル・デッド・コード除去で、ライブネス分析は、すべてのメンバ・ブロックに対して実行される。ライブネス分析は、各メンバ・ブロックのＩＲフォレストを生成し、このＩＲフォレストが、次に、そのブロックの対象レジスタ・ライブネス情報を導出するのに使用される。各メンバ・ブロックのＩＲフォレストは、グループ・ブロック作成のコード生成フェーズでも必要である。各メンバ・ブロックのＩＲフォレストをライブネス分析で生成したならば、これを、コード生成での後続使用のために保存すること、または削除し、コード生成中に再生成することのいずれかが可能である。
【００８０】
グループ・ブロック・グローバル・コード除去は、ＩＲを２つの形で効果的に「変換」することが可能である。第１に、ライブネス分析中にメンバ・ブロックごとに生成されたＩＲフォレストを、変更することが可能であり、その後、そのＩＲフォレスト全体を、コード生成フェーズに伝搬させる（すなわち、保存し、コード生成フェーズ中に再利用する）ことが可能であり、このシナリオでは、ＩＲ変換が、コード生成フェーズをＩＲフォレストに直接に適用し、その後、変換されたＩＲフォレストを保存することによって、コード生成フェーズを通じて伝搬される。このシナリオでは、各メンバ・ブロックに関連するデータに、ライブネス情報（さらにグローバル・レジスタ割振りで使用される）およびそのブロックの変換されたＩＲフォレストが含まれる。
【００８１】
その代わりに、好ましくは、あるメンバ・ブロックのＩＲを変換するグローバル・デッド・コード除去のステップが、以前に作成されたライブネス情報を使用して、グループ・ブロック作成の最後のコード生成フェーズ中に実行される。この実施形態では、グローバル・デッド・コード変換を、「デッド」対象レジスタのリストとして記録することが可能であり、このリストは、その後、各メンバ・ブロックに関連するライブネス情報に符号化される。したがって、ＩＲフォレストの実際の変換は、後続のコード生成フェーズによって実行され、このコード生成フェーズは、デッド・レジスタ・リストを使用して、ＩＲフォレストを枝刈りする。このシナリオは、変換器が、ライブネス分析中にＩＲを１回生成し、次にそのＩＲを捨て、次にコード生成中に同一のＩＲを再生成することを可能にし、このコード生成の時点で、ＩＲは、ライブネス分析を使用して変換される（すなわち、グローバル・デッド・コード除去が、ＩＲ自体に適用される）。このシナリオでは、各メンバ・ブロックに関連するデータに、ライブネス情報が含まれ、このライブネス情報に、デッド対象レジスタのリストが含まれる。ＩＲフォレストは、保存されない。具体的に言うと、ＩＲフォレストがコード生成フェーズで（再）生成された後に、デッド対象レジスタのＩＲツリー（ライブネス情報内のデッド対象レジスタ・リストにリストされる）が枝刈りされる。
【００８２】
１実施形態で、ライブネス分析中に作成されたＩＲは、メモリ・リソースを節約するために、ライブネス情報を抽出した後に捨てられる。ＩＲフォレスト（メンバ・ブロックごとに１つ）が、１時に１メンバ・ブロックずつ、コード生成中に再作成される。この実施形態では、すべてのメンバ・ブロックのＩＲフォレストが、変換のどの時点でも共存しない。しかし、それぞれライブネス分析中およびコード生成中に作成されるＩＲフォレストの２つのバージョンは、これらが同一のＩＲ生成工程を使用して対象コードから生成されるので、同一である。
【００８３】
もう１つの実施形態で、変換器は、ライブネス分析中に各メンバ・ブロックのＩＲフォレストを作成し、そのＩＲフォレストを各メンバ・ブロックに関連するデータに保存して、コード生成中に再利用する。この実施形態では、すべてのメンバ・ブロックのＩＲフォレストが、ライブネス分析の終り（グローバル・デッド・コード除去ステップの）からコード生成まで共存する。この実施形態の代替形態の１つでは、ＩＲの最初の作成（ライブネス分析中）からその最後の使用（コード生成）までの期間中に、ＩＲに対して変換または最適化が実施されない。
【００８４】
もう１つの実施形態で、すべてのメンバ・ブロックのＩＲフォレストが、ライブネス分析のステップとコード生成のステップの間で保存され、ブロック間最適化が、コード生成の前にＩＲフォレストに対して実行される。この実施形態では、変換器が、すべてのメンバ・ブロックＩＲフォレストが変換の同一の点で共存するという事実を利用し、最適化が、これらのＩＲフォレストを変換する異なるメンバ・ブロックのＩＲフォレストにまたがって実行される。この場合に、コード生成に使用されるＩＲフォレストは、ライブネス分析に使用されるＩＲフォレストと同一（上で説明した２つの実施形態のように）でない場合がある。というのは、これらのＩＲフォレストが、その後にブロック間最適化によって変換されているからである。言い換えると、コード生成に使用されるＩＲフォレストが、１時に１メンバ・ブロックずつ新たに生成することから生じるＩＲフォレストと異なる場合がある。
【００８５】
グループ・ブロック・グローバル・デッド・コード除去では、デッド・コード検出のスコープが、ライブネス分析が同時に複数のブロックに適用されるという事実によって広げられる。しかし、対象レジスタが最初のメンバ・ブロックで定義され、その後、３番目のブロックで再定義される（間に入る使用または出口点なしで）場合に、最初の定義のＩＲツリーを、最初のメンバ・ブロックから除去することが可能である。比べると、基本ブロック・コード生成の下で、変換器１９は、この対象レジスタがデッドであることを検出することが不可能である。
【００８６】
上で注記したように、グループ・ブロック最適化の目標の１つは、基本ブロック境界でのレジスタ同期化の必要を減らすかなくすことである。したがって、レジスタ割り振りおよび同期化がグループ・ブロッキング中に変換器１９によってどのように達成されるかの議論をこれから提供する。
【００８７】
レジスタ割振りは、抽象（対象）レジスタをターゲット・レジスタに関連付ける工程である。抽象レジスタ値が、ターゲット命令に参加するためにターゲット・レジスタ内に存在しなければならないので、レジスタ割振りは、コード生成の必要なコンポーネントである。ターゲット・レジスタと抽象レジスタの間のこれらの割振り（すなわち、マッピング）の表現を、レジスタ・マップと称する。コード生成中に、変換器１９は、作業レジスタ・マップを維持し、この作業レジスタ・マップは、レジスタ割振りの現在の状態を反映する（すなわち、ターゲット・コードの所与の点に実際に存在するターゲット対抽象レジスタ・マッピング）。以下で、出口レジスタ・マップに言及するが、この出口レジスタ・マップは、抽象的には、メンバ・ブロックからの出口での作業レジスタ・マップのスナップショットである。しかし、出口レジスタ・マップは、同期化に必要ではないので、記録されず、したがって、純粋に抽象的である。入口レジスタ・マップ４０（図３）は、メンバ・ブロックへの入口での作業レジスタ・マップのスナップショットであり、これは、同期化のために記録する必要がある。
【００８８】
また、上で述べたように、グループ・ブロックに、複数のメンバ・ブロックが含まれ、コード生成は、メンバ・ブロックごとに別々に実行される。したがって、各メンバ・ブロックは、それ自体の入口レジスタ・マップ４０および出口レジスタ・マップを有し、これらのマップは、それぞれ、そのブロックの変換されたコードの始めおよび終りでの特定の対象レジスタへの特定のターゲット・レジスタの割振りを反映する。
【００８９】
グループ・メンバ・ブロックのコード生成は、その入口レジスタ・マップ４０（入口での作業レジスタ・マップ）によってパラメータ化されるが、コード生成は、作業レジスタ・マップも変更する。メンバ・ブロックの出口レジスタ・マップは、コード生成工程で変更された、そのブロックの出口での作業レジスタ・マップを反映する。最初のメンバ・ブロックが変換される時に、作業レジスタ・マップは空である（下で述べるグローバル・レジスタ割振りの対象）。最初のメンバ・ブロックの変換の終りに、作業レジスタ・マップに、コード生成工程によって作成されたレジスタ・マッピングが含まれる。その後、この作業レジスタ・マップが、すべての後継者メンバ・ブロックの入口レジスタ・マップ４０にコピーされる。
【００９０】
メンバ・ブロックのコード生成の終りに、一部の抽象レジスタが、同期化を必要としない場合がある。レジスタ・マップは、変換器１９が、どのレジスタが実際に同期化を必要とするかを識別することによってメンバ・ブロック境界での同期化を最小にすることを可能にする。比べると、（非グループ）基本ブロック・シナリオでは、すべての抽象レジスタが、すべての基本ブロックの終りで同期化されなければならない。
【００９１】
メンバ・ブロックの終りで、後継者に基づいて３つの同期化シナリオが可能である。第１に、後継者が、まだ変換されていないメンバ・ブロックである場合に、その入口レジスタ・マップ４０は、作業レジスタ・マップと同一と定義され、その結果、同期化は不要である。第２に、後継者が、グループの外部である場合に、後継者の実行の前に制御が変換器コード１９に返されるので、すべての抽象レジスタを同期化しなければならない（すなわち、フル同期化）。第３に、後継者ブロックが、そのレジスタ・マップが既に固定されているメンバ・ブロックである場合に、次に作業マップを後継者の入口マップと一致させるために、同期化コードを挿入しなければならない。
【００９２】
レジスタ・マップ同期化のコストの一部は、グループ・ブロック順序付けトラバーサルによって減らされ、このグループ・ブロック順序付けトラバーサルは、ホット・パスに沿って、レジスタ同期化を最小にするか、レジスタ同期化を完全に除去する。メンバ・ブロックは、順序付けトラバーサルによって生成された順序で変換される。各メンバ・ブロックが変換される時に、その出口レジスタ・マップが、その入口レジスタ・マップがまだ固定されていないすべての後継者メンバ・ブロックの入口レジスタ・マップ４０に伝搬される。効果的に、グループ・ブロック内の最もホットなパスが、最初に変換され、そのパスに沿った、すべてではないにしてもほとんどのメンバ・ブロック境界が、対応するレジスタ・マップがすべて一貫しているので同期化を必要としない。
【００９３】
たとえば、最初のメンバ・ブロックと２番目のメンバ・ブロックの間の境界は、必ず同期化を必要としない。というのは、２番目のメンバ・ブロックが、必ず、その入口レジスタ・マップ４０を最初のメンバ・ブロックの出口レジスタ・マップ４１と同一になるように固定されるからである。メンバ・ブロックの間の同期化の一部は、グループ・ブロックに内部制御分岐および複数の入口点が含まれる可能性があるので、不可避である可能性がある。これは、実行が、異なる時に、異なる作業レジスタ・マップを有する異なる先祖から同一のメンバ・ブロックに達する場合があることを意味する。この場合に、変換器１９が作業レジスタ・マップを適当なメンバ・ブロックの入口レジスタ・マップに同期化することが必要である。
【００９４】
必要な場合に、レジスタ・マップ同期化が、メンバ・ブロック境界で行われる。変換器１９は、メンバ・ブロックの終りにコードを挿入して、作業レジスタ・マップを後継者の入口レジスタ・マップ４０と同期化する。レジスタ・マップ同期化では、各抽象レジスタが、１０個の同期化条件のうちの１つに含まれる。表１に、変換器の作業レジスタ・マップおよび後継者の入口レジスタ・マップ４０の関数としての１０個のレジスタ同期化の事例を示す。表２で、１０個の形式的な同期化事例を、それらの事例のテキスト記述および対応する同期化アクションの擬似コード記述（擬似コードは下で説明する）と共に列挙することによって、レジスタ同期化アルゴリズムを説明する。したがって、すべてのメンバ・ブロック境界で、すべての抽象レジスタが、１０事例のアルゴリズムを使用して同期化される。同期化条件およびアクションのこの詳細な表明は、変換器１９が、各抽象レジスタの同期化コストを最小にする効率的な同期化コードを生成することを可能にする。
【００９５】
次に、表２にリストされた同期化アクション関数を説明する。「Ｓｐｉｌｌ（Ｅ（ａ））」は、ターゲット・レジスタＥ（ａ）から対象レジスタ・バンク（グローバル・レジスタ・ストアの１コンポーネント）に抽象レジスタを保存する。「Ｆｉｌｌ（ｔ，ａ）」は、対象レジスタ・バンクからターゲット・レジスタｔに抽象レジスタａをロードする。「Ｒｅａｌｌｏｃａｔｅ（）」は、使用可能な場合に抽象レジスタを新しいターゲット・レジスタに移動し、再割振りし（すなわち、この抽象レジスタのマッピングを変更し）、ターゲット・レジスタが使用不能な場合には抽象レジスタをスピルする。「ＦｒｅｅＮｏＳｐｉｌｌ（ｔ）」は、関連する抽象対象レジスタをスピルせずに、ターゲット・レジスタを空きとしてマークする。ＦｒｅｅＮｏＳｐｉｌｌ（）関数は、同一の同期化点でのこのアルゴリズムの複数の適用にまたがる余分なスピルを避けるために必要である。「Ｎｉｌ」同期化アクションの場合に、対応する抽象レジスタに関して同期化コードが不要であることに留意されたい。
【００９６】
【表１】
0005419325.tif 000002
【００９７】
【表２】
0005419325.tif 000003
【００９８】
0005419325.tif 000004
【００９９】
変換器１９は、グループ・ブロック内で、グローバルおよびローカル（または一時）という２レベルのレジスタ割振りを実行する。グローバル・レジスタ割振りは、コード生成の前の、グループ・ブロック全体にまたがって（すなわち、すべてのメンバ・ブロックを通じて）永続する特定のレジスタ・マッピングの定義である。ローカル・レジスタ割振りは、コード生成の工程で作成されるレジスタ・マッピングからなる。グローバル・レジスタ割振りは、ローカル・レジスタ割振りを制約することによってメンバ・ブロックのコード生成をパラメータ化する特定のレジスタ割振り制約を定義する。
【０１００】
グローバルに割り振られる抽象レジスタは、すべてのメンバ・ブロックで同一のめいめいのターゲット・レジスタに割り振られることが保証されるので、メンバ・ブロック境界での同期化を必要としない。この手法は、同期化コード（ブロックの間のレジスタ・マッピングの相違を補償する）が、メンバ・ブロック境界で、グローバルに割り振られた抽象レジスタについて絶対に必要でないという利益を有する。グループ・ブロック・レジスタ・マッピングの不利益は、グローバルに割り振られたターゲット・レジスタが新しいマッピングに直接に使用可能でないので、ローカル・レジスタ割振りを妨げることである。補償するために、グローバル・レジスタ・マッピングの個数を、特定のグループ・ブロックについて制限することが可能である。
【０１０１】
実際のグローバル・レジスタ割振りの個数および選択は、グローバル・レジスタ割振りポリシによって定義される。グローバル・レジスタ割振りポリシは、対象アーキテクチャ、ターゲット・アーキテクチャ、および変換されるアプリケーションに基づいて構成可能である。グローバルに割り振られるレジスタの最適の個数は、経験的に導出され、ターゲット・レジスタの個数、対象レジスタの個数、変換されるアプリケーションのタイプ、およびアプリケーション使用パターンの関数である。この個数は、一般に、ターゲット・レジスタの総数から、一時値用の十分なターゲット・レジスタが残されることを保証するある小さい数を引いたものになる。
【０１０２】
ＭＩＰＳ−Ｘ８６変換器およびＰｏｗｅｒＰＣ−Ｘ８６変換器など、多数の対象レジスタがあるが少数のターゲット・レジスタがある場合に、グローバルに割り振られるレジスタの個数が０になる。これは、Ｘ８６アーキテクチャが、固定されたレジスタ割振りの使用が、固定されたレジスタ割振りを全く使用しない場合より悪いコードを作ることが観察されたほどに少数のターゲット・レジスタを有するからである。
【０１０３】
Ｘ８６−ＭＩＰＳ変換器など、多数の対象レジスタおよび多数のターゲット・レジスタがある場合に、グローバルに割り振られるレジスタの個数（ｎ）は、ターゲット・レジスタの個数（Ｔ）の４分の３である。したがって、
Ｘ８６−ＭＩＰＳ：ｎ＝３／４＊Ｔ
Ｘ８６アーキテクチャは、少数の汎用レジスタを有するが、完全なＸ８６プロセッサ状態（たとえば、条件コード・フラグを含む）をエミュレートするためには多数の抽象レジスタが必要なので、多数の対象レジスタを有するものとして扱われる。
【０１０４】
ＭＩＰＳ−ＭＩＰＳアクセラレータなど、対象レジスタの個数とターゲット・レジスタの個数がほぼ同一である場合には、ほとんどのターゲット・レジスタが、グローバルに割り振られ、ごく少数だけが一時値用に予約される。したがって、
ＭＩＰＳ−ＭＩＰＳ：ｎ＝Ｔ−３
グループ・ブロック全体にまたがって使用される対象レジスタの総数（ｓ）が、ターゲット・レジスタの個数（Ｔ）以下である場合に、すべての対象レジスタが、グローバルに割り振られる。これは、レジスタ・マップ全体が、すべてのメンバ・ブロックにまたがって一定であることを意味する。（ｓ＝Ｔ）である特殊な事例（ターゲット・レジスタの総数とアクティブな対象レジスタの総数が等しいことを意味する）で、これは、一時計算用に残されたターゲット・レジスタがないことを意味し、この場合に、一時値は、同一の式ツリー内でさらなる使用を有しない対象レジスタ（その情報は、ライブネス分析を介して得られる）にグローバルに割り振られたターゲット・レジスタにローカルに割り振られる。
【０１０５】
グループ・ブロック作成の終りに、コード生成が、トラバーサルの順序でメンバ・ブロックごとに実行される。コード生成中に、各メンバ・ブロックのＩＲフォレストが、（再）生成され、デッド対象レジスタのリスト（そのブロックのライブネス情報に含まれる）が、ターゲット・コードを生成する前にＩＲフォレストを枝刈りするのに使用される。各メンバ・ブロックが変換される時に、その出口レジスタ・マップが、すべての後継者ブロックの入口レジスタ・マップ４０（既に固定されているものを除く）に伝搬される。ブロックは、トラバーサルの順序で変換されるので、これは、ホット・パスに沿ったレジスタ・マップ同期化を最小にすると同時に、ホット・パス変換をターゲット・メモリ空間内で連続的にするという効果を有する。基本ブロック変換と同様に、グループ・メモリ・ブロック変換は、入口条件の組すなわち、グループ・ブロックを作成する時の現在の作業条件に対して特殊化される。
【０１０６】
図７に、例示的実施形態に従う、変換器コード１９によるグループ・ブロック生成の例を示す。例のグループ・ブロックは、５つのメンバ（「Ａ」から「Ｅ」）を有し、当初は、１つの入口点（「Ｅｎｔｒｙ  １」。Ｅｎｔｒｙ  ２は、下で説明するように、集計を介して後に生成される）および３つの出口点（「Ｅｘｉｔ  １」、「Ｅｘｉｔ  ２」、および「Ｅｘｉｔ  ３」）を有する。この例では、グループ・ブロック作成のトリガ閾値が、４５０００の実行カウントであり、メンバ・ブロックの包含閾値が、１０００の実行カウントである。このグループ・ブロックの構成は、ブロックＡの実行カウント（現在は４５０４７）が、４５０００のトリガ閾値に達した時にトリガされ、その時点で、制御フロー・グラフの検索が、グループ・ブロック・メンバを識別するために実行された。この例では、１０００の包含閾値を超える５つのブロックが見つかった。メンバ・ブロックを識別したならば、順序付き深さ優先検索（プロファイリング・メトリックによって順序付けられる）が実行され、よりホットなブロックおよびそれの後継者が、まず処理され、これによって、クリティカル・パス順序付けを有するブロックの組が作られる。
【０１０７】
この段階で、グローバル・デッド・コード除去が実行される。各メンバ・ブロックが、レジスタの使用および定義について分析される（すなわち、ライブネス分析）。これによって、２つの形でコード生成がより効率的になる。第１に、ローカル・レジスタ割振りで、どの対象レジスタがグループ・ブロック内でライブであるか（すなわち、どの対象レジスタが現在メンバ・ブロックまたは後継者メンバ・ブロックで使用されるか）を考慮に入れることが可能になり、これは、スピルのコストを最小にするのに役立つ。デッド・レジスタは、復元の必要がないので、最初にスピルされる。さらに、特定の対象レジスタが定義され、使用され、再定義（上書き）されることをライブネス分析が示す場合に、その値を、最後の使用の後のいつにでも捨てることが可能である（すなわち、そのターゲット・レジスタを解放することが可能）。特定の対象レジスタが、定義され、中間の使用なしで再定義される（これは、対象コンパイラがデッド・コードを生成したことを意味するので、ありそうにない）ことをライブネス分析が示す場合に、その値の対応するＩＲツリーを捨てることが可能であり、ターゲット・コードは、それに関して生成されなくなる。
【０１０８】
グローバル・レジスタ割振りが次である。変換器１９は、頻繁にアクセスされる対象レジスタを、すべてのメンバ・ブロックにまたがって一定の固定されたターゲット・レジスタ・マッピングに割り当てる。グローバルに割り振られたレジスタは、スピル可能ではなく、これは、これらのターゲット・レジスタが、ローカル・レジスタ割振りに使用不能であることを意味する。ターゲット・レジスタより多数の対象レジスタがある時には、ある比率のターゲット・レジスタを、一時対象レジスタ・マッピング用に残さなければならない。グループ・ブロック内の対象レジスタの組全体をターゲット・レジスタにおさめることが可能な特殊な場合に、スピルおよびフィルが、完全に回避される。図７に示されているように、変換器は、グループ・ブロック（「Ａ」）の先頭に入る前に、グローバル・レジスタ・ストア２７からレジスタをロードするコード（「Ｐｒ１」）を埋め込み、このようなコードを、プロローグ・ロードと称する。
【０１０９】
ここで、グループ・ブロックは、ターゲット・コード生成の準備ができている。コード生成中に、変換器１９は、作業レジスタ・マップ（抽象レジスタとターゲット・レジスタの間のマッピング）を使用して、レジスタ割振りを記憶する。各メンバ・ブロックの始めでの作業レジスタ・マップの値が、そのブロックの関連する入口レジスタ・マップ４０に記録される。
【０１１０】
まず、グローバルに割り振られた抽象レジスタをロードするプロローグ・ブロックＰｒ１を生成する。この時点で、Ｐｒ１の終りの作業レジスタ・マップを、ブロックＡの入口レジスタ・マップ４０にコピーする。
【０１１１】
次に、ブロックＡを変換し、ターゲット・コードを、Ｐｒ１のターゲット・コードの直後に埋め込む。制御フロー・コードを埋め込んで、Ｅｘｉｔ  １の出口条件を処理するが、これは、エピローグ・ブロックＥｐ１（後で埋め込まれる）へのダミー分岐（後でパッチされる）からなる。ブロックＡの終りに、作業レジスタ・マップを、ブロックＢの入口レジスタ・マップ４０にコピーする。Ｂの入口レジスタ・マップ４０のこの固定は、次の２つの結果を有する。第１に、ＡからＢへのパスで同期化が不要である。第２に、他のブロック（すなわち、このグループ・ブロックのメンバ・ブロックまたは集計を使用する別のグループ・ブロックのメンバ・ブロック）からＢに入ることは、そのブロックの出口レジスタ・マップをＢの入口レジスタ・マップと同期化することを必要とする。
【０１１２】
ブロックＢは、クリティカル・パスで次にある。そのターゲット・コードが、ブロックＡの直後に埋め込まれ、その２つの後継者、ＣおよびＡを処理するコードが、次に埋め込まれる。第１の後継者、ブロックＣは、その入口レジスタ・マップ４０をまだ固定されておらず、したがって、作業レジスタ・マップが、単純にＣの入口レジスタ・マップにコピーされる。しかし、第２の後継者、ブロックＡは、その入口レジスタ・マップ４０を前に固定されており、したがって、ブロックＢの終りの作業レジスタ・マップとブロックＡの入口レジスタ・マップ４０が異なる場合がある。レジスタ・マップのすべての相違は、作業レジスタ・マップを入口レジスタ・マップ４０と一致させるために、ブロックＢからブロックＡへのパスに沿ったある同期化（「Ｂ−Ａ」）を必要とする。この同期化は、レジスタ・スピル、フィル、およびスワップの形をとり、上の１０個のレジスタ・マップ同期化シナリオに詳細に示されている。
【０１１３】
ここで、ブロックＣを変換し、ターゲット・コードを、ブロックＣの直後に埋め込む。ブロックＤおよびＥが、同様に変換され、連続して埋め込まれる。ＥからＡへのパスは、やはり、Ｅの出口レジスタ・マップ（すなわち、Ｅの変換の終りでの作業レジスタ・マップ）からＡの入口レジスタ・マップ４０へのレジスタ・マップ同期化を必要とし、これが、ブロック「Ｅ−Ａ」に埋め込まれる。
【０１１４】
グループ・ブロックを出て変換器１９に制御を返す前に、グローバルに割り振られたレジスタを、グローバル・レジスタ・ストアに同期化しなければならず、このコードを、エピローグ保存と称する。メンバ・ブロックを変換した後に、コード生成は、すべての出口点のエピローグ・ブロック（Ｅｐ１、Ｅｐ２、およびＥｐ３）を埋め込み、メンバ・ブロック全体の分岐ターゲットを固定する。アイソブロックとグループ・ブロックの両方を使用する実施形態では、制御フロー・グラフ・トラバーサルが、ブロックのアイソブロックではなく一意の対象ブロック（すなわち、対象コード内の特定の基本ブロック）に関して行われる。したがって、アイソブロックは、グループ・ブロック生成に透過的である。１つの変換を有する対象ブロックまたは複数の変換を有する対象ブロックに関して、特別な区別は行われない。
【０１１５】
例示的実施形態で、グループ・ブロック最適化とアイソブロック最適化の両方を有利に使用することが可能である。しかし、アイソブロック機構が、同一の対象コード・シーケンスについて異なる基本ブロック変換を作成する場合があるという事実が、どのブロックをグループ・ブロックに含めるかを判断する工程を複雑にする。というのは、含まれるブロックが、グループ・ブロックが形成されるまで存在しない場合があるからである。最適化の前に存在した特殊化されないブロックを使用して収集された情報を、選択およびレイアウトの工程で使用する前に適合させなければならない。
【０１１６】
例示的実施形態では、さらに、グループ・ブロック生成で入れ子になったループという特徴に対処する技法を使用する。グループ・ブロックは、最初に、１つの入口点すなわち、トリガ・ブロックの始めだけを有して作成される。プログラム内の入れ子になったループは、内側のループを最初にホットにし、その内側ループを表すグループ・ブロックが作成される。後に、外側ループがホットになり、内側ループならびに外側ループのすべてを含む新しいグループ・ブロックが作成される。グループ・ブロック生成アルゴリズムが、内側ループで行われる作業を考慮に入れるのではなく、その作業のすべてをやり直す場合に、深くネストしたループを含むプログラムは、ますます大きくなるグループ・ブロックを漸進的に生成し、各グループ・ブロック生成でのより多くのストレージおよびより多くの作業を必要とする。さらに、古い（内側）グループ・ブロックが、到達不能になり、したがって、利益をほとんどまたは全くもたらさなくなる可能性がある。
【０１１７】
例示的実施形態によれば、グループ・ブロック集計が、以前に作られたグループ・ブロックを追加の最適化されたブロックと組み合わせることを可能にするのに使用される。ブロックが新しいグループ・ブロックに含めるために選択されるフェーズ中に、前のグループ・ブロックに既に含まれている候補が、識別される。
【０１１８】
これらのブロックのターゲット・コードを埋め込むのではなく、集計が実行され、これによって、変換器１９が、既存グループ・ブロック内の適当な位置へのリンクを作成する。これらのリンクは、既存グループ・ブロックの途中にジャンプする場合があるので、その位置に対応する作業レジスタ・マップを実施しなければならず、したがって、そのリンクのために埋め込まれるコードに、必要に応じてレジスタ・マップ同期化コードが含まれる。
【０１１９】
基本ブロック・データ構造３０に保管された入口レジスタ・マップ４０は、グループ・ブロック集計をサポートする。集計は、他の変換されたコードが、入口点としてメンバ・ブロックの始めを使用して、グループ・ブロックの途中にジャンプすることを可能にする。そのような入口点は、現在の作業レジスタ・マップがメンバ・ブロックの入口レジスタ・マップ４０に同期化されることを必要とし、変換器１９は、これを、先祖の出口点とメンバ・ブロックの入口点の間に同期化コード（すなわち、スピルおよびフィル）を埋め込むことによって実装する。
【０１２０】
１実施形態で、一部のメンバ・ブロックのレジスタ・マップが、リソースを節約するために選択的に削除される。まず、グループ内のすべてのメンバ・ブロックの入口レジスタ・マップを無限に保管して、すべてのメンバ・ブロックの始めでグループ・ブロックへ入る（集計グループ・ブロックから）ことを容易にする。グループ・ブロックが大きくなった時に、一部のレジスタ・マップを削除して、メモリを節約することが可能である。これが起きた場合に、集計は、グループ・ブロックを効果的に領域に分割し、この領域の一部（すなわち、そのレジスタ・マップが削除されたメンバ・ブロック）は、集計入口からアクセス不能である。種々のポリシが、どのレジスタ・マップを保管するかを決定するのに使用される。１つのポリシは、すべてのメンバ・ブロックのすべてのレジスタ・マップを保管することである（すなわち、絶対に削除しない）。代替のポリシは、最もホットなメンバ・ブロックのレジスタ・マップだけを保管することである。代替のポリシは、後方分岐の宛先（すなわち、ループの始め）であるメンバ・ブロックのレジスタ・マップだけを保管することである。
【０１２１】
もう１つの実施形態で、各グループ・メンバ・ブロックに関連するデータに、すべての対象命令位置の記録されたレジスタ・マップが含まれる。これによって、他の変換されたコードが、メンバ・ブロックの先頭だけではなく、任意の点でグループ・ブロックの途中にジャンプすることが可能になる。というのは、いくつかの場合に、グループ・メンバ・ブロックに、そのグループ・ブロックが形成される時に検出されなかった入口点が含まれる場合があるからである。この技法は、大量のメモリを消費し、したがって、メモリ節約が問題でない時に限って適当である。
【０１２２】
グループ・ブロッキングは、頻繁に実行されるブロックまたはブロックの組を識別し、それらに対して追加の最適化を実行する機構を提供する。計算的により高価な最適化が、グループ・ブロックに適用されるので、その形成は、頻繁に実行されることがわかっている基本ブロックに制限されることが好ましい。グループ・ブロックの場合に、この余分な計算は、頻繁な実行によって正当化され、頻繁に実行される連続するブロックを、「ホット・パス」と称する。
【０１２３】
複数のレベルの頻度および最適化を使用し、変換器１９が、頻繁に実行される基本ブロックの複数のティアを検出し、ますます複雑になる最適化が適用される実施形態を構成することが可能である。代替案では、上で説明したように、２レベルだけの最適化が使用され、基本最適化が、すべての基本ブロックに適用され、さらなる最適化の単一の組が、上で説明したグループ・ブロック作成機構を使用してグループ・ブロックに適用される。
ブロック変換の概要
図８に、ランタイムに、変換されたコードの実行の間で変換器によって実行されるステップを示す。最初の基本ブロック（ＢＢＮ−１）は、実行を終了した時１２０１に、制御を変換器に返す１２０２。変換器は、最初の基本ブロックのプロファイリング・メトリックを増分する１２０３。次に、変換器は、最初の基本ブロックの実行によって返された対象アドレスを使用して、現在の基本ブロック（ＢＢＮ、これはＢＢＮ−１の後継者である）の前に変換されたアイソブロックについて、基本ブロック・キャッシュに照会する１２０５。後継者ブロックが、既に変換されている場合には、基本ブロック・キャッシュは、１つまたは複数の基本ブロック・データ構造を返す。次に、変換器は、後継者のプロファイリング・メトリックを、グループ・ブロック・トリガ閾値と比較する１２０７（これには、複数のアイソブロックのプロファイリング・メトリックを集計することを用いることが可能である）。閾値が満足されない場合には、変換器は、基本ブロック・キャッシュによって返されたアイソブロックのいずれかが、作業条件と互換である（すなわち、ＢＢＮ−１の出口条件と同一の入口条件を有するアイソブロック）であるかどうかを検査する。互換アイソブロックが見つかった場合に、変換を実行する１２１１。
【０１２４】
後継者プロファイリング・メトリックが、グループ・ブロック・トリガ閾値を超える場合には、互換アイソブロックが存在する場合であっても、上で説明したように新しいグループ・ブロックを作成し１２１３、実行する１２１１。
【０１２５】
基本ブロックが、アイソブロックを返さない場合、または返されたアイソブロックのどれもが互換でない場合には、現在のブロックを、上で述べたように、現在の作業条件に対して特殊化されたアイソブロックに変換する１２１７。ＢＢＮの復号の終りに、ＢＢＮの後継者（ＢＢＮ＋１）が静的に判定可能である場合に１２１９、拡張基本を作成する１２１５。拡張基本ブロックが作成される場合に、ＢＢＮ＋１の変換１２１７などを行う。変換が完了した時に、新しいアイソブロックを、基本ブロック・キャッシュに保管し１２１１、実行する１２１１。
共用コード・キャッシング
もう１つの好ましい実施形態で、変換器１９に、共用コード・キャッシュ機構を含めることが可能であり、この共用コード・キャッシュ機構は、たとえば、特定の対象プログラムに対応するターゲット・コード２１および変換構造を変換器１９の異なるインスタンスの実行またはインスタンスの間で共用することを可能にすることが可能である。変換器「インスタンス」は、変換器の特定の実行であり、１つの対象プログラムの１つの変換された実行を意味する。下でさらに述べるように、そのような共用コード・キャッシングは、専用のコード・キャッシュ・サーバによって容易にすることが可能であり、このコード・キャッシュ・サーバは、その実行の始めおよび終りと、実行中に、対象コードが変更される時（対象ライブラリがロードされる時など）に必ず、変換器１９と相互作用する。
【０１２６】
図９に、例示的実施形態による共用コード・キャッシング工程の顕著な態様を示す。最初のステップ１０１で、変換器１９は、対象コードの一部Ｓ１をターゲット・コードＴ１に変換する。ターゲット・コードＴ１の再利用を提供するために、変換器１９は、そのターゲット・コードＴ１をキャッシングする、ステップ１０３。判断菱形１０５で、変換器１９は、対象コードの次の部分Ｓ２と、以前にステップ１０３でキャッシングされたターゲット・コードＴ１の間の互換性を判定する。判断菱形１０５に関して図示されているように、キャッシングされたターゲット・コードＴ１と対象コードの新しい部分Ｓ２の間に互換性が存在する場合には、キャッシュ・ターゲット・コードＴ１が取り出され、実行され、ステップ１０９、これによって、新しい対象コード部分Ｓ１を変換するという重荷および必要が除去される。互換性が存在しない場合には、ステップ１１１に示されているように、対象コードの次の（新しい）部分をターゲット・コードに変換し、さらに処理する。
【０１２７】
図９の工程の例示的で有利な適用において、変換器１９は、第１の対象プログラムの実行中に作られたすべてのターゲット・コードを一時ストレージに保持し、その後、そのターゲット・コードのすべてを、その実行の終りにキャッシングする。その後、変換器１９は、第２の対象プログラムの対象コードの変換中に互換性判定を実行する。
【０１２８】
ステップ１０５に示された対象コードの新しい部分とキャッシングされたターゲット・コードの間の互換性の判定は、複数の異なる方法に従って実行することが可能である。例示的実施形態では、変換器は、キャッシュ・キー・データ構造を使用して、現在の対象コード・シーケンスが以前に変換された対象コード・シーケンスと同一であるかどうかに関して、特定のキャッシュ・ユニットが現在の対象コード・シーケンスと互換であるかどうかを判定する。変換器１９は、新しいシーケンスのキャッシュ・キー・データ構造をすべての以前に生成されキャッシングされたターゲット・コード・シーケンスのキャッシュ・キー・データ構造と比較することによって、新しい対象コード・シーケンスが以前にキャッシングされたターゲット・コードを使用することが可能であるかどうかを確かめるために検査する。正確な一致が、変換（ターゲット・コード）が再利用可能であることを示す。
【０１２９】
実装された１実施形態で、キャッシュ・キー・データ構造に、（１）対象コード・シーケンスを含むファイルの名前または他の識別子、（２）そのファイル内の対象コード・シーケンスの位置（すなわち、オフセットおよび長さ）、（３）そのファイルの最終変更時刻、（４）キャッシングされた変換構造を生成した変換器のインスタンスのバージョン番号、および（５）対象コードがロードされた対象メモリ内のアドレスが含まれる。この実施形態では、変換器１９は、めいめいのキャッシュ・キーのすべての構成要素を順番に比較することによって、互換性を判定する。同一でないすべての値が、非互換性を示す。
【０１３０】
別のまたは代替の実施形態で、キャッシュ・キー・データ構造３９に、キャッシュ・ユニット３７が表すすべての対象命令の完全なコピーが含まれ、この実施形態では、変換器は、キャッシュ・ユニット３７の対象命令シーケンス全体を、変換される対象コード・シーケンスと比較し、各対象命令が同一であることを検査することによって、キャッシュ・ユニット３７の互換性を判定する。
【０１３１】
もう１つの実施形態で、変換器によるキャッシュ互換性の判定は、ハッシュ関数を使用することによって容易にされる。その場合に、キャッシュ・キー・データ構造に、対象コード・シーケンスの数値ハッシュが含まれる。変換器は、対象コード・シーケンス全体に一定の再現可能なハッシュ関数を適用する。このハッシュ関数は、ハッシュ数と称する、シーケンスの数値表現を生成する。そのような実施形態で、変換器は、変換された対象コード・シーケンスおよび現在の対象コード・シーケンスの各々のハッシュ数の算術比較を単純に実行することによって、互換性を判定する。
【０１３２】
このハッシュ関数技法は、めいめいの変換器インスタンスの以前に使用されたバージョンと現在使用されているバージョンとの互換性、またはたとえばより複雑なシステムの２つの異なるプロセッサに常駐する、異なる変換器インスタンス・バージョンの互換性を判定するのに使用することも可能である。その場合に、変換器・バージョン互換性の変換器による判定は、実行可能変換器・ファイルの数値ハッシュによって容易にされ、このハッシュ数は、キャッシュ・キーに保管される。そのような実施形態で、変換器・ハッシュ数は、変換器の各バージョンの実際のバイナリ実行可能ファイルを構成するバイト・シーケンスにハッシュ関数を適用することによって生成される。
【０１３３】
種々の実施形態によれば、変換される「対象コードの部分」は、下でさらに述べるように、基本ブロックまたは基本ブロックより大きい命令の他のシーケンスを含めることが可能なコード・シーケンスである。図１０に、各キャッシュ・ユニット内で特定のコード・シーケンスを表す共用コード・キャッシング工程を示す。
【０１３４】
図１０に示された工程によれば、変換器１９は、ステップ１２１に示されているように、第１のコード・シーケンスＣＳ１をターゲット・コードＴＣ１に変換する。次に、変換器１９は、ステップ１２３に示されているように、コード・シーケンスＣＳ１に対応するターゲット・コード・ブロックＴＢ１をインデクシングするキャッシュ・キーＫ１を生成する。ステップ１２４で、変換器１９は、ターゲット・ブロックＴＣ１を、それに関連するキーＫ１と共にキャッシュ・ストレージに保管する。ステップ１２５で、変換器１９は、第２のコード・シーケンスＣＳ２の処理を開始し、まず、そのシーケンスのキャッシュ・キーＫ２を生成する。次に、比較ステップ１２７で、変換器１９は、キャッシュ・キーＫ２を、Ｋ１を含む、キャッシュ２９に以前に保管されたコード・シーケンスに関連するキーと比較する。キャッシュ・キーＫ１がキャッシュ・キーＫ２と一致する場合に、ステップ１２９に示されているように、キャッシュ・キーＫ１に対応するターゲット・コード・ブロックＴＣ１が、変換器１９によってキャッシュ２９から取り出され、実行される。ステップ１３１に示されているように、フローは、次にステップ１３３に進み、ここで、変換器１９が、コード・シーケンスＣＳ３の処理を開始し、まず、そのシーケンスのキャッシュ・キーＫ３を生成し、次に、一致についてキャッシュ・キー、…Ｋ１、Ｋ２…のインデックスを検査する。ステップ１２７で、Ｋ１がＫ２と一致しない場合に、第２のコード・シーケンスが、ターゲット・コードＴＣ２に変換され、その後、ステップ１３５および１３６に示されているように、このターゲット・コードＴＣ２がキャッシングされる。
【０１３５】
例示的実施形態では、各キャッシュ・ユニットに、対象コード・シーケンスを表すのに必要なすべての変換構造が含まれる。コード・シーケンスは、これまでに定義された基本ブロック、またはそれに関してコードが生成される命令のより大きいシーケンスとすることが可能である。そのようなより大きいシーケンスの場合に、そのコード・シーケンス内のすべての基本ブロックに関連するすべての関連するデータが、同一のキャッシュ・ユニット内に保たれる。
【０１３６】
そのような例示的実施形態で、キャッシュ・ユニットに保管されるデータ構造に、次が含まれる。
（ａ）ＢａｓｉｃＢｌｏｃｋオブジェクト  −  各ＢａｓｉｃＢｌｏｃｋオブジェクトは、対象アドレスをあるデータに関連付ける。このデータに、次が含まれる。
【０１３７】
・その対象アドレスのプロファイル情報（たとえば、実行カウント）
・同等のターゲット・コード（存在する場合に）へのポインタ
・ポイントされるターゲット・コードが、基本ブロック・ターゲット・コードまたはグループ・ブロック・ターゲット・コードのどちらであるか
・「後継者情報」、ブロックがどのように終わるかがそれに依存する実際の内容
・コード・シーケンスが無条件ジャンプで終わる場合に、後継者情報は、次に実行されるＢａｓｉｃＢｌｏｃｋオブジェクトをポイントする
・コード・シーケンスが計算型ジャンプ（たとえば、「リンク・レジスタへの分岐」）で終わる場合に、次に後継者情報は、後継者キャッシュをポイントし、この後継者キャッシュは、対象アドレスを基本ブロック・アドレスにマッピングする。計算型ジャンプで終わる各ブロックは、それ自体の後継者キャッシュを有する。
【０１３８】
・コード・シーケンスが分岐で終わる場合に、後継者情報は、分岐が採用される／採用されない場合の次に実行される対象アドレスを表す基本ブロックをポイントする
（ｂ）ターゲット・コード  −  グループ・ブロックと基本ブロックの両方
（ｃ）グループ・ブロック情報  −  グループ・ブロック生成の後に、グループ・ブロックを経時的に増大させ変更することを可能にするために維持される
（ｄ）ブロック・ディクショナリ  −  これは、基本ブロックへの対象アドレスのマップである。キャッシュ・ユニット内のすべての基本ブロックが、ブロック・ディクショナリ内にエントリを有する。
【０１３９】
後継者情報では、次に実行されるＢａｓｉｃＢｌｏｃｋが現在のキャッシュ・ユニットの外にある場合に、ある特殊なフラグ（たとえば、ヌル・ポインタ）を使用して、ある特殊なアクションを行わなければならないことを示す。ここで、次の基本ブロックのアドレスをハードワイヤすることは不可能である。というのは、宛先ブロックが、使用可能でない場合があり、したがって、適当な後継者を見つけるために、システムで使用可能なすべてのキャッシュ・ユニットを検索することによって宛先ブロックを入手しなければならないからである。参照によって本明細書に組み込まれている同時係属の特許出願＿＿＿＿で開示されたＰａｒｔｉｔｉｏｎｓ機構が、対象アドレスに基づいてキャッシュ・ユニットを分割し、その結果、対象アドレスの特定の範囲内のコードを表すすべてのＢａｓｉｃＢｌｏｃｋが同一のキャッシュ・ユニットに置かれるようにする（対応する後継者キャッシュ、ターゲット・キャッシュ、グループ・ブロック情報、およびブロック・ディレクトリと同様に）のに使用可能な機構の１つである。しかし、他の代替機構を使用することが可能である。
【０１４０】
議論しているキャッシュ・ユニット構造の特定の例のすべてのデータ構造に、やはり同一のキャッシュ・ユニット内にあるデータへのポインタだけを含めることが可能である。したがって、キャッシュ・ユニット間のオブジェクトの参照は、特殊な作業を必要とする。これは、宛先キャッシュ・ユニットが使用可能であることに頼ることが不可能であるからである。この理由から、グローバル・ブロックは、その全体が単一のキャッシュ・ユニットに含まれる。
【０１４１】
キャッシュ・ユニット３７の例を、図１１に示す。図１１のキャッシュ・ユニット３７には、特に、１つまたは複数のブロック変換４１と、これらのブロック４１に関連する後継者リスト４３が含まれる。この形で、各キャッシュ・ユニット３７が、独立であり、これは、キャッシュ・ユニット３７内の変換構造が、そのキャッシュ・ユニットの外の変換構造の存在に依存しないことを意味する。というのは、個々のキャッシュ・ユニットに、キャッシュ・サーバ３５から独立にロードし、アンロードすることが可能であるからである。そのようなキャッシュ・ユニット３７に、特定の対象コード・シーケンスを表すのに必要なすべての変換構造が含まれ、この対象コード・シーケンスは、後継者コード・シーケンスを除外することが可能である。これに関して、「対象コード・シーケンス」に、制御フローに関してシーケンシャルであるが、対象アドレスに関して不連続である可能性がある複数の対象命令を含めることが可能である。言い換えると、キャッシュ・ユニット３７に、少なくとも１つの変換されたブロック（すなわち、特定の対象コード・シーケンスを表すターゲット・コード・シーケンス）と、その変換されたブロックが依存するすべての変換構造が含まれる。たとえば、キャッシュ・ユニット３７に、変換されたブロック４１  Ａ、４１  Ｂ、および４１  Ｃが含まれる実施形態で、これらのブロックの後継者リスト４３は、必要な変換構造であるが、後継者ブロック４９自体は不要である。
【０１４２】
種々の実施形態で、変換器１９が、種々のスコープの追加のキャッシュ・ユニット・データ構造を定義することが可能である。たとえば、変換器１９が、対象プログラムが自己書換式でないことを知っている時に、対象プログラムおよびそれに関連するすべてのライブラリを、単一のキャッシュ・ユニットにグループ化することが可能である。変換器１９は、さらに、次のタイプのキャッシュ・ユニットのうちの１つまたは複数を確立することが可能である：（ａ）各個々の対象命令を別々のキャッシュ・ユニットにすることが可能であり、（ｂ）各基本ブロックを別々のキャッシュ・ユニットにすることが可能であり、（ｃ）同一の開始対象アドレスに対応するすべてのブロックを単一のキャッシュ・ユニットにグループ化することが可能であり、（ｄ）キャッシュ・ユニットが対象コード・アドレスの別個の範囲を表すことが可能であり、（ｅ）各対象ライブラリを別々のキャッシュ・ユニットにすることが可能であり、（ｆ）各対象コード・アプリケーションが、そのアプリケーションのすべてのターゲット・コード（実行可能ファイルおよびすべてのライブラリ）を含む単一のキャッシュ・ユニット内で表される。変換器１９は、さらに、特定の変換要件およびターゲット環境に応じて、キャッシュ・ユニットの粒度のレベルを変更することが可能である。
【０１４３】
もう１つの有利な例として、変換器１９が応用例を見出すいくつかの対象オペレーティング・システム２０は、不変ライブラリ用に予約されたメモリの領域を有し、各不変ライブラリは、必ず同一の対象アドレスにロードされる。このメモリの領域は、単一のキャッシュ・ユニットとして扱われる。たとえば、ＭａｃＯＳオペレーティング・システムは、不変共用ライブラリ用に予約された予約済みメモリ範囲（０ｘ９０００００００〜０ｘＡ０００００００）を有し、ＭａｃＯＳアーキテクチャから変換するように構成された変換器は、ＭａｃＯＳ共用ライブラリ領域全体を単一のキャッシュ・ユニット内で表現する。キャッシュ・ユニットに複数の対象ライブラリが含まれる、適当な場合に、キャッシュ・ユニットのキャッシュ・キーに、その領域にロードされるすべてのライブラリのファイル変更時刻が含まれる。このキャッシュ・ユニットに含まれる対象ライブラリのいずれかの変更は、そこに含まれる変換構造を、変換器の将来のインスタンスについて使用不能にする。基礎になるライブラリの１つが変更された場合に、後続の変換器インスタンスは、そのキャッシュ・ユニット（すなわち、ＭａｃＯＳ共用ライブラリ領域）の変換構造を再作成しなければならない。新しい変換構造は、ライブラリの新しい構成（すなわち、そのライブラリに含まれる新しい対象コード）を反映した対応するキャッシュ・キーを有する。
【０１４４】
これまでに説明した共用コード・キャッシュ方法は、複数の異なるアーキテクチャ的方式で実装することが可能である。図１２〜１６に示されたものなどの共用コード・キャッシングを実装する種々の実施形態で、共用コード・キャッシュ・ストレージ機能２９は、特定の対象プログラムに対応するターゲット・コード２１および変換構造（キャッシュ・ユニット）を変換器１９の異なる実行またはインスタンスの間で共用することを可能にする。変換器「インスタンス」は、変換器の特定の実行であり、１つの対象プログラムの１つの変換された実行を意味する。
【０１４５】
たとえば、図１２に示されているように、共用コード・キャッシュ２９は、専用のコード・キャッシュ・サーバ３５によって容易にされ、このコード・キャッシュ・サーバ３５は、その実行の始めおよび終りと、実行中に、対象コードが変更される時（対象ライブラリがロードされる時など）に必ず、変換器１９と相互作用する。図１２の実施形態では、キャッシュ・サーバ３５が、変換器１９と同一のシステムまたはターゲット・アーキテクチャ３６に常駐する。他の実施形態で、キャッシュ・サーバ３５を、変換器のサブシステムとすることが可能である。
【０１４６】
図１３に、キャッシュ・サーバ３５が変換器１９と異なるシステム３２に常駐する実施形態を示す。その場合に、サーバ・システム３２のアーキテクチャを、ターゲット・アーキテクチャ３６と異なるものにすることが可能である。
【０１４７】
図１４に、図１の変換システムが、異なるシステム３２で動作しているキャッシュ・サーバ３５と協力する実施形態を示す。この場合に、キャッシュ・サーバ３５は、変換器１９がその上で動作しているものと異なるプロセッサ３１および異なるオペレーティング・システム３３で動作する。
【０１４８】
図１５に示された共用キャッシュ技法の代替実施形態では、キャッシュ・サーバ３５が、異なるシステム６３および６５で動作する変換器インスタンス１９ａと１９ｂの間でめいめいのキャッシュ２９Ａ、２９Ｂ、および２９Ｃ内の変換されたコード・ストアを共用する接続された工程のネットワークであり、システム６３および６５のターゲット・アーキテクチャは同一である。システム６３および６５は、たとえば、ネットワーク接続されたデスク・トップ・コンピュータの対とすることが可能である。単一のキャッシュ・サーバが、変換器１９の任意の個数の異なる構成にキャッシュをサービスすることが可能であるが、特定のキャッシュ２９を変換器１９の互換構成の間だけで共用することが可能である。
【０１４９】
図１４に示された共用キャッシュ技法の１実施形態で、キャッシュ・サーバ３５は、変換器工程からの照会に能動的に応答する専用の工程である。代替実施形態で、キャッシュ・サーバ３５は、キャッシュ・ユニットのファイル・ディレクトリまたはデータベースなど、受動的なストレージ・システムである。
【０１５０】
さらに、図１４の例示的実施形態では、変換器１９が、対象プログラムが終わる時にディスク上のファイルとしてキャッシュ・ユニットを保管することと、さらに、キャッシングされた対象コード・シーケンスに関連するすべてのキャッシュ・キー構造を含むインデックス・ファイルを維持することによって、キャッシングされた変換構造を永続的ストアに保存する。たとえば、そのような実施形態の１つで、コード・キャッシュに、キャッシュ・サーバ・オペレーティング・システム３３のファイル・システム内のファイルのディレクトリが含まれ、各キャッシュ・ユニット３７は、キャッシュ・ディレクトリ構造内の単一のファイルとして保管される。図１４のシステムのもう１つの実施形態で、永続的ストレージは、キャッシングされた変換構造を「所有し」、変換器１９による要求に応答してキャッシュ・ユニットを変換器インスタンスに分配する永続的サーバ工程によって実装される。
【０１５１】
したがって、例示的な共用コード・キャッシュ方法の実装で、対象プログラムの変換が、変換器１９がまだ変換を有しない対象コード・シーケンスに達した時に、変換器１９は、互換コード・キャッシュについてキャッシュ・サーバ３５を検査する。互換キャッシュが見つかった場合に、変換器１９は、そのキャッシュをロードし、このキャッシュには、ターゲット・コード２１および変換構造が含まれる。コード・キャッシュには、潜在的に、図６および７に関してこれまでに説明したグループ・ブロックなどの最適化されたターゲット・コードを含む、対象プログラムの前の変換された実行の過程で作成された変換されたコード２１のすべてが含まれる。これによって、後の変換器実行を、以前の実行の努力にピギーバックすることが可能になり、対象コードのより大きいセクションが、既に変換され、おそらくは最適化されている可能性があり、これによって、スタートアップ時間が減り、変換コストが減り、性能が高まる。
【０１５２】
共用キャッシングは、図１２の変換器１９の異なるインスタンス、インスタンス１９ａおよび１９ｂ、が互いの努力から利益を得ることを可能にする。具体的に言うと、共用キャッシングは、ある変換器インスタンスで作成された変換構造を別の変換器インスタンスで再利用することを可能にする。この文脈での「変換構造」は、変換器１９が対象コードを表し、管理し、実行するのに使用する、生成されたターゲット・コード（すなわち、特定の対象コード・シーケンスの変換）および他のデータを指す。そのような変換構造の例が、図１１に関して説明したものであり、この変換構造３７には、基本ブロックを含む変換されたコードおよび後継者リストが含まれる。
【０１５３】
共用キャッシングは、後の変換器インスタンスが同一の対象プログラムまたは共通の対象コード（たとえばシステム・ライブラリ）を有する異なる対象コードのいずれかを実行する時に、変換の結果を再利用することを可能にする。共用キャッシングは、後の変換器インスタンスが同一の対象コード・シーケンスに出会った場合に、以前の変換器インスタンスで作成された変換構造を再利用することを可能にする。以前の変換器インスタンスが、特定の対象コード・シーケンスに出会い、その後、後の変換器インスタンスが、同一の対象コード・シーケンスに出会う場合に、共用キャッシングは、後の変換器が、以前の変換器インスタンスによって作成された変換構造を使用することを可能にする。言い換えると、共用キャッシングは、特定の対象コード・シーケンスの変換（すなわち、キャッシュ・ユニット）が、その変換を作成した変換器インスタンスの寿命を超えて永続することを可能にする。
【０１５４】
キャッシングされた変換に関して、対象コードを、次の２つのカテゴリに分類することが可能である：（１）対象バイナリ、静的にリンクされたライブラリ、リンカ、およびランタイムにロードされるすべてのライブラリを含む、ディスクからメモリにロードされる実行可能コードと、（２）ランタイム・コンパイルのためにオン・ザ・フライで生成される対象コード、トランポリン、または他の形の動的に生成される対象コード（すなわち、自己書換型コード）。共用キャッシング技法は、本明細書で「静的」コードと称する、対象命令シーケンスの第１のカテゴリに関して特定の応用例を見出す。静的対象コードは、（ａ）同一アプリケーションの複数の実行、および（ｂ）複数のアプリケーション（たとえば、システム・ライブラリ）にまたがる正確に同一の対象命令シーケンスを含む可能性が高い。静的対象コードに対応するキャッシュ・ユニットを、本明細書では静的キャッシュ・ユニットと称する。対照的に、共用キャッシング技法の文脈で、対象コードがランタイムに変化するプログラムを、「動的」と称する。
【０１５５】
共用キャッシングの最適化の１つで、変換器インスタンス実行の終りに、変換器１９が、対象プログラムのどの部分が静的対象コードからなるかを判定し、共用キャッシング技法の適用をこれらの静的部分に制限する。そのような実施形態で、変換器インスタンス実行の終りに、静的コードに対応する変換構造だけがキャッシングされ、動的コードに対応する変換構造は破棄される。
キャッシュ・エボリューション（Ｃａｃｈｅ  Ｅｖｏｌｕｔｉｏｎ）
キャッシュ２９が変換器実行の終り（すなわち、変換されたプログラムが終了する時）に更新される実施形態で、変換の実行の現在の本体をサーバ３５によって現在保管されているコード・キャッシュと比較するようにキャッシュ・サーバ３５を構成することが可能である。そのような構成では、現在の実行のコード・キャッシュが、以前に保管されたバージョン「よりよい」場合に、サーバは、将来の使用のために現在の実行からキャッシュ・ユニットを保管する。変換器インスタンスからキャッシュ２９に変換をコピーする工程（すなわち、インスタンスの変換がサーバよりもよい時）を、「パブリッシュする（ｐｕｂｌｉｓｈｉｎｇ）」と呼ぶ。したがって、キャッシュ２９に保管されたコードの品質は、経時的に改善される。この技法の工程および結果を、「キャッシュ・エボリューション」と称する場合がある。
【０１５６】
変換器インスタンスが、当初に、キャッシュから構造を取り出す場合であっても、そのインスタンスの実行が、新しい対象コード・シーケンスの変換を引き起こし、したがって、新しい変換構造を作成させる場合がある。そのような変換器インスタンスが終了する時に、変換構造のそれ自体の組が、キャッシュに保管された対応する組より完全である場合がある。
【０１５７】
図１６の例示的工程によれば、変換器の第１のインスタンス実行（ステップ２０１）が実行され、その後、ステップ２０３で、そのキャッシュ・ユニットＣ１がキャッシングされる。次に、変換器１９の第２のインスタンスが、第２のプログラムを実行し、キャッシュ・ユニットＣ２を生成する、ステップ２０５。次に、変換器１９の第２のインスタンスが、その実行の終りに、その変換構造Ｃ２を、キャッシュ２９に保管された変換構造Ｃ１と比較し、ある適当な判断基準に従って、作られたばかりの変換がキャッシュ２９で使用可能な変換「よりよい」か否かを判定する。たとえば、あるコード・キャッシュが別のコード・キャッシュよりよいか否かの判定は、変換された対象命令の個数に基づく、適用された最適化の個数に基づく、または生成されたコードの品質を評価するアルゴリズムの実行によるものとすることが可能である。ステップ２０９に示されているように、Ｃ２がＣ１よりよい場合に、キャッシュ構造Ｃ２が、キャッシュ２９にロードされ、構造Ｃ１を置換する。
【０１５８】
変換器１９がキャッシュ・エボリューションを使用しない実施形態では、実行の終りに、変換器インスタンスが、すべての新しい変換構造（すなわち、最初にキャッシュから借りてきたものでない変換構造のすべて）を破棄する。
【０１５９】
代替実施形態で、変換器インスタンスが、実行の終りだけでなく、実行中の選択された時にキャッシュ・サーバ、たとえば３５に、変換構造をパブリッシュするようにシステムを構成することが可能である。これによって、たとえば、複数の変換器インスタンスＴ１、Ｔ２、…、Ｔｎを並列に実行することが可能である図１７などのシステムで、変換されたプログラムの終了の前に、変換構造を他の変換器インスタンスから使用可能にすることが可能になる。選択されたパブリッシュ時刻または「キャッシュ同期化点」に、（１）変換されたアプリケーションが多くのことを行っていない「アイドル」期間中、（２）閾値個数の変換構造が生成された後（たとえば、変換器インスタンスが、１メガバイトなどのある単位のターゲット・コードを生成するたびにパブリッシュする）、および（３）新しい変換器インスタンスが、共用キャッシュ内にはないが、変換器インスタンスの現在動作しているインスタンスに存在することがわかっている変換構造を必要とする時を含めることが可能である。
並列変換
キャッシュ・サーバ３５の種々の実施形態で、サーバ３５が変換器インスタンスから／変換器インスタンスにコード・キャッシュを送る／受け取るのにビジーでないアイドル期間中に、サーバ３５を、コード・キャッシュ２９を最適化するようにさらに構成することが可能である。そのような実施形態では、キャッシュ・サーバ３５が、次の最適化のうちの１つまたは複数を実行して、コード・キャッシュを変換する：（ａ）特定のキャッシュ・ユニットの検索をより効率的にするためにキャッシュ・ディレクトリ構造を再構成する、（ｂ）同一対象コードの後続のより最適化された変換によって取って代わられた変換を削除する、（ｃ）キャッシュ・サーバ３５のハードウェア・キャッシュ性能を高めるために、頻繁に要求されるキャッシュ・ユニットが互いの近くに位置するようにコード・キャッシュを再配置する（すなわち、サーバ・システム３２のハードウェア・キャッシュでキャッシュ・サーバ３５によって生成されるハードウェア・キャッシュ・ミスの回数を減らす）、（ｄ）キャッシングされた変換の高価な最適化を実行する（キャッシュ・サーバによるオフライン最適化は、変換器インスタンスにおける変換コストまたは性能ペナルティをこうむらない）、（ｅ）変換器インスタンスによってまだ変換されていないが、変換器インスタンスが出会うと期待される対象コードを変換する（すなわち、オフライン予測変換）。
共用メモリ
共用キャッシング技法のもう１つの最適化は、共用メモリを使用して、本来読取専用である（すなわち、その内容が、変更されるとしてもまれにしか変更されない）キャッシングされた変換構造にアクセスすることである。生成されたターゲット・コード・シーケンスなど、キャッシュ・ユニットに保管された変換構造のかなりの部分が、変換器インスタンスの寿命全体を通じて読取専用である可能性があり、生成されたならば、ターゲット・コード・シーケンスは、めったに破棄されず、変更されない（後の最適化された変換によって包摂される場合はあるが）。実行カウントおよび分岐宛先プロファイリング・データなどの他のキャッシュ・ユニット・コンポーネントは、変換器の実行全体を通じて定期的に更新されるので、頻繁に変更されることが期待される。同一のキャッシュ・ユニット構造が、たとえば図１７のように複数の変換器インスタンスによって同時に使用される場合に、これらの変換器の読取専用コンポーネントに、共用メモリとしてアクセスすることが可能である。この最適化は、単一のターゲット・システムで動作する複数の変換器による物理メモリ使用量全体を減らすことが可能である。
【０１６０】
例示的な共用メモリ・アプリケーション、変換器１９は、コード・キャッシュ・ファイルを共用メモリ領域にロードする。キャッシュ・フィルは、コピーオンライト・ポリシを使用して共用されることが好ましい。コピーオンライト・ポリシの下では、キャッシュ・ファイルが、まず、すべての動作中の変換器工程にまたがって共用され、「コピーオンライト」は、特定の変換器インスタンスが何らかの形で（たとえば、ブロックの実行カウントを増分する）キャッシングされた構造を変更する時に、その時点でのキャッシュの変更された部分が、その特定の実行に排他的になり、したがって、変更された領域を含むメモリ領域が、もはや共用不能になることを意味する。
【０１６１】
例示的な応用例で、キャッシュ２９に、変換器１９が動作する時に常に更新されるプロファイリング・データ構造と、生成された後に変更されないままになる他のデータ構造（ターゲット・コードなど）が含まれる。変換器１９がその上で動作するオペレーティング・システムは、たとえば、共用の単位として４ｋｂメモリ・ページを提供する。大きい（１ＭＢ）キャッシュを、複数の工程にまたがって共用することが可能であり、キャッシュに対するすべての変更が、その変更を含むページをそのプロセスにプライベートにする（そのページがコピーされ、プライベート・コピーだけが変更される）。これによって、キャッシュ２９の大多数を共用されたままにすることが可能になると同時に、変更可能プロファイリング・データが、各工程にプライベートにされる。キャッシュ２９は、キャッシュ２９にまたがってプロファイリング・データを分散させるのではなく、ある範囲のページを変更可能プロファイリング・データ専用にするように故意に配置されることが好ましい。これによって、ローカル変更によってプライベートにされるメモリの量が減る。
分散キャッシング
下で説明する実施形態では、共用キャッシング技法が、互いに相互作用する、１つまたは複数の変換器インスタンスおよび１つまたは複数のサーバ工程を含むキャッシュ・システムとして実行される。上で説明した実施形態に加えて、他の実施形態で、キャッシュ・サーバは、ルックアップ動作および保管動作に関する対応する周知の技法と共に、階層キャッシュおよび分散キャッシュの分野で周知の複数の方法論のいずれかに従って、キャッシュの分散システムに編成される。
【０１６２】
図１５に示されたものなどの複数のキャッシュを含むキャッシュ・システムでは、めいめいのキャッシュの編成で種々の技法を使用できる。そのような技法に、スコープド・キャッシュ（ｓｃｏｐｅｄ  ｃａｃｈｅ）、レンジド・キャッシュ（ｒａｎｇｅｄ  ｃａｃｈｅ）、およびキャッシュ・ポリシー（以下、方針ともいう）（ｃａｃｈｅ  ｐｏｌｉｃｙ）が含まれる。これらの技法を組み合わせて使用することが可能である。
【０１６３】
スコープド・キャッシュを使用するキャッシュ・システムの実施形態では、各キャッシュが、異なるキャッシュ・スコープを有する。スコープド・キャッシュは、変換器インスタンスの特定の組からのみアクセス可能である。特定のキャッシュのキャッシュ・スコープは、どの変換器インスタンスがそのキャッシュにアクセス可能であるかを定義する。たとえば、１実施形態で、各キャッシュが、「プライベート」または「グローバル」のいずれかのキャッシュ・スコープを有する。プライベート・キャッシュは、それを作成した変換器インスタンスによってのみアクセスが可能であり、その内容は、その変換器インスタンスが終了した後には永続しない。グローバル・キャッシュは、すべての変換器インスタンスによってアクセス可能であり、これは、複数の変換器が、そのキャッシュからキャッシュ・ユニットを取り出し、そのキャッシュにキャッシュ・ユニットを保管することが可能であることを意味する。グローバル・キャッシュの内容は、特定の変換器インスタンスの終了を超えて永続する。
【０１６４】
スコープド・キャッシュ・システムの実施形態に、（ａ）アプリケーション、（ｂ）アプリケーション・タイプ、（ｃ）アプリケーション・ベンダ、または他のデータを含む他の可能なキャッシュ・スコープ値を含めることができる。「アプリケーション固有」キャッシュ・スコープを有するキャッシュは、同一の対象アプリケーションを実行している変換器インスタンスのみによってアクセスできる。「アプリケーション」キャッシュ・スコープを有するキャッシュは、同一タイプのアプリケーション（たとえば、対話型、サーバ、グラフィカル）を実行している変換器インスタンスのみによってアクセスできる。「アプリケーション・ベンダ」キャッシュ・スコープを有するキャッシュは、同一ベンダによって作られたアプリケーションを実行している変換器インスタンスのみによってアクセスできる。
【０１６５】
レンジド・キャッシュを使用するキャッシュ・システムの実施形態で、各キャッシュに、対象アドレス範囲が関連し、キャッシュには、その範囲内の開始対象アドレスを有する変換を含むキャッシュ・ユニットだけが保管される。
【０１６６】
複数のキャッシュを含むキャッシュ・システムで、構造および各々のキャッシュを使用する形の制約を変更する異なるキャッシュ方針を実施することが可能である。キャッシュ方針に、挿入ポリシおよび対応する探索方針が含まれる。図１７に示されているように、キャッシュ・システムがキャッシュ・ユニット３７を保管する時に、挿入ポリシ５１が、そのキャッシュ・ユニットが保管されるキャッシュＡ、Ｂを定義する。図１８に示されているように、キャッシュ・システムが、キャッシュ・ユニット３７を取り出すことを試みる時に、探索方針５３が、複数のキャッシュＡ、Ｂに照会する順序を決定する。
【０１６７】
たとえば、表３に、挿入方針、探索方針、およびキャッシュ・システムに対するキャッシュ方針の影響に関する、キャッシュ方針の３つの例を示す。
【０１６８】
【表３】
0005419325.tif 000005
【０１６９】
探索方針が、キャッシュの部分的な順序付けだけを作る場合には、他のヒューリスティックを使用して、完全な順序付けを作成することが可能である。言い換えると、探索方針は、すべてが他のキャッシュ・グループに関して同一の優先順位を有するキャッシュのグループを提供でき、追加のヒューリスティックは、グループ間の同点に決着をつけるものとして働く。たとえば、キャッシュ・システムが、（ａ）大きい順、（ｂ）最近のヒット、または他のヒューリスティックを使用することが可能である。「大きい順」ヒューリスティックでは、最大のキャッシュが最初に照会され、２番目に大きいキャッシュが次に照会され、以下同様である。「最近のヒット」ヒューリスティックでは、最近にキャッシュ・ヒットを返したグループのキャッシュが照会され、次に、次に最近のヒットを含むキャッシュが照会され、以下同様である。
【０１７０】
複数のキャッシュを有するキャッシュ・システムでは、特定のキャッシュ・キーに対する照会が、それぞれがそのキャッシュ・キーと一致する変換構造を含む複数のキャッシュを返す場合がある。複数のヒットの間で選択する際に、キャッシュ１システムは、他の要因を考慮に入れることが可能である。そのような要因は、効果的にキャッシュ方針と相互作用して、キャッシュ・システムの構造および動作を決定する。そのような要因に、（ａ）すべての可能なキャッシュ・スコープ値の組（すなわち、何個の異なるスコープ・レベルがあるか）、（ｂ）変換器インスタンスまたはキャッシュ・サーバのメモリ空間制約またはディスク空間制約、（ｃ）実行中の対象アプリケーション、などを含めることが可能である。
積極的な最適化
動的バイナリ・変換器が実行可能な複数の最適化、または追加の変換コストを犠牲にして積極的にまたはより頻繁に適用するように変換器を構成することが可能な複数の最適化がある。共用キャッシング技法を使用しない変換器の実施形態で、変換器は、変換コストと実行コストのバランスをとって、特定の変換器インスタンス（すなわち、１つの実行）を最適化しなければならない。
【０１７１】
共用キャッシング技法を使用する変換器の実施形態では、変換コストを、単一の変換器インスタンスではなく、複数の変換器インスタンスにまたがって測定することが可能である。したがって、変換されたコードの積極的な最適化が、キャッシングが存在する場合により魅力的になる。最初の変換コストは、積極的最適化方式ではより高いが、複数の後続の変換インスタンスの存在が、その出費を正当化する。というのは、各後続変換インスタンスが、早期の最適化努力の利益を享受するからである。積極的な変換のコストは、第１の変換器インスタンス（特定の対象コード・シーケンスまたは対象プログラムの）がこうむる「１回限り」のヒットになるが、最適化された変換の利益は、キャッシュを使用可能な変換器の全ての将来のインスタンスのすべてによって享受される。
【０１７２】
したがって、共用キャッシング技法を使用する変換器では、特定の対象プログラムの第１の実行中により高価な最適化が適用される場合がある。これは、第１の実行についてわずかに低い性能をもたらす可能性があるが、結果の変換構造が、そのアプリケーションの将来の実行についてよりよい性能を作り、この将来の実行は、開始時に即座にキャッシングされた変換構造を使用することが可能なので、変換コストがかからない。積極的最適化戦略の最適化の１つは、未変換の対象コードに出会う、同一対象プログラムの将来の変換器インスタンスが、新しいコード・パスを探査する時の臨界変換コスト（および、したがって、待ち時間）を減らすために、当初に積極的な最適化を適用しないことを選択することが可能であることである。
【０１７３】
少数の好ましい実施形態を図示し、説明したが、当業者は、請求項で定義される発明の範囲から外れずに、種々の変更および修正を行えるであろう。
本願に関する本明細書と同時にまたはその前に出願され、本明細書と共に公衆の閲覧に公開されているすべての論文および文書に注意を向け、そのようなすべての論文および文書の内容を、本願明細書に援用する。
【０１７４】
本明細書（添付請求項、要約書、および図面を含む）で開示された特徴のすべて、および／またはそのように開示されたすべての方法または工程のすべてのステップを、そのような特徴および／またはステップの少なくとも一部が相互に排他的である組合せを除いて、任意に組み合わせることが可能である。
【０１７５】
本明細書（添付請求項、要約書、および図面を含む）で開示された特徴のそれぞれを、そうでないと明示的に述べられていない限り、同一の目的、同等の目的、または類似する目的のために代替の特徴に置換することが可能である。したがって、そうでないと明示的に述べられていない限り、開示された各特徴は、包括的な一連の同等の特徴または類似する特徴の１例にすぎない。
【０１７６】
本発明は、前述の実施形態の詳細に制限されない。本発明は、本明細書（添付請求項、要約書、および図面を含む）で開示された特徴のうちの新規のいずれかまたはその新規の組合せ、あるいはそのように開示された方法または工程のいずれかのステップのうちの新規のいずれかまたはその新規の組合せに拡張される。
【図面の簡単な説明】
【０１７７】
【図１】本発明の実施形態が応用例を見出す装置を示すブロック図。
【図２】ランタイム変換工程およびその工程中に生成される対応するＩＲ（中間表現）を示す概略図。
【図３】本発明の例示的実施形態による基本ブロック・データ構造およびキャッシュを示す概略図。
【図４】拡張基本ブロック工程を示す流れ図。
【図５】アイソブロッキングを示す流れ図。
【図６】グループ・ブロッキングおよび付随する最適化を示す流れ図。
【図７】グループ・ブロック最適化を示す例を示す概略図。
【図８】拡張基本ブロッキング、アイソブロッキング、およびグループ・ブロッキングを含むリアルタイム変換を示す流れ図。
【図９】共用コード・キャッシング工程の顕著な態様を示す流れ図。
【図１０】共用コード・キャッシング工程をさらに示す流れ図。
【図１１】キャッシュ・ユニットの例を示す概略ブロック図。
【図１２】変換器インスタンス、ローカル・コード・キャッシュ、およびローカル・キャッシュ・サーバを示す概略図。
【図１３】変換器インスタンス、リモート・コード・キャッシュ、およびリモート・キャッシュ・サーバを示す概略図。
【図１４】協力する変換器コードと異なるシステムで動作するキャッシュ・サーバを示す概略図。
【図１５】キャッシュ・サーバが複数のキャッシュを共用する接続された工程のネットワークであるシステムを示す概略図。
【図１６】キャッシュ・エボリューションを示す流れ図。
【図１７】同一のキャッシュ・ユニット構造が複数の変換器インスタンスによって利用されるシステムを示す概略図。
【図１８】それぞれキャッシュ挿入方針およびキャッシュ・ロックアップ方針の実装を示す概略図。
【図１９】それぞれキャッシュ挿入方針およびキャッシュ・ロックアップ方針の実装を示す概略図。
【図１】
0005419325.tif 000006
【図２】
0005419325.tif 000007
【図３】
0005419325.tif 000008
【図４】
0005419325.tif 000009
【図５】
0005419325.tif 000010
【図６】
0005419325.tif 000011
【図７】
0005419325.tif 000012
【図８】
0005419325.tif 000013
【図９】
0005419325.tif 000014
【図１０】
0005419325.tif 000015
【図１１】
0005419325.tif 000016
【図１２】
0005419325.tif 000017
【図１３】
0005419325.tif 000018
【図１４】
0005419325.tif 000019
【図１５】
0005419325.tif 000020
【図１６】
0005419325.tif 000021
【図１７】
0005419325.tif 000022
【図１８】
0005419325.tif 000023
【図１９】
0005419325.tif 000024