Loading article…
コンパイラの構築において、基本ブロックは、入口以外に分岐がなく、出口以外に分岐がない直線的なコードシーケンスです。[1] [2]この制限された形式により、基本ブロックは分析に非常に適しています。[3] コンパイラは通常、分析プロセスの最初のステップとしてプログラムを基本ブロックに分解します。基本ブロックは、制御フローグラフの頂点またはノードを形成します。
意味
基本ブロック内のコードは次のとおりです。
- エントリ ポイントは1 つであり、その中のコードはプログラム内のどこにもジャンプ命令の宛先ではありません。
- 1 つの終了ポイント。つまり、最後の命令のみがプログラムに別の基本ブロック内のコードの実行を開始させることができます。
このような状況では、基本ブロックの最初の命令が実行されるたびに、残りの命令は必ず1回だけ順番に実行されます。[4] [5]
コードは、ソース コード、アセンブリ コード、またはその他の命令シーケンスである場合があります。
より正式には、命令のシーケンスが基本ブロックを形成するのは、次の場合です。
- 各位置の命令は、後の位置にあるすべての命令よりも優先されます（常に先に実行されます）。
- シーケンス内の 2 つの命令の間には他の命令は実行されません。
この定義は、いくつかの点で直感的な定義よりも一般的です。たとえば、他のジャンプの対象ではないラベルへの無条件ジャンプを許可します。この定義は、アルゴリズムを構築するときに基本ブロックを簡単に操作できるようにするプロパティを具体化します。
ブロックの終わりに達した後に制御が移る可能性のあるブロックは、そのブロックの後続ブロックと呼ばれます。一方、ブロックに入るときに制御が移った可能性のあるブロックは、そのブロックの前続ブロックと呼ばれます。基本ブロックの先頭には、複数の場所からジャンプできます。
作成アルゴリズム
コードのリストから基本ブロックを生成するアルゴリズムは単純です。アナライザーはコードをスキャンして、ブロック境界をマークします。ブロック境界は、制御を転送するか、別のポイントから制御を受け入れるかのいずれかであるため、ブロックの開始または終了となる命令です。次に、リストはこれらの各ポイントで単純に「カット」され、基本ブロックが残ります。
この方法は、正式な定義によれば常に最大基本ブロックを生成するわけではないが、通常は十分である（最大基本ブロックとは、基本ブロックの定義に違反することなく隣接するブロックを含めることによって拡張することができない基本ブロックである[6]）。
入力: 命令のシーケンス（主に3アドレスコード）。[7]
出力: 3アドレス命令が1つのブロックにまとめられた基本ブロックのリスト。
- コード内のリーダーを特定します。リーダーとは、次の 3 つのカテゴリのいずれかに該当する指示です。
- それは最初の指示です。最初の指示はリーダーです。
- 条件付きまたは無条件の goto/jump 命令のターゲットはリーダーです。
- 条件付きまたは無条件の goto/jump 命令の直後に続く命令はリーダーです。
- リーダーから始まり、次のリーダーまで続くすべての命令のセット（次のリーダーは含まない）が、開始リーダーに対応する基本ブロックです。したがって、すべての基本ブロックにはリーダーが存在します。
基本ブロックを終了する命令には次のものがあります。
- 無条件分岐と条件分岐（直接的および間接的）。
- 呼び出し手順に戻ります。
- 例外をスローする可能性のある命令。
- 例外をスローする関数やCや
longjmpのような特殊な呼び出しなど、関数呼び出しが戻ることができない場合は、関数呼び出しを基本ブロックの最後に配置できますexit。
新しい基本ブロックを開始する命令には次のものがあります。
- プロシージャと関数のエントリ ポイント。
- ジャンプや分岐のターゲット。
- いくつかの条件分岐に続く「フォールスルー」命令。
- 例外をスローする命令に続く命令。
- 例外ハンドラ。
制御は基本ブロックの末尾を通過することはできないため、基本ブロックを見つけるために一部の命令を変更する必要があることに注意してください。特に、フォールスルー条件分岐は双方向分岐に変更する必要があり、例外をスローする関数呼び出しの後に無条件ジャンプを追加する必要があります。これを行うには、他のブロックの先頭にラベルを追加する必要がある場合があります。
参照
参考文献
- ^ ヘネシー、ジョン L.、デビッド A. パターソン。コンピュータアーキテクチャ：定量的アプローチ。エルゼビア、2011 年。
- ^ クーパー、キース・ダニエル、トルゾン、リンダ（2012年）。コンパイラのエンジニアリング（第2版）。アムステルダム：エルゼビア/モルガン・カウフマン。p. 231。ISBN 978-0120884780. OCLC 714113472.
- ^ 「制御フロー分析」、Frances E. Allen著。
- ^ Yousefi, Javad (2015). 「データ冗長性を利用した誤った後続制御フローエラーのマスキング」2015 第 5 回国際コンピュータおよび知識工学会議 (ICCKE) IEEE. pp. 201–205. doi :10.1109/ICCKE.2015.7365827. ISBN 978-1-4673-9280-8。
- ^ 「グローバル共通部分式の除去」、John Cocke 著。
- ^ 最新のコンパイラー設計、Dick Grune、Henri E. Bal、Ceriel JH Jacobs、Koen G. Langendoen 著、p. 320。
- ^ コンパイラの原理、テクニック、ツール、Aho Sethi Ullman。
外部リンク
- 基本ブロック - GNU コンパイラ コレクション
- 拡張基本ブロック - ウィクショナリー