分岐テーブル

分岐テーブルは、無条件分岐命令のシリアルリストで構成され、シーケンシャルインデックスに命令長（各分岐命令がメモリ内で占めるバイト数）を乗算して作成されたオフセットを使用して分岐します。分岐のためのマシンコード命令は固定長であり、ほとんどのハードウェアで非常に効率的に実行できるという事実に基づいており、シーケンシャルインデックス値に容易に変換できる生データ値を扱う場合に最も役立ちます。このようなデータの場合、分岐テーブルは非常に効率的です。通常、次の 3 つのステップで構成されます。

1. 必要に応じて、入力データが許容範囲内であることを確認するために検証を行います。また、入力値に疑いがない場合は、この手順を省略できます。
2. データを分岐テーブルへのオフセットに変換します。通常、これには命令長を考慮して、乗算またはシフト（実質的には2のべき乗を乗算）を行う処理が含まれます。データが定数の場合、この乗算は実行時コストなしで手動で、またはコンパイラによって実行できます。
3. 分岐テーブルのベースアドレスに、生成されたオフセットを加えたアドレスに分岐します。場合によっては、プログラムカウンタレジスタにオフセットを加算します（ただし、一部の命令セットでは、分岐命令が追加のインデックスレジスタを許可している場合があります）。この最終アドレスは通常、一連の無条件分岐命令のいずれか、またはその直後の命令を指します（テーブルのエントリを1つ節約できます）。

以下の擬似コードは、その概念を説明するものです。

...検証x /* x を値に応じて 0 (無効) または 1、2、3 に変換します。*/ y = x * 4 ; /* 分岐命令の長さ (例: 4) を掛けます */ goto next + y ; /* 分岐命令の「テーブル」に分岐します */ /* 分岐テーブルの開始 */ next : goto codebad ; /* x= 0 (無効) */ goto codeone ; /* x= 1 */ goto codetwo ; /* x= 2 */ ...分岐テーブルの残りの部分codebad : /* 無効な入力を処理します */

分岐テーブルを実装するもう一つの方法は、ポインタの配列から必要な関数のアドレスを取得する方法です。元々は転送ベクトルとして知られていたこの方法は、最近では「ディスパッチテーブル」や「仮想メソッドテーブル」など様々な名称で呼ばれていますが、本質的には全く同じ目的を果たします。このポインタ関数方式を用いることで、マシン命令を1つ削減でき、間接ジャンプ（分岐命令のいずれかへのジャンプ）を回避できます。

結果として得られる関数へのポインタのリストは、直接スレッド化されたコードとほぼ同じであり、概念的には制御テーブルに似ています。

ブランチテーブルを実装するために実際に使用される方法は、通常、以下に基づいています。

• コードが実行されるプロセッサのアーキテクチャ、
• それがコンパイル言語かインタプリタ言語かに関わらず、
• 遅延綴じが関係しているかどうかに関わらず。

プログラマーは、既知の検索キーから正しい選択をコンパイラが十分に行えると信じて、分岐テーブルを作成するかどうかの決定をコンパイラに任せることがよくあります。これは、検索キーの範囲が限られている比較的単純なケースでは、最適化コンパイラには当てはまるかもしれません。しかし、コンパイラは人間ほど賢くなく、「コンテキスト」を深く理解することはできません。例えば、1、2、4、6、7、20、23、40、42、50、1000 のような検索キーの整数値の範囲では、ほとんど利点がないにもかかわらず、空のエントリが過剰に多い (900 以上) 分岐テーブルが生成されると考えるかもしれません。優れた最適化コンパイラは、その場合、値を事前にソートし、 「次善の」オプションとしてバイナリチョップサーチのコードを生成する可能性があります。実際には、アプリケーションは非常に「時間制約」が厳しく、メモリ要件は全く問題にならないかもしれません。^{[ 2 ]}

しかし、少しの「常識」があれば、この特定のケースやその他多くの類似ケースを、非常に大きなコスト削減の可能性を秘めたシンプルな2段階プロセスに変えることができ、最終的な選択はコンパイラに委ねつつも、その決定を大幅に「支援」することができる。

• まず、検索キーが1000かどうかをテストし、適切な分岐を実行します。
• コンパイラが残りの検索キー（1～50）に基づいて分岐テーブルを生成するかどうかを「選択」できるようにします。

同様の手法は、2組の短い範囲があり、それらの範囲間に大きな間隔がある場合にも使用できます。

