Compiler-design-code-generation

コンパイラ設計-コード生成

コード生成は、コンパイルの最終段階と見なすことができます。 コード生成後、最適化プロセスをコードに適用できますが、それはコード生成フェーズ自体の一部と見なすことができます。 コンパイラによって生成されるコードは、アセンブリ言語などの下位レベルのプログラミング言語のオブジェクトコードです。 上位レベルの言語で記述されたソースコードが下位レベルの言語に変換され、その結果、下位レベルのオブジェクトコードが生成されることがわかりました。

• ソースコードの正確な意味を伝える必要があります。
• CPU使用率とメモリ管理の点で効率的である必要があります。

ここで、中間コードがターゲットオブジェクトコード（この場合はアセンブリコード）に変換される方法を確認します。

有向非巡回グラフ

有向非巡回グラフ（DAG）は、基本ブロックの構造を表すツールであり、基本ブロック間を流れる値の流れを確認するのに役立ち、最適化も提供します。 DAGは、基本ブロックの簡単な変換を提供します。 DAGはここで理解できます：

• リーフノードは、識別子、名前、または定数を表します。
• 内部ノードは演算子を表します。
• 内部ノードは、式の結果、または値が保存または割り当てられる識別子/名前も表します。

例：

t0 = a + b
t1 = t0 + c
d = t0 + t1

a

有向非巡回グラフ [t〜0〜= a + b] a

有向非巡回グラフ [t〜1〜= t〜0〜+ c] a

のぞき穴の最適化

この最適化手法は、ソースコード上でローカルに機能し、最適化されたコードに変換します。 ローカルでは、手元のコードブロックの小さな部分を意味します。 これらのメソッドは、ターゲットコードだけでなく中間コードにも適用できます。 一連のステートメントが分析され、次の可能な最適化についてチェックされます。

冗長命令除去

ソースコードレベルでは、ユーザーが次の操作を実行できます。

int add_ten(int x) { int y, z; y = 10; z = x + y; return z; }

int add_ten(int x) { int y; y = 10; y = x + y; return y; }

int add_ten(int x) { int y = 10; return x + y; }

int add_ten(int x) { return x + 10; }

コンパイルレベルで、コンパイラは本質的に冗長な命令を検索します。 命令の複数のロードと保存は、それらの一部が削除されても同じ意味を持ちます。 例えば：

• MOV x、R0
• MOV R0、R1

最初の命令を削除して、文を次のように書き直すことができます。

MOV x, R1

到達不能なコード

到達不能コードは、プログラミング構成のためアクセスされないプログラムコードの一部です。 プログラマーは、決して到達できないコードを誤って書いた可能性があります。

例：

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

このコードセグメントでは、 printf ステートメントが実行される前にプログラムコントロールが戻るため、 printf ステートメントは実行されません。したがって、 printf は削除できます。

制御最適化の流れ

重要なタスクを実行せずにプログラムコントロールが前後にジャンプするコードのインスタンスがあります。 これらのジャンプは削除できます。 次のコードチャンクを検討してください。

...
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

このコードでは、コントロールをL2に渡すときにラベルL1を削除できます。 したがって、以下に示すように、L1にジャンプしてからL2にジャンプする代わりに、コントロールは直接L2に到達できます。

...
MOV R1, R2
GOTO L2
...
L2 :   INC R1

代数式の単純化

代数表現を簡単にできる場合があります。 たとえば、式 a = a + 0 は a 自体に置き換えることができ、式a = a + 1は単純にINC aに置き換えることができます。

強度低下

より多くの時間とスペースを消費する操作があります。 それらの「強さ」は、時間とスペースをより少なく消費するが同じ結果をもたらす他の操作に置き換えることで低減できます。

たとえば、 x 2 は、左シフトを1つだけ含む *x << 1 に置き換えることができます。 a * aとa ^ 2 ^の出力は同じですが、a ^ 2 ^を実装する方がはるかに効率的です。

機械命令へのアクセス

ターゲットマシンは、より高度な命令を展開できます。これにより、特定の操作をより効率的に実行できるようになります。 ターゲットコードがこれらの命令に直接対応できる場合、コードの品質が向上するだけでなく、より効率的な結果が得られます。

コードジェネレーター

コードジェネレーターは、ターゲットマシンのランタイム環境とその命令セットを理解している必要があります。 コードジェネレーターは、コードを生成するために次のことを考慮する必要があります。

