(57)【特許請求の範囲】
【請求項１】
プロセッサが、コンパイルされたプログラミングコード（２０）を第１のコード状態（１２）から第２のコード状態（１４）に変換するための方法であって、前記第１のコード状態のプログラミングコードは複数の基本ブロック（２４）を含み、前記基本ブロックの各々は１組の命令を含み、少なくとも１つの基本ブロックは動的分岐で終了し、前記動的分岐は、行先アドレスの計算に基づく１組の行先のうちの１つへの移動であり、方法は、
前記第１のコード状態のプログラミングコードにおける複数の基本ブロックを識別するステップと、
前記識別された基本ブロックの間のリンクを識別するステップと、
前記識別された基本ブロックと前記識別されたリンクとに基づいて、プログラミングコードの制御フローグラフ／表示（ＣＦＧ）（２６）を構築するステップとを含み、前記ＣＦＧは予備的な形式であり、方法はさらに、
動的分岐で終了する、少なくとも１つの基本ブロックを識別するステップと、
前記ＣＦＧに基づいて、前記動的分岐に対する１組の行先アドレスを決定するために、動的分岐につながる識別された基本ブロックのすべてを探索するステップとを含み、前記行先アドレスの組は前記動的分岐からの１組の行先を規定し、方法はさらに、
前記行先の組を調べて分岐テーブルを識別するステップと、
ＣＦＧを更新して前記行先の組と前記識別された分岐テーブルとを反映させるステップと、
更新されたＣＦＧに少なくとも一部は基づいて、前記プログラミングコードを前記第１のコード状態から前記第２のコード状態に変換するステップとを含む、方法。
【請求項２】
前記探索するステップは、
探索された基本ブロックごとに、前記基本ブロックにおける命令の、対応するコードグラフ／表示（コードグラフ）を構築するステップと、
前記コードグラフの各々をトラバースして、動的分岐から１組の行先アドレスを決定するステップとを含む、請求項１に記載の方法。
【請求項３】
前記コードグラフの各々は、相互接続するノードを有する根付有向アサイクリックグラフであって、ノードの各々は、
対応する基本ブロック内の命令を表わす命令ノード、
対応の基本ブロック内の引数を表わす引数ノード、
命令ノードと引数ノードとに枝を張り、かつ前記引数ノードの前記命令ノードへの適用を表わし、特定の例においては別のノードから枝が張られる引数ノードでもある、適用ノード、
１対の引数ノードに枝を張り、前記１対の引数ノードを有する引数ノードとして作用するスタックノード、
異なった基本ブロックから供給される欠落した引数を表わす欠落引数ノード、または、
スタックノードまたは適用ノードから枝が張られ、前記スタックノードから離れた引数に枝を張り、かつ前記スタックノードに対する前記離れた引数を表わすエイリアスノード、のうちのいずれかである、請求項２に記載の方法。
【請求項４】
前記探索するステップは、
第１の基本ブロックに対応する第１のコードグラフが欠落した／不十分に定義された引数ノードを含むことを見出すステップと、
前記ＣＦＧに基づいて、第１の基本ブロックの直前の第２の基本ブロックの位置を突き止めるステップとを含み、第２のコードグラフは第２の基本ブロックに対応し、
前記第１のコードグラフ内の欠落した引数ノードを第２のコードグラフと置き換えることにより、前記第１のコードグラフと前記第２のコードグラフとを有する新しいコードグラフを構築するステップと、
動的分岐から１組の行先アドレスを決定する目的で、新しいコードグラフをトラバースするステップとを含む、請求項３に記載の方法。
【請求項５】
前記探索するステップは、
前記第２のコードグラフに対応する新しいコードグラフの部分において、プログラムフローが前記第２の基本ブロックから前記第１の基本ブロックに続くことを許すために、満たされねばならない条件を表わす命令ノードの位置を突き止めるステップと、
位置を突き止めた前記命令ノードを、満たされねばならない条件を示すテストノードに置き換えるステップとを含む、請求項４に記載の方法。
【請求項６】
前記位置を突き止められた命令ノードは分岐命令を表わし、満たされねばならない条件は論理真、論理偽、または予め定められたインデックス値である、請求項５に記載の方法。
【請求項７】
前記探索するステップは、プロップのリストに従って境界評価を行なうステップを含み、プロップの各々は、前記プロップが適用されるターゲットノードと前記ノードに適用されるべき１組の境界とを表わす、請求項５に記載の方法。
【請求項８】
前記境界評価を行なうステップは、リスト内のプロップごとのコードグラフ内のノードの各々をトラバースするステップを含む、請求項７に記載の方法。
【請求項９】
前記ノードの各々をトラバースするステップは、適用ノードがトラバースされ、かつ前記適用ノードがプロップのターゲットノードであれば、境界情報を前記適用ノードから枝を張る引数ノードにプッシュしようと試みるステップを含む、請求項８に記載の方法。
【請求項１０】
ノードの各々は境界情報を含み、前記試みるステップは、
ターゲット適用ノードから枝を張る引数ノードおよび命令ノードに基づき、前記ターゲット適用ノードから枝を張る前記引数ノードに対する境界情報を演繹しようと試みるステップと、
前記境界情報が演繹できる場合に、前記ターゲット適用ノードから枝を張る前記引数ノードの境界情報を変更するステップと、
前記ターゲット適用ノードから枝を張る前記引数ノードの境界情報が変更されていれば、新しいプロップをリストに加えるステップとを含む、請求項９に記載の方法。
【請求項１１】
前記ノードの各々をトラバースするステップは、テストノードに最初に出会ったときに、前記テストノードの各々の引数に対するプロップを生成するステップを含む、請求項７に記載の方法。
【請求項１２】
前記ノードの各々をトラバースするステップは、テストノードに対するプロップを累算する目的で、コードグラフを空のプロップで予備的にトラバースするステップを含む、請求項１１に記載の方法。
【請求項１３】
ノードの各々は境界情報を含み、前記ノードの各々をトラバースするステップは、コードグラフを通して拡張方向に１ステップずつ進み、次いで拡張の逆の方向に向かってコードグラフを通して再トレースするステップを含み、前記再トレースするステップは、境界における変化が生じ得るときにはいつでも、再トレースされたノードの各々の境界情報を再評価するステップを含む、請求項１２に記載の方法。
【請求項１４】
プロセッサ（１６）上で動作してコンパイルされたプログラミングコード（２０）を第１のコード状態（１２）から第２のコード状態（１４）に変換するためのトランスレータ（１０）であって、前記第１のコード状態のプログラミングコードは複数の基本ブロック（２４）を含み、基本ブロックの各々は１組の命令を含み、少なくとも１つの基本ブロックが動的分岐で終了し、前記動的分岐は行先アドレスの計算に基づいた１組の行先のうちの１つへの移動であり、前記トランスレータは、
前記第１のコード状態のプログラミングコードにおける複数の基本ブロックを識別し、
前記識別された基本ブロックの間のリンクを識別し、
前記識別された基本ブロックと前記識別されたリンクとに基づいて、プログラミングコードの制御フローグラフ／表示（ＣＦＧ）（２６）を構築し、前記ＣＦＧは予備的な形式であり、トランスレータはさらに、
動的分岐で終了する、少なくとも１つの基本ブロックを識別し、
前記ＣＦＧに基づいて、前記動的分岐に対する１組の行先アドレスを決定するために、動的分岐につながる識別された基本ブロックのすべてを探索し、前記行先アドレスの組は、前記動的分岐からの１組の行先を規定し、トランスレータはさらに、
前記行先の組を調べて分岐テーブルを識別し、
ＣＦＧを更新して前記行先の組と前記識別された分岐テーブルとを反映させ、
更新されたＣＦＧに少なくとも一部は基づいて、前記プログラミングコードを前記第１のコード状態から前記第２のコード状態に変換する、トランスレータ。
【請求項１５】
探索された基本ブロックごとに、前記基本ブロックにおける命令の、対応するコードグラフ／表示（コードグラフ）を構築し、
前記コードグラフの各々をトラバースして、動的分岐から１組の行先アドレスを決定する、請求項１４に記載のトランスレータ。
【請求項１６】
前記コードグラフの各々は、相互接続するノードを有する根付有向アサイクリックグラフであって、ノードの各々は、
対応する基本ブロック内の命令を表わす命令ノード、
対応の基本ブロック内の引数を表わす引数ノード、
命令ノードと引数ノードとに枝を張り、かつ前記引数ノードの前記命令ノードへの適用を表わし、特定の例においては別のノードから枝が張られる引数ノードでもある、適用ノード、
１対の引数ノードに枝を張り、前記１対の引数ノードを有する引数ノードとして作用するスタックノード、
異なった基本ブロックから供給される欠落した引数を表わす欠落引数ノード、または、
スタックノードまたは適用ノードから枝が張られ、前記スタックノードから離れた引数に枝を張り、かつ前記スタックノードに対する前記離れた引数を表わすエイリアスノード、のうちのいずれかである、請求項１５に記載のトランスレータ。
【請求項１７】
前記トランスレータは、
第１の基本ブロックに対応する第１のコードグラフが欠落した／不十分に定義された引数ノードを含むことを見出し、
前記ＣＦＧに基づいて、第１の基本ブロックの直前の第２の基本ブロックの位置を突き止め、第２のコードグラフは第２の基本ブロックに対応し、前記トランスレータはさらに、
前記第１のコードグラフ内の欠落した引数ノードを第２のコードグラフと置き換えることにより、前記第１のコードグラフと前記第２のコードグラフとを有する新しいコードグラフを構築し、
動的分岐から１組の行先アドレスを決定する目的で、新しいコードグラフをトラバースする、請求項１６に記載のトランスレータ。
【請求項１８】
前記トランスレータは、
前記第２のコードグラフに対応する新しいコードグラフの部分において、プログラムフローが前記第２の基本ブロックから前記第１の基本ブロックに続くことを許すために、満たされねばならない条件を表わす命令ノードの位置を突き止め、
位置を突き止めた前記命令ノードを、満たされねばならない条件を示すテストノードに置き換える、請求項１７に記載のトランスレータ。
【請求項１９】
前記位置を突き止められた命令ノードは分岐命令を表わし、満たされねばならない条件は論理真、論理偽、または予め定められたインデックス値である、請求項１８に記載のトランスレータ。
【請求項２０】
前記トランスレータは、プロップのリストに従って境界評価を行ない、プロップの各々は、前記プロップが適用されるターゲットノードと、前記ノードに適用されるべき１組の境界とを表わす、請求項１８に記載のトランスレータ。
【請求項２１】
前記トランスレータは、リスト内のプロップごとにコードグラフ内のノードの各々をトラバースする、請求項２０に記載のトランスレータ。
【請求項２２】
前記トランスレータは、プロップごとに、適用ノードがトラバースされ、かつ前記適用ノードがプロップのターゲットノードであれば、境界情報を前記適用ノードから枝を張る引数ノードにプッシュしようと試みる、請求項２１に記載のトランスレータ。
【請求項２３】
ノードの各々は境界情報を含み、前記トランスレータは、
ターゲット適用ノードから枝を張る引数ノードおよび命令ノードに基づき、前記ターゲット適用ノードから枝を張る前記引数ノードに対する境界情報を演繹しようと試み、
前記境界情報が演繹できる場合に、前記ターゲット適用ノードから枝を張る前記引数ノードの境界情報を変更し、
前記ターゲット適用ノードから枝を張る前記引数ノードの境界情報が変更されていれば、新しいプロップをリストに加える、請求項２２に記載のトランスレータ。
【請求項２４】
前記トランスレータは、テストノードに最初に出会ったときに、前記テストノードの各々の引数に対するプロップを生成する、請求項２０に記載のトランスレータ。
【請求項２５】
前記トランスレータは、テストノードに対するプロップを累算する目的で、コードグラフを空のプロップで予備的にトラバースする、請求項２４に記載のトランスレータ。
【請求項２６】
ノードの各々は境界情報を含み、前記トランスレータはコードグラフを通して拡張する方向に１ステップずつ進み、次いで拡張の逆の方向に向けてコードグラフを通して再トレースし、前記再トレースには境界における変化が生じ得るときにはいつでも、再トレースされたノードの各々の境界情報を再評価することを含む、請求項２５に記載のトランスレータ。
【請求項２７】
コンパイルされたプログラミングコード（２０）を第１のコード状態（１２）から第２のコード状態（１４）に変換することに関し、前記第１のコード状態のプログラミングコードは複数の基本ブロック（２４）を含み、基本ブロックの各々は１組の命令を含み、少なくとも１つの基本ブロックは動的分岐で終了し、動的分岐は行先アドレスの計算に基づいた１組の行先のうちの１つの移動であり、
前記第１のコード状態のプログラミングコードにおける複数の基本ブロックを識別するステップと、
前記識別された基本ブロックの間のリンクを識別するステップと、
前記識別された基本ブロックと前記識別されたリンクとに基づいて、プログラミングコードの制御フローグラフ／表示（ＣＦＧ）（２６）を構築するステップと、前記ＣＦＧは予備的な形式であり、
動的分岐で終了する、少なくとも１つの基本ブロックを識別するステップと、
前記ＣＦＧに基づいて、前記動的分岐に対する１組の行先アドレスを決定するために、動的分岐につながる識別された基本ブロックのすべてを探索するステップとを含み、前記行先アドレスの組は前記動的分岐からの１組の行先を規定し、
前記行先の組を調べて分岐テーブルを識別するステップと、
ＣＦＧを更新して前記行先の組と前記識別された分岐テーブルとを反映させるステップと、
更新されたＣＦＧに少なくとも一部は基づいて、前記プログラミングコードを前記第１のコード状態から前記第２のコード状態に変換するステップとを行なうためのコンピュータ実行可能命令を有する、コンピュータ可読媒体。
【請求項２８】
前記探索するステップは、
探索された基本ブロックごとに、前記基本ブロックにおける命令の、対応するコードグラフ／表示（コードグラフ）を構築するステップと、
前記コードグラフの各々をトラバースして、動的分岐から１組の行先アドレスを決定するステップとを含む、請求項２７に記載のコンピュータ可読媒体。
【請求項２９】
前記コードグラフの各々は、相互接続するノードを有する根付有向アサイクリックグラフであって、ノードの各々は、
対応する基本ブロック内の命令を表わす命令ノード、
対応の基本ブロック内の引数を表わす引数ノード、
命令ノードと引数ノードとに枝を張り、かつ前記引数ノードの前記命令ノードへの適用を表わし、特定の例においては別のノードから枝が張られる引数ノードでもある、適用ノード、
１対の引数ノードに枝を張り、前記１対の引数ノードを有する引数ノードとして作用するスタックノード、
異なった基本ブロックから供給される欠落した引数を表わす欠落引数ノード、または、
スタックノードまたは適用ノードから枝が張られ、前記スタックノードから離れた引数に枝を張り、かつ前記スタックノードに対する前記離れた引数を表わすエイリアスノード、のうちのいずれかである、請求項２８に記載のコンピュータ可読媒体。
【請求項３０】
前記探索するステップは、
第１の基本ブロックに対応する第１のコードグラフが欠落した／不十分に定義された引数ノードを含むことを見出すステップと、
前記ＣＦＧに基づいて、第１の基本ブロックの直前の第２の基本ブロックの位置を突き止めるステップとを含み、第２のコードグラフは第２の基本ブロックに対応し、
前記第１のコードグラフ内の欠落した引数ノードを第２のコードグラフと置き換えることにより、前記第１のコードグラフと前記第２のコードグラフとを有する新しいコードグラフを構築するステップと、
動的分岐から１組の行先アドレスを決定する目的で、新しいコードグラフをトラバースするステップとを含む、請求項２９に記載のコンピュータ可読媒体。
【請求項３１】
前記探索するステップは、
前記第２のコードグラフに対応する新しいコードグラフの部分において、プログラムフローが前記第２の基本ブロックから前記第１の基本ブロックに続くことを許すために、満たされねばならない条件を表わす命令ノードの位置を突き止めるステップと、
位置を突き止めた前記命令ノードを、満たされねばならない条件を示すテストノードに置き換えるステップとを含む、請求項３０に記載のコンピュータ可読媒体。
【請求項３２】
前記位置を突き止められた命令ノードは分岐命令を表わし、満たされねばならない条件は論理真、論理偽、または予め定められたインデックス値である、請求項３１に記載のコンピュータ可読媒体。
【請求項３３】
前記探索するステップは、プロップのリストに従って境界評価を行なうステップを含み、プロップの各々は、前記プロップが適用されるターゲットノードと前記ノードに適用されるべき１組の境界とを表わす、請求項３１に記載のコンピュータ可読媒体。
【請求項３４】
前記境界評価を行なうステップは、リスト内のプロップごとのコードグラフ内のノードの各々をトラバースするステップを含む、請求項３３に記載のコンピュータ可読媒体。
【請求項３５】
前記ノードの各々をトラバースするステップは、適用ノードがトラバースされ、かつ前記適用ノードがプロップのターゲットノードであれば、境界情報を前記適用ノードから枝を張る引数ノードにプッシュしようと試みるステップを含む、請求項３４に記載のコンピュータ可読媒体。
【請求項３６】
ノードの各々は境界情報を含み、前記試みるステップは、
ターゲット適用ノードから枝を張る引数ノードおよび命令ノードに基づき、前記ターゲット適用ノードから枝を張る前記引数ノードに対する境界情報を演繹しようと試みるステップと、
前記境界情報が演繹できる場合に、前記ターゲット適用ノードから枝を張る前記引数ノードの境界情報を変更するステップと、
前記ターゲット適用ノードから枝を張る前記引数ノードの境界情報が変更されていれば、新しいプロップをリストに加えるステップとを含む、請求項３５に記載のコンピュータ可読媒体。
【請求項３７】
前記ノードの各々をトラバースするステップは、テストノードに最初に出会ったときに、前記テストノードの各々の引数に対するプロップを生成するステップを含む、請求項３３に記載のコンピュータ可読媒体。
【請求項３８】
前記ノードの各々をトラバースするステップは、テストノードに対するプロップを累算する目的で、コードグラフを空のプロップで予備的にトラバースするステップを含む、請求項３７に記載のコンピュータ可読媒体。
【請求項３９】
ノードの各々は境界情報を含み、前記ノードの各々をトラバースするステップは、コードグラフを通して拡張方向に１ステップずつ進み、次いで拡張の逆の方向に向かってコードグラフを通して再トレースするステップを含み、前記再トレースするステップは、境界における変化が生じ得るときにはいつでも、再トレースされたノードの各々の境界情報を再評価するステップを含む、請求項３８に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【０００１】
発明の分野
この発明は、コンパイルされたコンピュータコード（すなわち、マシンコード）における動的分岐の行先を決定することに関する。より特定的には、この発明は、該動的分岐に関するコンピュータコードの制御フローが正確に決定されることができるよう、該動的分岐のあらゆる起こり得る行先を決定することに関する。
【０００２】
発明の背景
ある特定の状況においては、コンパイルされたマシンコードを、第１の命令セットに対応する第１の状態から、第２の命令セットに対応する第２の状態へ変換することが有用である。公知であるように、そのような変換は以下の方法、すなわち、第１のコード状態のマシンコードが導出されたソースコードの位置を突き止め、コンパイラを書き、デバッグして、該位置を突き止められたソースコードを第２のコード状態のマシンコードに直接コンパイルする方法よりも好ましい。
【０００３】
また公知であるように、そのような第１のコード状態から第２のコード状態への変換は、付属のメモリを備えた適切なプロセッサ上の適切なリコンパイラまたはトランスレータによって行なわれる。しかしながら、第１の状態のマシンコードが分岐または行先アドレス情報を含み、該分岐アドレス情報が第２の状態のマシンコードに対しては異なる可能性があり、かつ最初のコンパイラからの明示的なアドレス情報がない状況では、問題が生じる。分岐アドレス情報があまり直接的な態様で変換されない場合、この問題は悪化する。
【０００４】
公知であるように、一般的に計算においては、動的分岐とは、分岐または行先アドレスの時に複雑となる計算に基づいた、コンピュータコードの一部分からのコンピュータコードのいくつもの他の部分のうちの１つへの移動である。トランスレータは、最初のコンパイラからの明示的な情報がなければ、動的分岐の可能性のある起こり得る行先のすべてを正確に決定して、該動的分岐に関する制御フローを正確に変換しなければならない。
【０００５】
一方の命令セットからのコードを他方に変換するためには、あらゆる分岐の行先を識別することが必要である。これはコードに対する完全制御フローグラフ（ＣＦＧ）を生成するための前提条件である。理解されるように、そのようなＣＦＧはそのコードの完全なセマンティック解析のために必要であり、より狭義には、ターゲット（すなわち、第２の）命令セットにおける変更されたアドレスまたは新しいアドレス形式への、分岐またはそれらの引数に対する調整を参酌するために必要である。静的分岐（すなわち、１つの行先のみに対する分岐）に対しては、コードセグメントに基づくかまたは自己相対であるかのいずれであっても、行先のアドレスが分岐命令自体にエンコードされているために、これは簡単な作業である。しかしながら動的分岐に対しては、作業はより複雑になる。
【０００６】
動的分岐は、その全体または一部において、分岐の前に行なわれた計算の結果に依存し、したがって変換に対しより困難な問題をもたらす。動的分岐は当然、単一の行先ではなく、１組の可能性のある行先アドレスを意味している。すると、ターゲットの命令セットにおける再配置された可能性のある行先または異なったアドレス構造に対して調整するために、分岐に先立つ計算を評価するトランスレータに対する必要性がある。
【０００７】
発明の概要
この発明は、コンパイルされたプログラミングコードを第１のコード状態から第２のコード状態へ変換するための、方法、トランスレータ、およびコンピュータ可読媒体を提供することにより、上述の必要性を満たす。第１のコード状態におけるプログラミングコードは、複数の基本ブロックを有し、基本ブロックの各々は１組の命令を有する。少なくとも１つの基本ブロックが動的分岐で終了し、動的分岐は、行先アドレスの計算に基づく、１組の行先のうちの１つへの移動である。
【０００８】
第１のコード状態のプログラミングコードにおける複数の基本ブロックが識別され、識別された基本ブロックの間のリンクもまた識別される。次いでプログラミングコードの制御フローグラフ／表示（ＣＦＧ）が、識別された基本ブロックと識別されたリンクとに基づいて構築されるが、このＣＦＧは予備的な形式である。動的分岐で終了する少なくとも１つの基本ブロックが識別され、ＣＦＧに基づいて、動的分岐に対する１組の行先アドレスを完全に決定するために必要な限り、動的分岐につながる識別された基本ブロックのすべてが探索される。
【０００９】
行先アドレスの組は、動的分岐からの行先の組を規定する。該行先の組が調べられて分岐テーブルが識別され、この行先の組と識別された分岐テーブルとを反映するようＣＦＧが更新される。プログラミングコードは次いで、更新されたＣＦＧに少なくとも一部は基づいて、第１のコード状態から第２のコード状態に変換される。
【００１０】
上述の概要と、以下のこの発明の好ましい実施例の詳細な説明とは、添付の図面と併せて読まれるとより良く理解されるであろう。この発明の例示の目的で、ここで好ましい実施例が図面に示される。しかしながら、この発明は示されるとおりの構成および装置に限定されるものではないことを理解されたい。
【００１１】
好ましい実施例の詳細な説明
以下の説明の中で便宜のためにのみ、ある特定の用語を用い得るが、限定するものとは解されない。「左」、「右」、「上側」、および「下側」という用語は、参照される図面における方向を示すものである。「内側に」および「外側に」という用語は、それぞれ参照される対象のジオメトリ的中心へ向かう方向、およびそれから離れる方向を示すものである。用語は上に特に述べたものを含む他に、これらからの派生語、および同様の意味の用語を含む。
【００１２】
この開示においては、ペンシルバニア州ブルーベルのユニシス・コーポレイション（UNISYS Corporation）によって製造され販売される特定のコンピュータに関連して用いるためのコンパイラによって生成される、Ｅ−Ｍｏｄｅマシンコード命令セットに関して特に記載する。しかしながら、この発明は該Ｅ−Ｍｏｄｅ命令セットに限定されるものではなく、この発明の精神および範囲から逸脱することなく、実際には（適切な変更によって）いかなる適切な命令セットと併せても用いることが可能である。
【００１３】
動的分岐
Ｅ−Ｍｏｄｅは３つの動的分岐命令を有するが、１つは無条件（ＤＢＵＮ）であり、他の２つは条件付き（ＤＢＦＬおよびＤＢＴＲ）である。これらすべては行先としてスタックのトップの引数をとる。条件付きは、分岐を行なうべきであるか、またはフォールスルーするべきであるかのブール表示として、付加的なスタック引数をとる。説明される方法に特に関連がない限り、条件付きと無条件の形式との間のさらなる区別は行なわない。動的分岐への行先引数は２つの形式のうちの１つをとり得る。すなわち、プログラム制御語（ＰＣＷ）もしくはＰＣＷへの参照、またはオペランドである。ＰＣＷは、セグメント識別を含むコードアドレスを含む。オペランドは、分岐命令自体のように、同じコードセグメントに関するアドレスであると解釈される。
【００１４】
オペランド形式の１つの一般的な使用法は、分岐テーブルへの分岐である。公知であるように、分岐テーブルは、ＳＷＩＴＣＨまたはＣＡＳＥステートメントを実現するためにソースコードをＥ−Ｍｏｄｅプログラムにコンパイルする間に生成される。たとえば、以下のソースコードに基づいて、
0003685717.tif 000002
以下のＥ−Ｍｏｄｅプログラムを生成し得る。
【００１５】
ＶＡＬＣ  ｘ      （スタックに値ｘを置く）
＜ｘに対し何らかの境界チェックを行なう＞
＜何らかのオフセット計算を行ない、結果として生じるオフセット値をスタックに置く＞
ＡＤＤ      （スタック上のオフセット値とスタック上のｘとを加算し、結果として生じるアドレスをスタックに置く）
ＤＢＵＮ      （スタック上のアドレスへ分岐する）
コードにおいては、インデックスｘは境界チェックされ、分岐テーブルの位置に調整され、かつ動的分岐ＤＢＵＮへのアドレス引数として用いられる。
【００１６】
該コードに加えて、以下の分岐テーブルを生成し得るが、それらのエントリの各々は特定のｃａｓｅに対応する行先への無条件静的分岐である。
【００１７】
ＢＲＵＮ−ｃａｓｅ  ０
ＢＲＵＮ−ｃａｓｅ  １
ＢＲＵＮ−ｃａｓｅ  ２
ＢＲＵＮ−ｃａｓｅ  ３
…
ＢＲＵＮ−ｃａｓｅ  ｎ
ここで理解されるように、ＤＢＵＮ命令は、値ｘに基づいて行なわれるべき動作に対応する分岐テーブル内の特定のＢＲＵＮ命令のアドレスに動的に分岐し、ＢＲＵＮ命令はさらに、値ｘに基づいて行なわれるべき動作に対応するコードに静的に分岐する。
【００１８】
分岐テーブルにおいて、この発明の精神および範囲から逸脱することなくさまざまな変更を用い得ることが認識されるであろう。たとえば、個々のテーブルエントリは静的分岐である必要はない。しかしながら、コンパイラ規則によるとそのようなエントリはどこかに無条件に分岐するか、プロシジャを離れるか、または無条件にフォールトしなければならない。そのような規則への唯一の例外とは、分岐テーブルにおける最後のエントリには何の規制も課されておらず、かつしばしば、そのエントリによって分岐先となったであろうコードシーケンスであることである。分岐テーブルには常にオペランド動的分岐によって入り、先行の命令によって入るものではないというのもまたコンパイラ規則である。
【００１９】
動的分岐のＰＣＷ形式はその行先引数として、ＰＣＷ自体か、またはＰＣＷへの非直接的な参照のいずれかを取る。この形式は、行先のアドレスが固定されていても、分岐の行先が異なったコードセグメントにある場合には常に用いられなければならない。ＰＣＷは、アドレス可能起動レコード位置にストアされ、非直接的に参照され、スタック上に直接構築されるか（ＭＰＣＷ命令）、または他の手段によってスタックのトップに置かれる。ＰＣＷはしばしば、「ｅｘｉｔ」命令が単にＤＢＵＮであるような「チープな」プロシジャコールに対するリターンポイントとしてスタックに残される。
【００２０】
動的分岐が単純なリテラルのコードアドレスによって達成される場合もある。そのような状況においては、アドレスはスタック内に残されるか、ローカルの起動レコードセルにストアされ、複数の部分を備えたループの状態を示すために用いられる。このときＤＢＵＮ命令が用いられて、ループの次の要素への反復を行なう。次いで要素の各々は、次の反復に対して適切に状態を更新する。コンパイラはこの形式を用いていかなる「状態機械」構造をも実現化し得る。
【００２１】
予備的なトランスレータ動作
図１を参照するとこの発明において、リコンパイラまたはトランスレータ１０はコンパイルされたマシンコードを、第１の命令セットに対応する第１の状態１２から、第２の命令セットに対応する第２の状態１４に変換する。典型的には、トランスレータは付属のメモリ１８を備えたプロセッサ１６上で動作し、トランスレータ１０は、コンピュータ実行可能命令を有するコンピュータ可読媒体１７からプロセッサ１６によって構築される。この発明の範囲および精神から逸脱することなく、いかなる適切なプロセッサ１６およびメモリ１８をも用い得る。
【００２２】
この開示において、第１の命令セットの例としてＥ−Ｍｏｄｅマシンコード命令セットが用いられる。しかしながら、第１の命令セットは、この発明の精神および範囲から逸脱することなく、いかなる適切な命令セットでもあり得る。同様に、第２の命令セットは、この発明の精神および範囲から逸脱することなく、いかなる適切な命令セットでもあり得る。
【００２３】
図２を参照すると、Ｅ−Ｍｏｄｅプログラム２０は、１組のコードセグメント２２からなる。コードセグメントに対する記述子がセグメント辞書内に含まれる。この発明においては、トランスレータ１０によるコード解析は一度に１つのコードセグメント２２ずつ行なわれるが、完全なプログラム２０に対する一般化は簡単である。
【００２４】
特定のコードセグメント２２は、一般的に１組の基本ブロック２４に分割し得るが、基本ブロック２４の各々は、分岐、プロシジャコール、または先行のブロックからのフォールスルーのいずれによって行なわれるかにかかわらず、その先頭でのみ入ることができ、かつ、該基本ブロック２４の最後の命令を介してのみ出ることができるシーケンスである。こうして、いかなる分岐も基本ブロック２４における最後の命令である必要がある。常にではないがしばしば、基本ブロック２４はできるだけ大きなシーケンスとして定義されるが、これはこの発明の目的に対しては必要ではない。
【００２５】
この発明において好ましくは、プロシジャコールシーケンス（ＥＮＴＲ）における最後の命令は、特定の割込を引起こす命令と同様に、分岐のように扱われる。これは活性判断（すなわち、特定の基本ブロック２４が他の基本ブロック２４のいずれかから到達可能であるか、または該特定の基本ブロック２４はＥ−Ｍｏｄｅプログラム２０の最初のコンパイルから生じた「ごみ」であり、したがって無視されるべきであるか）で役に立ち、リターンポイントを明確にマークする。ＰＣＷはＭＰＣＷ命令によってのみ構築し得るために、Ｅ−Ｍｏｄｅプログラム２０のすべてのコードセグメント２２における走査によって、プロシジャコールまたはＰＣＷ動的分岐によって入る基本ブロック２４が識別されるであろう。さらに、該プログラム２０のすべてのセグメント２２における走査は、基本ブロック２４を終了させるかまたは開始させるすべての分岐および他の構造を識別するために必要である。
【００２６】
図３を参照すると、この発明においては次いで、トランスレータ１０はプログラム２０の全体を予備的に調べ、そのようなＰＣＷ、分岐および他の構造の位置を突き止めることにより、プログラム２０内のすべての基本ブロック２０を予備的に識別する（ステップ３０１）。次いでトランスレータ１０は適切なテーブルなどを構築して、識別された基本ブロック２４およびこれに関連する情報の各々をトラッキングする。そのような情報は以下のものを含み得るが、これに限定されるものではない。すなわち、活性／到達可能性、コードアドレス、入口および出口モード、および基本ブロック２４における命令の表示である。理解されるように、この段階での基本ブロック２４の識別は予備的なものであり、いくつかの分岐または他の終了させる構造は検出されていないかもしれない。たとえば、動的分岐は単一の基本ブロック２４の中間であるように見える行先を有し、そのような単一の基本ブロック２４に見えるものは実際は（少なくとも）１対の基本ブロックであって、その１対の中の第２の部分は上述の行先から開始し、第１の部分はその直前で終了しているかもしれないことを示唆する。しかしながら、後で付加的な基本ブロック２４が検出されると、上述のテーブルは適切に調整／更新されることができる。
【００２７】
一旦基本ブロック２４が識別されると、トランスレータ１０は次いで特定のセグメント２２における識別された基本ブロック２４の間のリンクを識別し始め（ステップ３０２）、識別された基本ブロック２４に基づいてセグメント２２の予備的な制御フローグラフまたは表示（ＣＦＧ）２６を構築する。図４にそのようなＣＦＧ２６をグラフの形式で示すが、トランスレータ１０はＣＦＧ２６をファイルまたはテーブルフォーマットなどで維持することを理解されたい。さらに、分岐行先が決定されると、基本ブロックから該基本ブロックの分岐行先へのリンクもまた確立される。確立されたリンクはＣＦＧ２６に対する基礎である。理解されるように、ＣＦＧ２６は予備的なものであって、いくつかの基本ブロック２４は予備的に識別されていないかもしれず、動的分岐行先もまだ識別されていないかもしれない。しかしながら、ＣＦＧ２６は、適切な付加的な情報を得ると適切に調整／更新可能である。
【００２８】
図４を参照すると、１６個の識別されたブロック２４を有するセグメント２２に対するＣＦＧ２６が示される。示されるように、セグメント２２はブロックＡで入り、該ブロックＡはブロックＢまたはブロックＣのいずれかに分岐する。ブロックＣおよびＤは循環経路を形成するが、ブロックＤはブロックＥにもつながり、該ブロックＥはブロックＦにつながり、該ブロックＦはブロックＧにつながる。ブロックＥおよびブロックＦはまたブロックＮにも分岐する。ブロックＧは動的分岐で終了し、したがってトランスレータ１０によって解析される。好ましくは、トランスレータ１０は動的分岐を有するすべての活性ブロック２４のリストをまとめる。ブロックＧからのいかなるブロックへのリンクもこの時点ではわかっていないが、点線のリンク線で示されるように、ブロックＧはブロックＨ、Ｉ、およびＪにつながることが見出される。
【００２９】
ブロックＨ、Ｉ、およびＪはそれぞれブロックＫ、Ｌ、およびＭにつながり、これらはすべてブロックＮにつながる。ブロックＫはまたブロックＯにつながり、該ブロックＯはブロックＰにつながり、該ブロックＰはブロックＢにつながる。ブロックＨ〜Ｍ、Ｏ、およびＰは活性ではないとマークされるが、これはこの時点でブロックＨ−Ｊに分岐するとわかっている他のブロック２４はなく、かつブロックＫ〜Ｍ、ＯおよびＰがこの時点ではブロックＦからのみ到達可能であるとわかっているためである。ブロックＱは活性ではないとマークされるが、これはこの時点では他のいかなるブロックからも到達できないからである。さらに、ブロックＱはセグメント２２内のいかなる他のブロック２２にも（少なくともこの時点では）分岐しない。
【００３０】
コードのグラフ化
この発明において、一旦トランスレータ１０が完全にプログラム２０をパーズして基本ブロック２４およびＣＦＧ２６を確立し、かつトランスレータ１０が動的分岐を有するすべての活性ブロック２４のリストをまとめると、トランスレータ１０は次いでブロック２４の各々における命令のコードグラフまたは表示２８（たとえば、図５〜図９に示す）を構築する（ステップ３０７）。これに代えて、この場合すべてのブロック２４をコードグラフ化する必要はないかもしれないことから、トランスレータ１０はブロック２４に対するコードグラフ２８を必要に応じて構築してもよい。ＣＦＧ２６の場合のように、この図面においてコードグラフ２８はグラフの形式で示されるが、トランスレータ１０はコードグラフ２８をファイルまたはテーブル形式などで維持することを理解されたい。好ましくは、コードグラフ２８の各々は相互接続されたノードを有する根付き有向アサイクリックグラフであって、それらノードは３つのカテゴリに入る。すなわち、命令、内部、特別である。すべてのノードはいくらかの基本的な情報、たとえばそのノードによっていくつのスタック入力が要求されるか、およびそのノードによっていくつのスタック項目が残されるか、などの情報を担持する。
【００３１】
さらに図５から図９を参照すると、命令ノードは別れる枝を有さない葉ノードである。各々は、ブロック２４におけるもとの命令ストリーム内の命令を表わす。命令がスタックから１つ以上の引数を消費すると、これは内部の「適用」ノードによってそのような引数にリンクされる。適用ノードは２つの外に向かう枝を有し、（左側の）一方は適用される命令に、かつ（右側の）他方は適用される引数に向かう。ほとんどの命令は、スタックには０または１つの結果項目を残す。この場合適用ノードは、その引数へのその命令の適用を表わす。そのような適用の結果が次の命令への引数である場合、適用ノードは、次の命令のための適用ノードの右側の枝によって参照されることができる。スタックのトップから引数をとらない命令に関しては、適用ノードは必要ではない。
【００３２】
多くのＥ−Ｍｏｄｅ命令は、スタックから１つ以上の引数をとる。これらの引数は、「スタック」内部ノードを用いてグラフで表わされる。スタックノードはまた、２つの外に向かう枝を有する。左側はスタックに加えられた最も最近の（最もトップの）項目を示し、右側は残りの項目を示す。左側のスタックノードのサブツリーはそれ自体がスタックサブツリーであることはない一方、右側のサブツリーはしばしばそうである。スタックサブツリーは何もスタックに残さない表示を表わし得るために、ここで「スタック上の項目」という用語は大まかに用いられる。
【００３３】
異なった基本ブロックから一部の、またはすべての引数が供給された（すなわち、それらにより引数がスタックに入れられた）命令を、基本ブロック２４が含むことがしばしばある。欠落した引数に対するプレースホルダとして、グラフ内で特別な「欠落」ノードが用いられる。欠落ノードは葉であって、常にスタック上の単一の項目を示す。グラフ内のノードの各々は、これが率いるサブツリー内の欠落ノードの数のカウントを含む。
【００３４】
いくつかのＥ−Ｍｏｄｅ命令は複数の項目をスタック上に返す。これらの結果を後の命令のために個々に入力引数として表わすことを可能にするために、「エイリアス」の内部ノードがプレースホルダおよび、そのような命令の結果項目のうちの１つ（一般的には最もトップのものではない）への非直接的な参照として作用する。これは内部ノードであってスタックノードまたは適用ノードから枝を張り、通常はこれが参照する項目を生成する命令の適用につながる、単一の外に向かう枝を有するか、または時には（以下参照）そのような適用の引数のうちの１つに直接つながる。エイリアスノードは常に同じコードグラフ２８内の他のノードを指し、別のエイリアスノードまたはスタックノードを指すことはない。そのようなエイリアスノードはまた、その命令のどの結果が参照されているかを示すインデックスをも担持する。
【００３５】
エイリアスノードが、複数の結果を備えた命令に関わる表示を表わすために用いられる場合、その命令に対する適用ノードは１つの結果のみを返すとマークされる。実際には、適用ノードは１よりも大きな結果カウントを伴って現れることはない。しかしながら、スタックノードはこれを伴って現れるが、これはスタックノードに関連の出力カウントはこれが率いるサブツリーの合計であるためである。
【００３６】
Ｅ−Ｍｏｄｅ命令セットは、スタックのトップの項目を並べ替える１組の命令を含む。これらは、ＤＵＰＬ：スタックのトップを複製、ＥＸＣＨ：スタック項目のトップの２つを交換、ＲＳＤＮ：トップから３つの項目を下向きにローテート、およびＲＳＵＰ：トップから３つの項目を上向きにローテート、を含む。これらの命令に対するエイリアスノードは１のインデックスで、命令ノードではなく、もとの項目を直接示す。
【００３７】
図５においては、示されるコードグラフ２８は値の計算と、そのような値の変数への割当てを表わす。グラフ２８は、命令と引数との間の関係およびスタックノードがどのように複数の引数を集めるために用いられるかを示す。特に、コードグラフ２８は次のソースコードステートメントを表わす。
【００３８】
Ａ：＝（Ｂ＊−Ｃ）＋Ｄ
これはＥ−Ｍｏｄｅ命令セットにおいて次のように表わし得る。
【００３９】
ＶＡＬＣ  Ｂ      （値Ｂをスタックに置く）
ＶＡＬＣ  Ｃ      （値Ｃをスタックに置く）
ＣＨＳＮ      （スタックのトップの項目の符号を変える）
ＭＵＬＴ      （スタックのトップから２つの項目を消費して乗算し、結果をスタックに残す）
ＶＡＬＣ  Ｄ      （値Ｄをスタックに置く）
ＡＤＤ      （スタックのトップから２つの項目を消費して加算し、結果をスタックに残す）
ＮＡＭＣ  Ａ      （位置Ａに対する参照をスタックに置く）
ＳＴＯＤ      （スタックのトップから２つの項目を消費し、結果を示される位置にストアする）
図５を参照すると理解されるように、いずれのコードグラフ２８においても、時間的な動作は一般的に、全域木（すなわち、いかなるエイリアスノードもリンクも有さないツリー）の下部右から上部左へという移動方向で、下から上へ行なわれる。しかしながら、トランスレータ１０によって行なわれるバックトラッキング解析は、以下に説明するように、一般的に上から下に行なわれる（すなわち、反時間順で行なわれる）。
【００４０】
図６はブロック２４に対するグラフ２８を表わし、このグラフ２８はＤＵＰＬ（スタックのトップを複写する）命令の効果を表わすエイリアスノードを含む。ＤＵＰＬはその引数を変えることをしないために、エイリアスは直接ＶＡＬＣノードを参照する。ＤＵＰＬの適用自体は、ＡＤＤに対する一方の引数を生成するのに対し、エイリアスは他方を表わすために用いられる。
【００４１】
図７に示すように、スタック内のトップのアイテムを３番目にし、２番目および３番目をそれぞれ１番目および２番目に上げるＲＳＤＮ（スタックを下向きにローテート）の効果を表わすために２つのエイリアスノードが必要である。
【００４２】
図８に示すように、ブロック２４が、引数のいくつかが該ブロック２４によっては供給されない（すなわち、別のブロック２４によってスタックに置かれる）命令を含む場合、グラフ２８は欠落した引数を表わすために「欠落」ノードを用いる。欠落ノードは常に、出力カウントが１であるスタック項目を有する。
【００４３】
図９に示すように、ＴＥＱＵ（等価物を更新しながら移動する）命令はそれだけで、欠落ノードおよびエイリアスノードのいくらか極端な組合せを引き起こす。理解されるように、そのようなＴＥＱＵ命令は４つのスタック引数を消費し、スタックに３つの結果項目を残す。返される項目はもとのどの引数の単なるコピーでもなく、そのためにエイリアスノードはＴＥＱＵの適用を参照し、かつ２番目および３番目の返される項目を示すインデックスを含む。
【００４４】
一般的に、かつ図５から図９に示されるいくつもの例によって示されるように、基本ブロック２４内の命令の各々および該命令がスタックに対して有する効果に基づいて、トランスレータ１０は比較的簡単な態様でそのようなブロック２４を表わすコードグラフ２８を構築し得る。
【００４５】
特別ノードは、トランスレータ１０がコードグラフ２８を構築した後で、一般的に該トランスレータ１０によって用いられるが、「テスト」ノードを含む。複数の基本ブロック２４からのコードグラフ２８が組合わされて経路に沿った命令シーケンスを表わす場合、３つのタイプのテストノードが分岐を表わすために用いられる。そのようなテストノードは、単一の引数に適用される命令として作用し、かつ葉ノードである。テスト真およびテスト偽ノードはそれぞれ、引数は真または偽をもたらすことを経路が推定することを示す。テストインデックスノードは、引数が命令によって担持されるインデックスに等しい整数値をもたらすことを示す。テストノードは、以下により詳しく説明する境界評価に用いられる。
【００４６】
動的分岐行先判断
この発明において、トランスレータ１０がＥ−Ｍｏｄｅ命令セットにコンパイルされたプログラム２０を変換している場合、該トランスレータ１０は、すべてのセグメント２２を同時に解析するのではなく、セグメント２２ごとに解析を行なうことができる。これがＥ−Ｍｏｄｅに関して可能であるのは、Ｅ−Ｍｏｄｅ静的分岐またはオペランド動的分岐の行先のすべてが、該分岐と同じコードセグメント２２に存在するためである。
【００４７】
上述のように、トランスレータ１０は第１に、基本ブロック２４の境界を確立する（以下に説明する１つの例外を除く）（ステップ３０１）。次いでトランスレータ１０は、静的分岐の影響を表わす不完全な制御フローグラフ（ＣＦＧ）２６を確立し、基本ブロック２４の各々の中のコードシーケンスをさらなる解析のためにグラフ２８に変換する（ステップ３０７）。制御フローの目的のために、プロシジャコールは、基本ブロックを終了させるが、次にフォールスルーするようモデル化される。これに対する唯一の例外は、コールポイントに戻らない、オペレーティングシステムルーチンに対するプロシジャコールとして、いわゆる「好ましくないｇｏｔｏ」（Ｃでは「ｌｏｎｇｊｍｐ」）が実現されることである。これは特定的に、無条件分岐として認識され扱われなければならないが、これは最初にプログラム２０を生成したコンパイラが、スタックが縮むであろうことを知っていて、ときに該スタックを後のブロック２４の要件に整合しない状態で残すためである。トランスレータ１０によって生成されるＣＦＧ２６は、プロシジャコールによって引起されるブロック２４の間の関係をモデル化しない。すなわち、コールブロック２４からそのターゲットへの枝は存在せず、ターゲットからリターンポイントに戻る枝も存在しない。そのようなモデリングが要求されないのは、実務においてはそのような関係は動的分岐行先の判断のためにいかなる役割も果たさないためである。
【００４８】
図４に示されるようにＣＦＧ２６は、基本ブロック２４の間の動的な「続く」関係を示すために、当然有向である。ＰＣＷが存在するいずれのブロック２４も根として扱われる。不完全なＣＦＧ２６におけるいくつかの基本ブロック２４は、いくつかの根、ときにはいかなる根からも、到達不可能であるかもしれない。これが起こるのは、動的分岐によって欠落した接続のためか、または単一のコードセグメント２２内に複数のプロシジャが存在するためか、または最初にプログラム２０を生成したコンパイラが到達不可能なコードをなくすことに対して厳密ではなかったためである。
【００４９】
不完全なＣＦＧ２６内において、ＰＣＷから到達可能であるブロック２４は活性であるとマークされる。いくつかの活性ブロック２４は、未だ活性ではない（活性になることはないかもしれない）ブロック２４から到達可能であり得る。初期のトランスレータ解析（ステップ３０１）が、実際には複数のブロック２４であるコードシーケンスを、単一の基本ブロック２４をであると識別することもあり得る。これは（非分岐テーブル）動的分岐が、ブロック２４と思われたものの中間に行先を有していた場合に、最終的に判明するであろう。そのようなブロック２４は２つに分割されねばならず、ＣＦＧ２６および他の構造は適切に調整される。
【００５０】
好ましくは、トランスレータ１０は動的分岐の各々を、これらが活性になった場合にのみ解析する。これにより、ＣＦＧ２６内の新しいリンクの発見に基づいてすべての動的分岐を反復的に解析する必要性を最小化する。
【００５１】
好ましくは、図１０を参照すると、一旦動的分岐が識別されると（ステップ１００１）、トランスレータ１０によって用いられる一般的な解析方法は、動的分岐につながるすべての命令シーケンスを、引数のタイプ、およびもしこれがオペランドであればそのようなオペランドがとり得る範囲または１組の値を、十分に判断するために必要な限り広く探索する（ステップ１００３）。一旦動的分岐からのすべての可能性のある行先が規定されると、トランスレータ１０は次いでそのような行先の有効性を調べ、可能性のある分岐テーブルを識別する（ステップ１００５）。最終的に、動的分岐は意図された効果のより的確な表示によってコードグラフ２８内で置き換えられ、ＣＦＧ２６は、必要なだけ活性を伝播させて、実際の行先の組を示すよう更新される（ステップ１００７）。したがって、トランスレータ１０は、プログラミングコードを第１のコード状態１２から第２のコード状態１４に変換する場合に、最終的に動的分岐に伴うすべての行先を発見する（ステップ１００９）。
【００５２】
引数の判断
第１の目的は、動的分岐に対する引数のタイプ、すなわちオペランドかＰＣＷかを判断することである。トランスレータ１０はオペランドが、ＶＡＬＣ（値をスタック上に置く）、「リテラル」命令（その即値パラメータをオペランドとしてスタックのトップに残す）、ＡＤＤなどのような、演算命令または表現によって生成されたもの、または算術比較によって明示的に境界チェックされていることにより生成されたものとして認識する。（非直接的参照を生成する）ＮＡＭＣによって生成された動的分岐引数は常にＰＣＷになり、オペランドになると判断できないすべての引数はＰＣＷであると推定される。
【００５３】
コンパイラによって用いられるいくつものイディオムがあるが、これらは命令のすべての起こり得る組合せごとの、完全な可能性のあるセマンティック解析の要件を回避できるので、トランスレータ１０の解析プロセスをいくらか簡略化する。たとえば、分岐テーブルへの分岐に対して先行するコードは常に、明示的にまたは暗示的に、分岐引数の境界を規定する。この必要性は、Ｅ−Ｍｏｄｅおよび他の現代的な命令セットの基本的なマルチプロセシング、共有メモリ性から生じる。ブロック２４に分岐テーブルに対する明示的な境界付与コードが現れる場合、これは常に動的分岐の直前に存在し、位置の突き止めと解析とを容易にする。
【００５４】
明示的境界付与のための、比較と条件付分岐とのさまざまな組合せを用い、おそらくは上限および下限テストを組合せるための論理演算を備えた、いくつものモデルが存在する。別アプローチは、引数に最小および最大の関数を適用して、いずれの端部において１つの位置分だけ公称の分岐テーブル範囲を超える範囲に入るようにすることである。分岐テーブルは整合するよう拡張され、余分な要素は両方とも「その他」コードに分岐する。
【００５５】
境界のいずれかまたはその両方は、引数を構成するために用いられる命令から推論し得る。特定的に用いられるのはビットフィールド分離命令であって、これは結果を小さな整数の演算範囲に拘束する。他の命令は、引数が正であること（下限が０）を強制するかもしれない。そのような知識を用いて、明示的境界チェックを完全になくすことができる。代わりに、分岐テーブルは引数の実際の範囲に整合するために必要なだけ、または上限か下限のいずれかをチェックするために必要なだけ、拡張し得る。
【００５６】
別のイディオムの例は、ＣＯＢＯＬのＰＥＲＦＯＲＭ動詞に関する。そのような動詞は、リターンポイントを示すＰＣＷとＰＥＲＦＯＲＭ範囲を終了させる段落を識別する整数とを、スタックのトップにプッシュすることにより実現される。次いでＰＥＲＦＯＲＭ範囲の第１の段落は、（行先が同じコードセグメントであった場合）静的分岐、またはＭＰＣＷ（ＰＣＷを作る）と動的分岐との組合せのいずれかに分岐する。コードセグメントの制御フローグラフの目的のために、この構成はプロシジャコールのようにふるまい、この実行は分岐の後に続く命令で最終的に再開することを認識することが重要である。ＣＯＢＯＬのＰＥＲＦＯＲＭシーケンスからの出口は常にスタック項目のトップのテストをして、これが現在の段落で終了するＰＥＲＦＯＲＭを表わすかどうかを判断することである。そうであれば、その項目は削除され、常にＰＣＷを見出すと期待される動的分岐が後に続く。
【００５７】
別のイディオムの例はクロスセグメントコールに関する。ブロック構造言語（ＡＬＧＯＬ、ＮＥＷＰ）に対するコンパイラのいくつかは、内部ブロックに対するコードを別々のコードセグメント２４に入れるので、エントリおよびリターンの両方に対してＰＣＷ動的分岐を必要とし得る。エントリコードは２つの連続するＭＰＣＷであり、第１のものはリターンポイントを示し、第２のものは内部ブロックの開始とＤＢＵＮ（動的分岐無条件）とを示す。リターンポイントは常に、ＤＢＵＮの後にすぐに続く命令である。ＣＯＢＯＬのＰＥＲＦＯＲＭと同様に、最終的に次の命令において実行が再開することを認識することが重要である。別のコードセグメント内の内部ブロックからの出口は、単にＤＢＵＮであって、その引数は同じコードセグメント２２内のＤＢＵＮに先立つコードによっては与えられない。そのようなＤＢＵＮは、エントリシーケンスによって残されたリターンＰＣＷを見出すことを期待する。トランスレータ１０は、ＤＢＵＮに対する引数が、このコードセグメント２２内の基本ブロックによって与えられていないことを見出さねばならず、したがって、この状況が発生したことを演繹しなければならない。
【００５８】
別のイディオムは、ＰＣＷのｇｏｔｏに関する。異なったコードセグメントへの明示的なプログラマーによって特定される分岐、またはコンパイラによって生成されるもののどちらの場合であっても、コードは次の２つのうち１つの形を取る。すなわち、ＮＡＭＣ；ＤＢＵＮまたは、ＭＰＣＷ；ＤＢＵＮのいずれかである。両方とも即座にＰＣＷのケースとして認識可能であり、さらなる解析は必要ではない。
【００５９】
経路解析
経路解析を行なうにおいて、この発明のトランスレータは不完全なＣＦＧ２６を、該当の動的分岐を含んだブロック２４に根を有し、ＣＦＧ２６における対応の枝を逆にした枝を備えた、有向グラフとして扱う。探索は深さ優先であり、該当の動的分岐に対する引数のすべてのソースとなり得るものを見出すまで必要な限り深く行なわれる。逆の枝に出会うと、その経路はループであると宣言され、無視される。
【００６０】
経路がソースを供給することなく終了すると、次の２つの状況のうちの１つであり得る。トランスレータ１０は、まだ評価されていない動的分岐を介してのみ到達可能であるブロック２４に出会ったか、またはどこかからのＰＣＷ動的分岐によってコードセグメントが入れられたポイントに来たか、である。後者の場合は、現在の動的分岐がセグメント出口（ＰＣＷ）であり、デフォールトになるであろうことを示すことから、無視し得る。前者の場合には、複数の動的分岐の間の相互作用を見出すために、反復的に解析を行なうことが必要となり得る。
【００６１】
一旦トランスレータ１０が該当の動的分岐へのすべての経路を探索し終わると、タイプおよびおそらくは境界情報が各々に付与された０以上の経路が存在する。もし１つも存在しなければ、トランスレータ１０はセグメント出口を推定し（ＰＣＷはコードセグメント２２が入れられたときにスタックに残された）、分岐タイプはＰＣＷであると想定する。ＰＣＷは後に変換され、かつＣＦＧ２６はコードセグメント２２を超えて延在せずこうして更新される必要がないことから、これ以上のことをこの場合に関して行なう必要はない。ＮＡＭＣまたはＭＰＣＷのいずれかが先行する動的分岐の明示的な場合は、もちろん動的分岐のＰＣＷ形式である。
【００６２】
もし該当の動的分岐から戻ってくる経路のすべてが、上限および下限境界が各々の経路内で等しい（しかしさまざまな経路の間では異なる）整数境界を示すと、ソースはリテラルであって、ケースはステート表示がスタックのトップに残される有限状態機械である。次いでトランスレータ１０はリテラルを与える命令を識別して、変更されたコードアドレスを反映するようリテラル値をコード変換と生成との間に更新する。
【００６３】
もし１つの経路しか存在せず、かつそのソースが下限チェックされたＶＡＬＣ（ローカル変数からのオペランドのフェッチ）であれば、これはステート表示がローカルな一時記憶にストアされる有限状態機械の形式である。これはＡＬＧＯＬイディオムである。動的分岐に到達するブロック２４内の一時的なセルへのストアのすべては、トランスレータ１０によって調べられねばならず、ストアされるリテラルは更新のために上述のように識別されなければならない。これは、ＡＬＧＯＬコンパイラがこのスタックセルを、他のいかなるもののためにも用いず、特定的にこの構造の一例のためにのみ専用に用いるために働くことに留意されたい。
【００６４】
もし１つの経路が存在し、これが完全に境界されていれば、分岐テーブルが表示される。
【００６５】
プロシジャコールから何が返されるか（スタック上の１つまたは０の結果）に伴う不確実性のために、ＰＣＷとオペランド形式との両方をはっきりと示す経路を有することもありえる。プロシジャコールは、ソースと、分岐テーブルまたはローカル変数有限状態機械のいずれかに対する動的分岐との間に介入しないことから、選択は明示的なＰＣＷまたは有限状態機械のスタックのトップのいずれかのみにある。好ましくは、かついくらかヒューリスティックに、トランスレータ１０は定数のリストは正しい答であると推定し、よってこのケースはスタック有限状態機械のトップであると解される。
【００６６】
コードグラフ生成
ブロック２４の命令の各々を、先行の命令から結果として生じたコードグラフ２８（命令に対する引数としての作用を果たす）に順に与えることにより、基本ブロック２４に対するコードグラフ２８が生成される。プロセスは基本ブロック２４の中の第１の命令と空のコードグラフ２８とによって開始され、実行の順序で基本ブロック２４の命令を通して進行する。
【００６７】
命令の各々が調べられて、どれだけのスタック入力が必要とされるかが判断される。次いで引数コードグラフ２８は、スタック上の（先行の命令によって生成された）さまざまな項目に対応する別々のサブグループに分解される。ちょうど十分なだけの項目が引数コードグラフ２８によって表わされていると、これは直接引数として用いられる。もし命令によって要求されるよりも多い項目が引数コードグラフ２８によって表わされていると、要求されているだけの数が（すなわち、スタックのトップから）用いられ、残りは保持される。後の基本ブロック２４内の命令によって引数が与えられることを示して、命令によって要求されるよりも少ない数の項目が引数によって表わされていると、欠損に対処するよう十分な「欠落」ノードが与えられる。
【００６８】
引数コードグラフ２８からのいくつかのサブグラフは、スタック上に何の項目も返さないかもしれないことに留意することが重要である。これらは（スタックノードで接続されて）スタック上に実際に項目を返す次のサブグラフ上にスタックされ、該当の命令に対応する引数を形成する。
【００６９】
該当の命令のために複数の引数が要求されると、それらは最終的な引数を形成するために適切な順序でスタックされる。１つのスタック引数のみが要求されると、該１つのスタック引数を表わすサブグラフが最終的な引数である。いずれの場合においても、左に命令および右に引数を備えた適用ノードを構築することにより、適用コードグラフ２８が形成される。スタック引数が要求されなければ、該当の命令自体が結果である。
【００７０】
もし該当の命令がスタックに１つ以上の項目を返すと、適用ノードの上にエイリアスノードが要求に応じてスタックされる。
【００７１】
最終的に、元のコードグラフ２８からの残りは（要求された引数が抽出された後に）、もしあれば、適用結果の下にスタックされて基本ブロック２４の開始から処理された分の命令に対してコードグラフ２８を生成する。
【００７２】
経路に沿った複数の基本ブロック２４に対するコードグラフが組合されて単一のコードグラフ２８を形成すると、プロセスは後続の基本ブロック２４を表わすコードグラフ２８の、先行の基本ブロック２４を表わすコードグラフ２８への適用として説明される。プロセスは上述のように空の引数グラフによって開始する。次いで基本ブロック２４の各々からのコードグラフ２８は、ここで説明されたように先行のものから後続のものへ連続的に与えられる。プロセスは上述のものと同様である。コードグラフ２８の各々は、コードグラフ２８が生成された基本ブロック２４における命令の出現の順序に対応して右から左にトラバースされる。この移動中に出会う命令の各々は、いくらかの変更を加えて、上述のように引数グラフに加えられる。
【００７３】
無条件分岐に出会うとこれは単に無視されるが、これは関連する２つの基本ブロック２４が連続物によって表わされる経路に沿った実行の効果が、あたかも基本ブロック２４が隣接している、すなわち１つから分岐なしに隣に入るのと同じであるためである。もし条件付分岐または動的分岐に出会うと、どのように実行が先行の基本ブロック２４から後続の基本ブロック２４へ分岐を介して進むかという想定に基づいて、適切なテストノードに置き換えられる。特定的には、もしプログラムがＢＲＴＲ（真なら分岐）から分岐すると推定されると、置き換えられるテストノードはＴＴ（テスト真）である。したがって、もしプログラムが該ＢＲＴＲからフォールスルーすると推定されると、置き換えられるテストノードはＴＦ（テスト真）である。もちろんＢＲＦＬ（偽なら分岐）からの逆もまた真である。
【００７４】
境界評価
好ましくは、図１５を参照すると、トランスレータは「プロップ」のリストに従って境界評価を行なう（ステップ１５０１）。プロップの各々は、適用されるグラフ内のノード（「ターゲット」）と、そのノードに適用される１組の境界とを示す。境界は、上限および下限のいずれかまたはその両方を含み得る。
【００７５】
リストのプロップの各々に関しては、コードグラフ２８内のノードの各々はトラバースする（ステップ１５０５）。ノードの種類と、これがプロップによって示されるターゲットノードであるかどうかに応じて、動作が行なわれる。エイリアスノードおよびリンクを無視することによりコードグラフ２８上に規定される全域木の右から左への方向で、コードグラフ２８はトラバースされる。スタックおよび直接（セレクタ１）エイリアスノードは、プロップのターゲットにはなり得ないことに留意されたい。
【００７６】
調べられているノードがプロップのターゲットであると、これは適用ノード（引数上の命令の適用）か、またはいかなる引数も取らない単なる命令かである。後者の場合は興味深くはなく、以下に示すように境界を更新するという点を除いては、さらには動作を必要としない。適用ノードに関しては、枝を張る命令とその引数とは調べられて、適用ノードに課せられるべき（プロップ内の）境界情報を、その引数に対して既に利用可能であるいずれかの境界情報と組合せることが可能であるかどうか判断する。望ましくは、そのような組合せを用いて１つ以上の引数に対してよりよい境界情報を提供し得る（ステップ１５０７）。たとえば、１対の引数に対してＡＤＤ命令を適用し（結果にいくらかの束縛を課す）、このうちの一方が何らかの境界情報を有していると、他方の引数に対しても何らかの境界情報を演繹することができる。同様に、算術比較命令に関しては、もしこの比較の結果が真であるとわかっており（上限および下限＝１）、かつ引数の一方がリテラルであるか、または部分的にでも境界内の表現であれば、何らかの境界情報を他方の引数に対して演繹し得る。もしいずれかの新しい境界情報を演繹し得るのであれば、引数ノードに対してそのような境界情報を含むプロップが必要なだけ生成されて、最終的な処理のためにリストに加えられる（ステップ１５１１）。ターゲットノードに対する境界情報は、プロップから変更／更新される（ステップ１５０９）。トラバースは、適用ノードまたはターゲットを参照するスタックノードに戻る。
【００７７】
もし調べられているノードがターゲットではなければ、行なわれる動作はノードのタイプに依存する。スタックノードに関しては、トラバースはスタックノードの左側を調べ、次いで右側を調べることにより行なわれる。もし調べられたノードが直接（セレクタ１）ノードであり、エイリアスリンクによって示されるノードがターゲットであれば、エイリアス自体の境界情報がプロップから更新される。
【００７８】
もし調べられているノードがターゲットではなく適用ノードであると、行なわれる動作は適用ノードの左側に依存する。もし左側がテストノードであってこれが初期のトラバースであれば（プロップが存在しない）、テストノードに依存する境界（上限と下限は同じ）を備えたプロップがその引数に対して生成される。テスト真により１の境界が生じ、テスト偽により０の境界が生じ、テストインデックスはテストノード内で示されるインデックスに等しい境界を生じさせる。ターゲットノードではなく、テストノードを適用もしない適用ノードに関しては、トラバースは適用ノードへの引数に対して続けられる。
【００７９】
いずれの場合においても、トラバースが後退するにつれ、境界の変化はグラフを通して上向きに伝播する。すなわち、適用ノードへの引数内で境界情報が変化すると、その情報は与えられる命令の定義とともに用いられて、適用の結果（適用ノード自体）を更新する。適用ノードがエイリアスリンクのターゲットでもあれば、その適用ノードに対してプロップが生成されて、エイリアス自体が最終的に更新される。
【００８０】
ノードに対して変更／更新する境界は、範囲を狭めることだけが可能である（上限境界を引下げるか、または下限境界を引上げる）。もし結果として上限および下限境界が矛盾すると（下限＞上限）、そのノードに対するすべての境界情報は捨てられる。次いでそのような矛盾するノードは、動的分岐の行先の総合的な判断に対して貢献しないと推定される。
【００８１】
好ましくは、グラフ２８上の最初のトラバースは、テストノードに対するプロップを累算する目的のみで、空のプロップで始まる（ステップ１５０３）。通常のグラフ構造は、引数から利用可能であるすべての境界情報を用いて、命令の適用に対する初期の境界を決定することに留意されたい。グラフがテストノードを含んでいなければ、その構造は既にすべての境界情報に与えられている。
【００８２】
境界評価プロセスは、単に動的分岐の可能性のある行先を判断する目的であるために、そのような判断に対し貢献しないいかなる命令をも無視することが好ましい。理解されるように、コンパイラが境界付与（比較、条件付分岐など）および正規化（リテラルの加算および減算）のために用いる、またはコンパイラが当然境界内の結果を有すると認識するような１組の命令が存在する。その他のすべては無視し得る。
【００８３】
当然境界内にある結果を備えた命令は、リテラル、比較（０または１のいずれかをもたらす）、および結果が限定された数のビットで表わされる他いかなる命令をも含む。境界情報は、通常のグラフ構築の間に付与される。
【００８４】
通常のコードグラフ構造と、グラフトラバースが後退した場合の境界情報の上向きの伝播との両方とも、ノードの引数を調べることにより有用な境界を演繹しようと試みるが、該境界は命令のその引数への適用に対するものである。このプロセスは、縮退する場合、命令をリテラル引数に適用することを含むが、この性質の適用はまた、一般的に定数にまとめられる。有用な命令セットは、ＡＤＤ／ＳＵＢＴ、ＭＵＬＴ、算術比較、ＡＭＩＮ／ＡＭＡＸ、特定のビット調整命令、および論理を含む。
【００８５】
いずれの所与のノードに対しても、境界が収束したときにプロセスは終了されなければならないが、これは範囲が広げられることがないためである。この時点で、このノードの解析はこれ以上のプロップは生成しない。コードグラフ２８は有限であり固定されているので、全体的な処理は終了する。
【００８６】
分岐タイプ判断
特定の動的分岐に対するすべての可能性のあるソースが探索されると、その結果は経路の集合であり、その各々がどのような種類のソースが見出されたかの何らかの表示を備える。それらは以下のものであり得る。
【００８７】
・完全に境界内にあり、唯一の経路であり、分岐テーブルを示す、演算ソース。
【００８８】
・完全にまたは部分的に境界内にあり、唯一の経路であり、ローカル変数有限状態機械を示す、ＶＡＬＣ。
【００８９】
・複数のうちの１つであって、スタック有限状態機械のトップを示す、定数整数値。
【００９０】
・ＮＡＭＣまたはＭＰＣＷのいずれかであって、唯一の経路である、明示的ＰＣＷ参照。
【００９１】
・経路は認識可能なソースなしに終了し、セグメント２２が分岐される前にＰＣＷがスタックに残されるクロスセグメントリターンを示す、未知のもの。
【００９２】
プロシジャコールのために、定数整数値と、明示的ＰＣＷと、未知の場合との混合を得ることが可能である。これが起こる場合、未知のケースは捨てられる。もし定数整数ケースがある場合は、明示的ＰＣＷは捨てられる。
【００９３】
例
以下の３つのブロック２４はプログラム２０内でシーケンシャルに流れ、最後のブロック２４は動的分岐で終了すると想定する。
【００９４】
ブロック１：
ＶＡＬＣ  Ａ      （変数Ａの値を得て、スタックに置く）
ＤＵＰＬ      （スタックのトップの値を複写し、スタックに置く）
ＬＴ  ０      （値０をスタックに置く）
ＬＥＳＳ      （スタックのトップから２つの値を消費し、比較して（結果、Ａが０未満であるかどうか）判断し、比較結果をスタックに置く）
ＢＲＴＲ      （スタックのトップを消費しこれに基づいて分岐するか、でなければフォールスルーする）
ブロック２：
ＤＵＰＬ
ＬＴ  １０
ＧＲＴＲ      （スタックのトップから２つの値を消費し、比較して（結果、Ａが１０よりも大きいどうか）判断し、比較結果をスタックに置く）
ＢＲＴＲ
ブロック３：
ＬＴ  ５０      （予め定められたオフセット値５０をスタックに置く）
ＡＤＤ      （スタックのトップの２つの値を消費し、加算して結果をスタックに置く）
ＤＢＵＮ      （スタックのトップを消費し、動的分岐のアドレスとして使用する）
したがって、ブロック１においては、値Ａが下端で境界から逸脱している（すなわち、０未満）かどうかをテストし、ブロック２においては、値Ａが上端で境界から逸脱している（すなわち、１０以上）かどうかをテストする。もしいずれかの端で境界から逸脱していれば、プログラム２０はどこかで分岐する。そうでなければ、プログラムはブロック３にフォールスルーし、ここで値Ａは予め定められたオフセット値によってオフセットされ、その結果はここでは特定されない分岐テーブルへの動的分岐のアドレスとして用いられる。理解されるように、ブロック１−３は大まかに図４におけるブロックＥ、ＦおよびＧに対応する。
【００９５】
おそらく、上述のブロックを有するプログラム２０の解析においては、トランスレータ１０はブロック３において動的分岐を見出し、上述のようにより完全にＣＦＧ２６を特定するために該動的分岐を最終的に調べるであろう。これを行なうにおいて、トランスレータ１０はそれぞれ図１１Ａ−図１１Ｃに示すように、（他のものの中から）ブロック１−３の各々に対して、コードグラフ２８を構築するであろう。トランスレータ１０は次いでＤＢＵＮ命令に提供し得るすべてのあり得る値を規定するために、すべての適切なコードグラフ２８を解析するであろう。
【００９６】
他のブロック２４もまた、この例に示す該当の動的分岐に向けて流れることも十分にあり得る。そのような場合においては、トランスレータは必要なだけそのような他のブロック２４をも解析する。しかしながら、簡略化のために、この例はブロック１−３にのみ焦点を当てる。
【００９７】
図１４を参照するとここで、トランスレータ１０による解析は、動的分岐を有するブロック（ブロック３）において、分岐アドレスを計算するために必要な値に関する情報がどこかで（すなわち、プログラム２０のフローの中の先行のブロックから）供給されるか、さもなければ、不十分に規定されていることを見出すことで開始する（ステップ１４０１）。そのような必要な値に関する情報は、図１１Ｃの最下部の欠落ノードによって表わされる。
【００９８】
該欠落ノードに関する情報を得るために、ブロック３を含むＣＦＧ２６を調べて判断し得るように、トランスレータ１０は、図１１Ｂに示すブロック２である直前のブロック２４を見る（ステップ１４０３）。特に、トランスレータ１０は、ブロック３およびブロック２（図１１Ｃおよび図１１Ｂ）の両方に対してコードグラフ２８を有する新しいコードグラフ２８を構築する（ステップ１４０５）。図１２に示すように、トランスレータ１０は、ブロック３（図１１Ｃ）に対するコードグラフ２８の最下部の欠落ノードを、ブロック２（図１１Ｂ）に対するコードグラフ２８の頂部のスタックノード、および該スタックノードから流れる他のすべてのノードと置き換える。さらに、トランスレータ１０は、ブロック２（図１１Ｂ）に対するコードグラフ２８内のＢＲＴＲノードを、同じコードグラフ２８内のＧＲＴＲが偽であるという想定に基づいて、テスト偽（ＴＦ）ノードと置き換え、これによりプログラム２０をブロック２のＢＲＴＲでフォールスルーすることを許す（ステップ１４０７、１４０９）。プログラム２０がＢＲＴＲにおいてフォールスルーする代わりに分岐すると想定されていると、テスト真（ＴＴ）ノードが代わりに用いられるであろう。理解されるように、もし命令がＢＲＦＬ（偽に基づく分岐）であれば、その逆が真となる。さらに理解されるように、ＤＢＵＮノードと、ＤＢＵＮノードに枝を張る適用ノードとは、この解析においては必要ではないとして省かれる。すなわち、この解析の最終的な目標とは、ＤＢＵＮ命令に適用される引数を表わす（今やトップの）適用ノードに関連する境界情報を見付けることである。次いでトランスレータ１０は、進んで新しいコードグラフ２８をトラバースする（ステップ１４１１）。
【００９９】
トランスレータ１０は次いで、ブロック２において、分岐アドレスを計算するために必要な値に関する情報が、やはりどこかで（すなわち、プログラム２０のフロー内の先行するブロックから）供給されることを見出す。必要な値に関するそのような情報は、図１１Ｂの最下部と、ここでは図１２の最下部にも見られる欠落ノードによって再び表わされる。重要なことに、トランスレータ１０が欠落した値をまだ規定していないにもかかわらず、そのような欠落した値の範囲を少なくとも狭める情報がここで利用可能である。すなわち、欠落した値は１０未満でなければならない。そうでなければ、プログラム２０はブロック２におけるＧＲＴＲ命令をフォールスルーできない。
【０１００】
ブロック３およびブロック２（図１２）に対するコードグラフ２８の最下部に欠落ノードがまだ存在することから、トランスレータ１０は、ブロック３およびブロック２を含むＣＦＧ２６を調べて再び判断されるように、図１１Ａに示されるブロック１である直前のブロック２４を見る。特に、トランスレータ１０は、ブロック３、２、および１（図１１Ｃ−図１１Ａ）に対するコードグラフ２８を有する新しいコードグラフ２８を再び構築する。特に、図１３に示すように、トランスレータ１０はブロック３および２（図１２）に対するコードグラフ２８の最下部の欠落ノードを、ブロック１（図１１Ａ）に対するコードグラフ２８の頂部のスタックノード、および該スタックノードから流れる他のすべてのノードと置き換える。さらに、トランスレータ１０は再び、ブロック２（図１１Ｂ）に対するコードグラフ２８内のＢＲＴＲノードと、同じコードグラフ２８内のＬＥＳＳが偽であるという推定に基づき、再びテスト偽（ＴＦ）ノードと置き換え、これによりプログラム２０がブロック１内のＢＲＴＲでフォールスルーすることを許す。また示されるように、図１１Ｂおよび図１２からのエイリアスノードは、図１１ＡからのＶＡＬＣノードに枝を張るよう調整されるが、エイリアス化された値は最終的にそのようなＶＡＬＣノードから導出されるためである。さらに、エイリアスおよびスタックノードの各々は、以下の説明の目的のために別個に識別されている。
【０１０１】
再び、トランスレータ１０は、ブロック１において、分岐アドレスを計算するために必要な値がやはりどこかで（すなわち、プログラム２０のフロー内の先行のブロックから）供給されていることを見出す。しかしながら、この場合においては、そのような必要な値は図１１Ｃ、およびここでは図１３の最下部にも存在するＶＡＬＣノードによって表わされる。重要なことに、トランスレータ１０が必要な値をまだ規定していないにも関わらず、該必要な値の範囲を少なくとも狭める付加的な情報が、この時点で存在する。すなわち、該必要な値は０よりも大きくなくてはならない。そうでなければ、プログラム２０はブロック１におけるＧＲＴＲ命令をフォールスルーできない。
【０１０２】
さらに、この時点でトランスレータ１０は、必要な値が０よりも大きく１０未満であることがわかっているために、トランスレータ１０は必要な値の正確な値に関してこれ以上関わる必要はない。こうして、「必要な値」と「必要な値についての情報」とは区別される。簡単にいうと、少なくともブロック１−３によって表わされる経路に従うと、必要な値は設定された上限と設定された下限とを有することがわかれば十分である。重要なことに、上述のＶＡＬＣノードが別の欠落ノードに代わっても、これは真である。もちろん、もし他の経路が存在すれば、該他の経路はより広い境界をもたらす可能性があるために、該他の経路はトランスレータ１０によってトラバースされねばならない。
【０１０３】
一旦ブロック３のコードグラフ２８の最下部の欠落ノードの最も広い境界が規定されると、トランスレータ１０は、該ブロック３における動的分岐（ＤＢＵＮ）に対して示し得るアドレスの範囲を計算し得る。特に、もし該欠落ノードが０から１０までの間の値を取り得ると、スタックにおかれたリテラル値が５０であることから、ＡＤＤ命令はスタックに５０から６０の間の値を返す。該５０から６０の間の値は、動的分岐に示されるアドレスの範囲であって、そのような情報に基づいてトランスレータ１０は関連の分岐テーブルの位置を突き止め、それによりこれに従ってＣＦＧ２６を更新し得る。
【０１０４】
これを行なうにおいて、以前は到達不可能であったブロック２４がこの時点で到達可能であることも十分起こり得る。該この時点で到達可能なブロック２４は当然、活性であるとマークされる。該この時点で活性であるブロック２８が１つ以上の動的分岐を有することも起こり得るが、この場合、トランスレータ１０によって解析されねばならない。
【０１０５】
この例はここまで叙述形式で解析されてきたが、トランスレータ１０は解析を実行するためにアルゴリズムを用い、トランスレータ１０は（上述のプロップを介して）境界情報をコードグラフ２８を通して下向きに伝え、かつ変化を該コードグラフ２８を通して上向きに伝播させようと試みることに留意されたい。予備的に、そのようなアルゴリズムは、動的分岐を有するブロック（例中のブロック３）に対するコードグラフ２８に対して行なわれることを理解されたい。もし結果が確定的でなければ、トランスレータ１０はＣＦＧ２６内で後向きに進み、確定的な結果が得られるまで、組合されたコードグラフ２８（図１２および図１３内のものなど）を解析する。しかしながら、理解を明快にするために、この解析は図１３に示すコードグラフ２８に対してのみ焦点を当てる。
【０１０６】
予備的に、トランスレータ１０はコードグラフ２８の最下部に向かって、命令（すなわち、下および左に存在するもの）が「重要な」適用ノードを探して、トラバースする。ここでは、テストノードのみが重要とみなされる。これを行なうにおいて、トランスレータ１０は上側ＴＦノードおよび下側ＴＦノードの存在を見出す。トランスレータ１０は次いで、調べるために興味深いノードのうちの１つを選択する。下側ＴＦノードが最初に選択されたと想定すると、トランスレータ１０は、下側ＴＦノードの引数である（すなわち、右）適用ノード（ａ６）が該ＴＦノードを満たすために偽（０）でなければならないということを認識して、該ＴＦノードを調べ始める。したがってトランスレータは、ａ６が０の上限および下限を有することを意味するよう、境界情報をａ６に付与する。
【０１０７】
次いでトランスレータ１０は、ａ６の命令（下および左側のＬＥＳＳ）と引数（スタックノードｓ５の下に、右に向かって下がる０ノードおよびａ７ノード）とを調べなければならないことを認識する。これを行なうにおいて、トランスレータ１０はａ７がＬＥＳＳノードを満たすために０以上でなければならないことを認識する。したがってトランスレータ１０は、ａ７が０の下限と未知の上限を有することを意味するよう、境界情報をａ７に付与する。
【０１０８】
ここで、トランスレータ１０がａ７が引数ＶＡＬＣ（定められていない値）に対する命令ＤＵＰＬ（複写）の適用であると認識していることから、トランスレータ１０はさらに、ＶＡＬＣがａ７と同じノード情報を有さねばならないことを認識する。トランスレータ１０はしたがって、ＶＡＬＣが０の下限と未知の上限を有することを意味するよう、境界情報をＶＡＬＣに付与する。
【０１０９】
次いで、トランスレータ１０はスタックノードｓ４から続く下側エイリアスノード（および、スタックノードｓ２から続く上側エイリアスノード）がＶＡＬＣを指すことを認識する。スタックノードｓ２は、ＴＦ命令の結果である適用ノードａ５に続くことから、トランスレータはａ５を無視可能であり、かつｓ４はＶＡＬＣと同じノード情報を有さねばならないことを認識する。トランスレータはしたがって、ｓ４が０の下限と、未知の上限を有することを意味するよう、境界情報をｓ４に付与する。同じ理由から、トランスレータ１０は同様に、ｓ２が０の下限と未知の上限とを有することを意味するよう、境界情報をｓ２に付与する。
【０１１０】
次いでトランスレータ１０は、ＴＦノードに対する引数（すなわち、右）である適用ノード（ａ３）が該ＴＦノードを満たすために、偽（０）でなければならないことを認識することにより、上側ＴＦノードを調べ始める。したがってトランスレータは、ａ３が０の上限と下限とを有することを意味するよう、境界情報をａ３に付与する。
【０１１１】
次いでトランスレータ１０は、ａ３の命令（下および左のＧＲＴＲ）と引数（１０ノードと、スタックノードｓ３から下がる下および右のａ４ノード）とを調べなければならないことを認識する。これを行なうにおいて、トランスレータ１０は、ＧＲＴＲノードを満たすためにａ４は１０未満でなければならないことを認識する。トランスレータ１０はしたがって、ａ４が１０の上限と未知の下限とを有することを意味するよう、境界情報をａ４に付与する。
【０１１２】
ここで、トランスレータ１０は、ａ４がスタックノードｓ４への命令ＤＵＰＬ（複写）の適用であると認識していることから、トランスレータ１０はｓ４がａ７と同じノード情報を有さねばならないことをさらに認識する。さらに、ｓ４が既に境界情報（下限は０、上限は未知）を有するために、トランスレータは従って、ｓ４が０の下限と１０の上限を有する意味でｓ４の境界情報を更新する。
【０１１３】
次いで、トランスレータ１０は再び、ｓ４からつながる下側エイリアスノードがＶＡＬＣを指し、スタックｓ２からつながる上側エイリアスノードもまたＶＡＬＣを指すことを認識する。トランスレータ１０は次いで、ＶＡＬＣ、ｓ２、およびｓ４はすべて同じ境界情報を有さねばならないことを認識し、したがってｓ２の境界情報を、ｓ２が０の下限と１０の上限とを有する意味で更新する。
【０１１４】
トランスレータ１０は次いで、ａ１の命令（左下のＡＤＤ）と、引数（スタックノードｓ３から下がる、５０ノードおよび下および右のｓ２ノード）とを調べなければならないことを認識する。これを行なうにおいて、トランスレータ１０はＡＤＤ命令の結果は、スタックノードｓ２＋５０によって表わされるものであることを認識する。ｓ２は０の下限と１０の上限を有することから、次いでトランスレータ１０はしたがってａ４が５０の下限と６０の上限とを有することを意味するよう、境界情報をａ１に付与する。
【０１１５】
そのような５０および６０のａ１境界は、動的分岐に示されるアドレスの範囲であり、そのような情報に基づいて、トランスレータ１０は関連の分岐テーブルの位置を突き止めることが可能であり、それによりこれに従ってＣＦＧ２６を更新し得る。
【０１１６】
この例から、もしトランスレータ１０が動的分岐の境界を過度に狭く規定すると、分岐テーブル情報が失われてＣＦＧ２６が不完全になることを認識されたい。しかしながら、もしトランスレータ１０が動的分岐の境界を過度に広く規定すると、分岐テーブル情報は失われず、ＣＦＧ２６は不完全にはならない。その代わりに、分岐テーブルに隣接する情報は分岐テーブル情報であると誤って解釈され、ＣＦＧ２６は害のないごみで更新されるおそれがある。しかしながら好ましくは、トランスレータ１０は該隣接する情報が分岐テーブルの一部であるとは認識せず、該隣接する情報を無視する。
【０１１７】
もちろん、さまざまな変更とショートカットが存在する。たとえば、もし第１の動的分岐から戻る経路が第２の動的分岐に向かってていれば、そのような第２の動的分岐は好ましくは、新しいコードグラフ（図１２または図１３）内のトランスレータによって、第１の動的分岐に向かってフォールスルーするために必要である値を有するテストインデックスノードと置き換えられる。
【０１１８】
もしトランスレータ１０が必要な値を見出し、必要な値がたとえば４ビット幅（０−１５）であるとわかれば、トランスレータ１０はコードグラフ解析を行なわず、代わりに必要な値は０から１５の間であると推定する。
【０１１９】
もしトランスレータ１０がコードグラフ２８のトラバースにおいてプロシジャコールに出会えば、不確定性が生じるが、これは該プロシジャコールはスタックに１つの結果を返すか、全く返さないかのいずれかであり得るためである。位置がランタイムまで定められないために、プロシジャコールについては追跡できない。この場合には、プロシジャコールが何を戻すかについて他に何もわかっていなければ、トランスレータ１０は好ましくは両方の場合（０またはスタック上の１つの結果）の効果を調べ、効果を比較し、コンテクストに整合する方を選択する。大抵、この選択は明確である。
【０１２０】
ときには、トランスレータ１０は関連の境界付与およびオフセッティングコードなしに動的分岐に出会う。代わりに、動的分岐はいくつかの異なったブロック２４から流れ、該ブロックの各々は動的分岐が動作するためにスタックの上に予め定められたアドレス値のみをストアする。そのような場合においては、トランスレータは好ましくはこれが有限状態機械に出会ったことを認めるであろう。そのようなマシンにおいては、動的分岐は分岐テーブルには向かわず、各々がそのようなマシンの一部であろういくつかの他のブロック２４に直接向かう。トランスレータ１０は次いで、動的分岐によって動作し得る特定のアドレスの全領域を得るために必要な範囲まで、該動的分岐につながるすべての経路のコードグラフ２８をトラバースするだけでよい。
【０１２１】
先の記載において、この発明はコンパイルされたプログラミングコードを第１のコード状態から第２のコード状態に変換するための、新しく有用な方法およびトランスレータを含むことが理解されるであろう。この発明の概念から逸脱することなく、上述の実施例に変更を行ない得ることが理解されるであろう。したがって、この発明は開示される特定の実施例に限定されるものではなく、前掲の特許請求の範囲に定義されるこの発明の精神および範囲内に変更を包含することが意図されることを理解されたい。
【図面の簡単な説明】
【図１】  プロセッサ上で動作し、プログラムを第１の状態から第２の状態に変換する、この発明に従ったトランスレータを示すブロック図である。
【図２】  図１の第１の状態で現われ得る、典型的なプログラムの構造を示すブロック図である。
【図３】  図１のトランスレータによって行なわれる予備的なステップを示すフロー図である。
【図４】  特定のコードセグメントに対して図１のトランスレータによって構築される、制御フローグラフ（ＣＦＧ）を示す図である。
【図５】  コードの特定の基本ブロックに対して、図１のトランスレータによって構築されるコードグラフの例を示す図である。
【図６】  コードの特定の基本ブロックに対して、図１のトランスレータによって構築されるコードグラフの例を示す図である。
【図７】  コードの特定の基本ブロックに対して、図１のトランスレータによって構築されるコードグラフの例を示す図である。
【図８】  コードの特定の基本ブロックに対して、図１のトランスレータによって構築されるコードグラフの例を示す図である。
【図９】  コードの特定の基本ブロックに対して、図１のトランスレータによって構築されるコードグラフの例を示す図である。
【図１０】  動的分岐の解析において、図１のトランスレータによって行なわれるステップを示すフロー図である。
【図１１】  ＡからＣは、解析されるべき３つの関連したブロックに対する、図１のトランスレータによって構築されるコードグラフを示す図である。
【図１２】  図１１Ａ−図１１Ｃのコードグラフから、図１のトランスレータによって構築された新しい組合されたコードグラフを示す図である。
【図１３】  図１１Ａ−図１１Ｃのコードグラフから、図１のトランスレータによって構築された新しい組合されたコードグラフを示す図である。
【図１４】  動的分岐の解析において、図１のトランスレータによって行なわれるステップを示す付加的なフロー図である。
【図１５】  動的分岐の解析において、図１のトランスレータによって行なわれるステップを示す付加的なフロー図である。
【図１６】  動的分岐の解析において、図１のトランスレータによって行なわれるステップを示す付加的なフロー図である。
【図１】
0003685717.tif 000003
【図２】
0003685717.tif 000004
【図３】
0003685717.tif 000005
【図４】
0003685717.tif 000006
【図５】
0003685717.tif 000007
【図６】
0003685717.tif 000008
【図７】
0003685717.tif 000009
【図８】
0003685717.tif 000010
【図９】
0003685717.tif 000011
【図１０】
0003685717.tif 000012
【図１１】
0003685717.tif 000013
【図１２】
0003685717.tif 000014
【図１３】
0003685717.tif 000015
【図１４】
0003685717.tif 000016
【図１５】
0003685717.tif 000017
【図１６】
0003685717.tif 000018