ブランチテーブルに明確な整数値がない場合でも、何らかの算術変換によって検索キー（または検索キーの一部）から作成することができます。あるいは、データベースの行番号、またはキーの以前の検証中に見つかった検索キーを含む配列のエントリ番号を使用することもできます。

場合によっては、インデックスを作成するためにハッシュテーブルが必要になることがあります。ただし、AZ（またはより長いキーの最初のバイト）のような1バイトの入力値の場合、バイト自体の内容（生データ）を2段階の「単純なハッシュ関数」処理に使用して、ギャップのないブランチテーブルの最終インデックスを取得できます。

1. 生データの文字を数値に変換します（例： ASCII「A」==> 10進数65、16進数0x41）。
2. 数値整数値をインデックスとして、256個のエントリを持つ2バイト配列にアクセスし、2番目のインデックスを取得します（無効なエントリは0（ギャップを表す）、それ以外の場合は1、2、3など）。

配列のサイズは、考えられるすべての8ビットバイトに対応する16ビット符号なし（short）整数を格納するために、(256 × 2)バイト以下になります。検証が不要で、大文字のみを使用する場合は、配列のサイズは(26 × 2) = 52バイトまで小さくできます。

分岐テーブルを用いた分岐手法は、プログラムの流れを変更するため 、つまり無条件​​分岐であるプログラムラベルにジャンプするために最も頻繁に用いられますが 、同じ手法は他の目的にも使用できます。例えば、ドロップスルーが一般的で意図的な、繰り返し命令のシーケンスにおける開始点を選択するために使用できます。これは、ループ展開を行う最適化コンパイラやJITコンパイラなどで利用できます。

8ビットのMicrochip PICアセンブリ言語における分岐テーブルの使用例を以下に示します。

movf INDEX , W ; メモリからインデックス値を W (作業) レジスタに移動します。addwf PCL , F ; プログラムカウンタに加算します。 PIC 命令は 1命令ワードであると仮定します。 ; 乗算を実行する必要はありません。 ; ほとんどのアーキテクチャでは、インデックスをプログラムカウンタに加算する前に何らかの方法で変換します。テーブル; 分岐テーブルは、このラベルでここから始まりますgoto index_zero ; これらの goto 命令はそれぞれ無条件分岐ですgoto index_one ; コードのgoto index_two goto index_threeindex_zero ; INDEX = 0 の場合に必要なアクションを実行するためのコードがここに追加されますreturnインデックス1 ...

注：このコードは、PCL < (table + index_last) の場合にのみ機能します。この条件を満たすには、「org」ディレクティブを使用できます。GOTOが2つの命令ワード（例えばPIC18F）の場合、テーブルエントリの数は128未満に制限されます。PCLを超える上位ビットは、PCLATHの対応する部分によって提供されます。

もう一つの簡単な例として、今回は単なる分岐テーブルではなくジャンプテーブルを示します。これにより、現在アクティブなプロシージャ/関数以外のプログラムブロックを呼び出すことができます。

#include <stdio.h> #include <stdlib.h>typedef void ( * Handler )( void ); /* ハンドラ関数へのポインタ *//* 関数 */ void func3 ( void ) { printf ( "3 \n " ); } void func2 ( void ) { printf ( "2 \n " ); } void func1 ( void ) { printf ( "1 \n " ); } void func0 ( void ) { printf ( "0 \n " ); }ハンドラjump_table [ 4 ] = { func0 , func1 , func2 , func3 };int main ( int argc , char ** argv ) { int value ;/* 最初の引数を0～3の整数（剰余）に変換します */ value = atoi ( argv [ 1 ]) % 4 ;/* 適切な関数（func0～func3）を呼び出す */ jump_table [ value ]();return 0 ; }

PL/I では、ジャンプテーブルはラベル変数の配列として実装されます。これらのラベル変数は、添え字付きのステートメントラベルを使用することで、通常とは異なる方法で初期化できます。PL/I のラベル変数は、単にステートメントのアドレスを示すだけでなく、通常はそれらが属するコードブロックの状態に関する追加情報を含んでいます。このような特殊な初期化を行わない場合、呼び出しとエントリ変数の配列を使用してコーディングすることも可能です。

 ラボ（10）のラベルを宣言します。 xを固定バイナリとして宣言します。 lab(x)へ移動; lab(1): /* 選択肢1のコード */ ; ... lab(2): /* 選択肢2のコード */ ; ...