• ターゲット言語：コードジェネレーターは、コードが変換されるターゲット言語の性質を認識する必要があります。 その言語は、コンパイラがより便利な方法でコードを生成するのを助けるために、いくつかのマシン固有の命令を容易にするかもしれません。 ターゲットマシンは、CISCまたはRISCプロセッサアーキテクチャを使用できます。
• * IRタイプ*：中間表現にはさまざまな形式があります。 抽象構文ツリー（AST）構造、逆ポーランド記法、または3アドレスコードになります。
• 命令の選択：コードジェネレーターは中間表現を入力として受け取り、それをターゲットマシンの命令セットに変換（マッピング）します。 1つの表現は、それを変換する多くの方法（命令）を持つことができるため、適切な命令を賢明に選択するのはコードジェネレーターの責任になります。
• レジスタの割り当て：プログラムには、実行中に維持されるいくつかの値があります。 ターゲットマシンのアーキテクチャでは、すべての値をCPUメモリまたはレジスタに保持できない場合があります。 コードジェネレーターは、レジスタに保持する値を決定します。 また、これらの値を保持するために使用するレジスタを決定します。
• 命令の順序：最後に、コードジェネレーターは命令が実行される順序を決定します。 命令を実行するためのスケジュールを作成します。

ディスクリプタ

コードジェネレーターは、コードの生成中に、レジスター（可用性）とアドレス（値の場所）の両方を追跡する必要があります。 両方について、次の2つの記述子が使用されます。

• レジスタ記述子：レジスタ記述子は、レジスタの可用性についてコード生成プログラムに通知するために使用されます。 レジスタ記述子は、各レジスタに格納されている値を追跡します。 コード生成中に新しいレジスタが必要になるたびに、レジスタの可用性についてこの記述子が参照されます。
• アドレス記述子：プログラムで使用される名前（識別子）の値は、実行中に異なる場所に保存される場合があります。 アドレス記述子は、識別子の値が保存されているメモリの場所を追跡するために使用されます。 これらの場所には、CPUレジスタ、ヒープ、スタック、メモリ、またはこれらの場所の組み合わせが含まれます。

コードジェネレーターは、両方の記述子をリアルタイムで更新し続けます。 ロードステートメント、LD R1、x、コードジェネレーターの場合：

• xの値を持つレジスタ記述子R1を更新し、
• アドレス記述子（x）を更新して、xの1つのインスタンスがR1にあることを示します。

コード生成

基本ブロックは、一連の3アドレス命令で構成されます。 コードジェネレーターは、これらの一連の命令を入力として受け取ります。

注：名前の値が複数の場所（レジスタ、キャッシュ、またはメモリ）で見つかった場合、キャッシュとメインメモリよりもレジスタの値が優先されます。 同様に、キャッシュの値はメインメモリよりも優先されます。 メインメモリにはほとんど設定がありません。

*getReg* ：コードジェネレーターは_getReg_関数を使用して、使用可能なレジスターの状態と名前の値の場所を判別します。 _getReg_は次のように機能します。

• 変数Yが既にレジスターRにある場合、そのレジスターを使用します。
• それ以外の場合、レジスタRが使用可能であれば、そのレジスタを使用します。
• それ以外の場合、上記の両方のオプションが使用できない場合、最小限の数のロードおよびストア命令を必要とするレジスタを選択します。

命令x = y OP zの場合、コードジェネレーターは次のアクションを実行できます。 Lはy OP zの出力が保存される場所（できればレジスタ）であると仮定します。

• 関数getRegを呼び出して、Lの位置を決定します。
• y のアドレス記述子を調べて、 y の現在の位置（レジスタまたはメモリ）を決定します。 y が現在レジスタ L にない場合、次の命令を生成して y の値を L にコピーします。 + MOV y ’、L +ここで、 y’ は y のコピーされた値を表します。
• y の手順2で使用したのと同じ方法を使用して z の現在の場所を特定し、次の命令を生成します。 + OP z ’、L +ここで、 z’ は z のコピーされた値を表します。
• ここで、Lにはy OP zの値が含まれ、これは x に割り当てることを目的としています。 したがって、Lがレジスターである場合、その記述子を更新して、 x の値が含まれていることを示します。 x の記述子を更新して、位置 L に格納されていることを示します。
• yとzがそれ以上使用されない場合、それらをシステムに戻すことができます。

ループや条件ステートメントなどの他のコード構成は、一般的なアセンブリ方法でアセンブリ言語に変換されます。