Loading article…
分岐、ジャンプ、または転送とは、コンピュータプログラム 内の命令で、コンピュータが異なる命令シーケンスの実行を開始し、命令を順番に実行するというデフォルトの動作から逸脱させるものです。[ a ]分岐（または分岐、分岐）は、分岐命令の実行の結果として実行を別の命令シーケンスに切り替える行為を指す場合もあります。分岐命令は、プログラムのループや条件分岐（つまり、特定の条件が満たされた場合にのみ特定の命令シーケンスを実行する）で制御フローを実装するために使用されます。
分岐命令は、常に分岐が発生する無条件分岐と、条件に応じて分岐が発生する場合と発生しない場合がある条件分岐のいずれかです。また、新しい命令シーケンスのアドレス（「ターゲット」アドレス）の指定方法に応じて、分岐命令は一般的に直接、間接、相対のいずれかに分類されます。これは、命令にターゲットアドレスが含まれているか、ターゲットアドレスがどこにあるか（レジスタやメモリ位置など）が指定されているか、または現在のアドレスとターゲットアドレスの差が指定されているかのいずれかを意味します。
分岐命令は、 CPUのプログラムカウンタ（PC）（Intelマイクロプロセッサでは命令ポインタ）の内容を変更できます。プログラムカウンタは、次にフェッチして実行されるマシン命令のメモリアドレスを保持しています。したがって、分岐命令が実行されると、CPUは新しいメモリアドレスからコードを実行し、プログラマが計画したアルゴリズムに従ってプログラムロジックを変更します。
マシンレベルの分岐命令の一種にジャンプ命令があります。ジャンプ命令では、プログラムカウンタ（PC）が通常とは異なる新しい値でロードまたは変更される場合とされない場合があります（現在の命令よりインクリメントされて、次の命令を指すようになります）。ジャンプ命令には通常、無条件ジャンプと条件付きジャンプがあり、条件付きジャンプは条件に応じて実行される場合とされない場合があります（PCが変更される場合とされない場合があります）。
マシンレベルの分岐命令の2つ目のタイプは、サブルーチンを実行するために使用されるコール命令です。ジャンプ命令と同様に、コール命令は条件コードに応じてプログラムカウンタ（PC）を変更する場合と変更しない場合があります。ただし、コール命令では、戻りアドレスがメモリ内の安全な場所（通常はスタックと呼ばれるメモリ常駐データ構造）に保存されます。サブルーチンの実行が完了すると、この戻りアドレスがPCに復元され、コール命令の次の命令からプログラムの実行が再開されます。
マシンレベルの分岐命令の3つ目は、リターン命令です。これはスタックからリターンアドレスをポップしてPCレジスタにロードし、呼び出し元のルーチンに制御を戻します。リターン命令は条件付きで実行される場合もあります。この説明は一般的な運用に関するものですが、マシンプログラマはスタック上のリターンアドレスを操作し、プログラムの実行を様々な方法でリダイレクトする強力な権限を持っています。
プロセッサの種類によっては、ジャンプ命令やコール命令によってPCレジスタの内容が変更される場合があります。絶対アドレスがロードされる場合もあれば、PCの現在の内容に何らかの値（変位）が加算または減算され、宛先アドレスがプログラム内の現在の位置からの相対アドレスとなる場合もあります。変位値のソースは様々で、命令内に埋め込まれた即値、プロセッサレジスタやメモリ位置の内容、あるいはインデックス値に加算された位置の内容などが考えられます。
ブランチという用語は、高水準プログラミング言語のプログラムを指す場合にも使用できます。これらの場合、ブランチは通常、条件が満たされた場合に実行される命令シーケンスをカプセル化するさまざまな形式の条件文の形をとります。GOTO などの無条件ブランチ命令は、無条件に別の命令シーケンスにジャンプするために使用されます。アルゴリズムが条件付きブランチを必要とする場合、GOTO (または GOSUB サブルーチン呼び出し) の前に条件を指定するIF-THENステートメントが続きます。すべての高水準言語は、ループとしてコードを再利用できるアルゴリズムをサポートしています。ループとは、ループが終了する何らかの条件が満たされるまで一連の命令を繰り返す制御構造です。ループもブランチ命令として適格です。マシンレベルでは、ループは、実行を繰り返しコードにリダイレクトする通常の条件付きジャンプとして実装されます。
フラグレジスタを備えたCPUでは、先行する命令によってフラグレジスタに条件が設定されます。先行する命令は算術命令または論理命令の場合があります。多くの場合、分岐命令の近くにある命令ですが、必ずしも分岐命令の直前にあるとは限りません。格納された条件は、オーバーフローフラグが設定されている場合のジャンプなどの分岐命令で使用されます。この一時的な情報は、多くの場合フラグレジスタに格納されますが、他の場所に格納される場合もあります。フラグレジスタの設計は、低速で単純なコンピュータでは簡単です。高速なコンピュータでは、フラグレジスタが速度のボトルネックとなる可能性があります。これは、本来であれば並列に（複数の実行ユニットで）実行できるはずの命令が、特定の順序でフラグビットを設定する必要があるためです。
また、条件がジャンプ命令自体によってチェックされるマシン（または特定の命令）も存在します。例えば、レジスタXが負の場合に<ラベル>を分岐する命令などです。単純なコンピュータ設計では、比較分岐はフラグレジスタ分岐よりも多くの演算を実行し、より多くの電力を消費する可能性があります。高速なコンピュータ設計では、比較分岐はフラグレジスタ分岐よりも高速に実行できます。これは、比較分岐が計算と同じCPUメカニズムを使用して、より並列的にレジスタにアクセスできるためです。
初期のワード指向CPUアーキテクチャ[ b ]の中には、比較結果に応じてNSI、NSI+1、NSI+2（PC+1、PC+2、PC+3）に分岐する条件付き「次の命令をスキップ」操作を実装しているものがある。マイクロコントローラなどで見られるような単純なCPUアーキテクチャの中には、条件付きジャンプを実装せず、スキップ操作と無条件ジャンプ操作のみを実装しているものもある。そのため、条件付きジャンプまたはコールは、無条件ジャンプまたはコール命令の条件付きスキップとして実装される。
コンピュータのアーキテクチャによって異なりますが、ジャンプ命令のアセンブリ言語ニーモニックは通常、 「jump」または「branch」という単語の短縮形であり、多くの場合、条件を表すその他の情報文字（または追加のパラメータ）が付加されます。場合によっては、ジャンプの範囲（オフセットサイズ）や、実際の有効オフセットを特定するために使用すべき特別なアドレッシングモードなど、その他の詳細情報も含まれることがあります。
この表は、いくつかのよく知られたアーキテクチャで使用されているマシンレベルの分岐命令またはジャンプ命令を示しています。
* x86、PDP-11、VAX、およびその他一部のアーキテクチャでは、キャリーフラグを設定して借用を通知し、キャリーフラグをクリアして借用しないことを示します。ARM、6502、PIC、およびその他一部のアーキテクチャでは、減算演算で逆の動作をします。特定の命令におけるキャリーフラグのこの逆の動作は、( * ) で示されます。つまり、表の一部では借用 =キャリーしないことを意味しますが、特に明記されていない限り、借用≡キャリーとなります。ただし、加算演算におけるキャリーは、ほとんどのアーキテクチャで同じように処理されます。
高性能を実現するために、現代のプロセッサはパイプライン処理を採用しています。複数の部分から構成され、各部分は命令を部分的に処理し、その結果をパイプラインの次の段階に渡して、プログラムの次の命令の処理を開始します。この設計では、命令は特定の不変の順序で実行されることを前提としています。条件分岐命令では、この順序を把握することが不可能になります。そのため、条件分岐によって「停止」が発生し、パイプラインをプログラムの別の部分で再開する必要が生じる場合があります。
条件分岐による停止を減らすことで速度を向上させるいくつかの手法がある。
従来、分岐予測は統計情報を取得し、その結果をコードの最適化に利用していました。プログラマーはプログラムのテストバージョンをコンパイルし、テストデータで実行します。テストコードは、実際に分岐がどのように行われたかをカウントします。テストコードから得られた統計情報は、コンパイラによってリリース版コードの分岐を最適化するために使用されました。この最適化により、最も速い分岐方向（分岐が行われたか否かに関わらず）が常に最も頻繁に実行される制御フローパスとなるように調整されます。これを実現するには、CPUは予測可能な分岐タイミングを持つように設計されている必要があります（少なくとも、予測可能な分岐タイミングを備えている必要があります）。一部のCPU（Power ISAなど）は、「分岐ヒント」を備えた命令セットを採用しており、コンパイラが各分岐をどのように実行すべきかをCPUに指示できるようになっています。
ソフトウェアの分岐予測における問題点は、複雑なソフトウェア開発プロセスを必要とすることである。
ソフトウェアを実行するために、ハードウェア分岐予測器は統計情報を電子回路に組み込みました。分岐予測器は、条件分岐の結果を推測するプロセッサの一部です。そして、プロセッサのロジックは、その推測に基づいて、期待される命令フローの実行を開始します。単純なハードウェア分岐予測方式の一例として、後方分岐（つまり、より小さいプログラムカウンタへの分岐）はすべて実行される（ループの一部であるため）、前方分岐（より大きなプログラムカウンタへの分岐）はすべて実行されない（ループから抜け出すため）と仮定することが挙げられます。より優れた分岐予測器は、さまざまなテストプログラムでシミュレーションを実行することによって統計的に開発および検証されます。優れた予測器は通常、分岐の過去の実行結果をカウントします。より高速で高価なコンピュータは、より優れた分岐予測回路に投資することで、より高速に動作することができます。ハードウェア分岐予測を備えたCPUでは、分岐ヒントによって、コンパイラのより優れた分岐予測が、ハードウェアのより単純な分岐予測を上書きすることができます。
分岐なし、または分岐の少ないロジックを記述できる場合もあります。多くの場合、分岐の代わりにビット演算、条件付き移動、またはその他の述語を使用できます。[ 2 ] [ 3 ]実際、タイミング攻撃のため、暗号では分岐のないコードが必須です。[ 4 ]
もう一つの手法は、分岐遅延スロットです。この方式では、MIPSアーキテクチャの分岐可能性/可能性の判定命令など、例外はありますが、分岐命令に続く少なくとも1つの命令が必ず実行されます。そのため、パイプラインが停止するかどうかにかかわらず、コンピュータはこの命令を使って有用な処理を実行できます。この方式は、 RISCコンピュータでは歴史的に広く用いられていました。互換性のあるCPUファミリーでは、マルチサイクルCPU（パイプラインなし）、パイプラインが予想よりも長い高速CPU、および命令を順不同で実行できるスーパースカラCPUでは、この方式が複雑化します。