Loading article…
コンパイラ構築において、基本ブロックとは、エントリ以外には分岐がなく、エグジット以外には分岐がない直線的なコードシーケンスである。[ 1 ] [ 2 ]この制限された形式により、基本ブロックは分析に非常に適している。[ 3 ]コンパイラは通常、分析プロセスの最初のステップとしてプログラムを基本ブロックに分解する。基本ブロックは、制御フローグラフの頂点またはノードを形成する。
基本ブロック内のコードは以下のとおりです。
このような状況下では、基本ブロック内の最初の命令が実行されると、残りの命令は必ず一度だけ順番に実行されます。[ 4 ] [ 5 ]
コードは、ソースコード、アセンブリコード、またはその他の命令のシーケンスである可能性があります。
より厳密に言えば、命令のシーケンスは、以下の条件を満たす場合に基本ブロックを形成する。
この定義は、直感的な定義よりもいくつかの点でより一般的です。例えば、他のジャンプのターゲットとなっていないラベルへの無条件ジャンプを可能にします。この定義は、アルゴリズムを構築する際に基本ブロックを扱いやすくする特性を体現しています。
ブロックの末尾に到達した後に制御が移る可能性のあるブロックは、そのブロックの後継ブロックと呼ばれ、ブロックに入る際に制御が移ってきた可能性のあるブロックは、そのブロックの前任ブロックと呼ばれます。基本ブロックの開始位置は、複数の場所からジャンプできます。
コードリストから基本ブロックを生成するアルゴリズムは単純です。アナライザはコードをスキャンし、ブロック境界をマークします。ブロック境界とは、制御を別の箇所に渡したり、別の箇所から制御を受け入れたりすることで、ブロックの開始または終了となる命令のことです。次に、リストはこれらの境界で単純に「切り取られ」、基本ブロックが残ります。
この方法は、形式的な定義によれば必ずしも最大基本ブロックを生成するわけではありませんが、通常は十分です（最大基本ブロックとは、基本ブロックの定義に違反することなく隣接ブロックを含めることによって拡張できない基本ブロックです[ 6 ]）。
入力：命令のシーケンス（主に3アドレスコード）。[ 7 ]出力：各3アドレス命令がちょうど1つのブロックに含まれる基本ブロックのリスト。
基本ブロックを終了する命令には、次のものが含まれます。
longjmpのような特別な呼び出しなど、戻り値を返すことができない場合は、基本ブロックの最後に配置できますexit。新しい基本ブロックを開始する命令には、以下のものが含まれます。
基本ブロックの末尾を制御が通過することはないという点に注意してください。そのため、基本ブロックを見つけるには、一部の命令を修正する必要がある場合があります。特に、条件分岐を双方向分岐に変更し、例外をスローする関数呼び出しの後には無条件ジャンプを追加する必要があります。これらの変更を行うには、他のブロックの先頭にラベルを追加する必要があるかもしれません。