|
基本ブロック基本ブロック（きほんブロック、英: Basic block）は、コンピュータにおいて、一つの入り口（すなわち、内部のコードが他のコードの分岐先になっていない)と一つの出口を持ち、内部に分岐を含まないコードを指す。基本ブロックの開始点には、他のコードからジャンプすることができる。基本ブロックの終了点は、他のコードへのジャンプ命令（あるいは、ジャンプの一つ前の命令）である。 基本ブロックは通例コンパイラ最適化を行う最小単位であり、制御フローグラフにおけるノードや頂点である。 基本ブロックにおけるコードとは、ソースコードでもアセンブリ言語でも、またその他の命令列であっても良い。 定義正式な定義では、各位置におけるコードがグラフ理論上支配するか、あるいはその命令より後に置かれたコードより先に実行され、命令列の二つの命令の間には別の命令が実行されることがない場合、命令列は基本ブロックを形成する。この定義は慣れ親しんだものとは異なり、たとえば他のジャンプから参照されないラベルへの無条件のジャンプが許容される。この定義ではアルゴリズムを構築する際にも基本ブロックの考え方を用いることができる。 あるブロックの終端に到達した後、次に制御を移すブロックは「後任者(successor)」と呼ばれ、制御を渡してきたブロックは「前任者(predecessor)」と呼ばれる。 生成アルゴリズムコードのリストから基本ブロックを生成するアルゴリズムは単純である。コードをスキャンし、ブロックの開始や終端となる命令すなわち「ブロックの境界」をマークする。マークした境界ごとにリストを切り分ければ、基本ブロックができる。この方法は、公式な定義では「最長」の制御ブロックを生成するとは限らないが、通常十分（最長の基本ブロックとは、隣接の基本ブロックを、定義を侵すことなく取り込むことができないものを指す[1]）である。 基本ブロックを終了させる命令には以下のものがある:
基本ブロックを開始させる命令には以下のものがある:
制御が基本ブロックの最後を通過することはないため、ブロックの境界は、基本ブロックを見つけた後に修正しなければならない場合もある。特に、分岐しなかった場合のコードは二方向の分岐に変換し、例外を発生させる関数呼び出しには無条件分岐を付き足なければならない。このため他のブロックの先頭にラベルをつける必要が生じる場合もある。 関連項目参考文献
外部リンク |