Compiler-design-code-optimization

コンパイラの設計-コードの最適化

最適化はプログラム変換手法であり、コードの改善によりリソースの消費を抑えようとします（つまり、 CPU、メモリ）と高速を実現します。

最適化では、高レベルの一般的なプログラミング構造が、非常に効率的な低レベルのプログラミングコードに置き換えられます。 コード最適化プロセスは、次の3つの規則に従う必要があります。

• 出力コードによって、プログラムの意味が変わることはありません。
• 最適化によりプログラムの速度が向上し、可能であれば、プログラムが必要とするリソースの数が少なくなります。
• 最適化自体は高速であり、コンパイルプロセス全体を遅らせるべきではありません。

プロセスをコンパイルするさまざまなレベルで、最適化されたコードへの取り組みを行うことができます。

• 最初は、ユーザーはコードを変更/再配置したり、より良いアルゴリズムを使用してコードを記述したりできます。
• 中間コードを生成した後、コンパイラはアドレス計算とループの改善により中間コードを変更できます。
• ターゲットマシンコードの生成中に、コンパイラはメモリ階層とCPUレジスタを使用できます。

最適化は、マシンに依存しないタイプとマシンに依存するタイプの2つに大きく分類できます。

マシンに依存しない最適化

この最適化では、コンパイラーは中間コードを取り込み、CPUレジスターや絶対メモリー位置を含まないコードの一部を変換します。 例えば：

do
{
   item = 10;
   value = value + item;
} while(value<100);

このコードには、識別子アイテムの繰り返し割り当てが含まれます。

Item = 10;
do
{
   value = value + item;
} while(value<100);

CPUサイクルを節約するだけでなく、どのプロセッサでも使用できます。

マシン依存の最適化

マシン依存の最適化は、ターゲットコードが生成された後、ターゲットマシンアーキテクチャに従ってコードが変換されるときに行われます。 これにはCPUレジスタが含まれ、相対参照ではなく絶対メモリ参照が含まれる場合があります。 マシン依存のオプティマイザーは、メモリ階層を最大限に活用する努力をします。

基本ブロック

通常、ソースコードには多数の命令があり、それらは常に順番に実行され、コードの基本ブロックと見なされます。 これらの基本ブロックにはジャンプステートメントがありません。つまり、最初の命令が実行されると、同じ基本ブロック内のすべての命令が、プログラムのフロー制御を失うことなく、出現順に実行されます。

プログラムは、IF-THEN-ELSE、SWITCH-CASE条件ステートメント、DO-WHILE、FOR、およびREPEAT-UNTILなどのループなど、基本ブロックとしてさまざまな構造を持つことができます。

基本ブロック識別

次のアルゴリズムを使用して、プログラムの基本ブロックを見つけることができます。

• 基本ブロックが始まるすべての基本ブロックのヘッダーステートメントを検索します。
• プログラムの最初のステートメント。
• ブランチのターゲットであるステートメント（条件付き/無条件）。
• 分岐ステートメントに続くステートメント。
• ヘッダーステートメントとそれに続くステートメントは、基本ブロックを形成します。
• 基本ブロックには、他の基本ブロックのヘッダーステートメントは含まれません。

基本ブロックは、コード生成と最適化の両方の観点から重要な概念です。

基本ブロック

基本ブロックは、単一の基本ブロックで複数回使用されている変数を識別するのに重要な役割を果たします。 変数が複数回使用されている場合、ブロックが実行を終了しない限り、その変数に割り当てられたレジスタメモリを空にする必要はありません。

制御フローグラフ

プログラムの基本ブロックは、制御フローグラフを使用して表すことができます。 制御フローグラフは、プログラム制御がブロック間でどのように渡されるかを示します。 これは、プログラム内の不要なループを見つけるのに役立つことにより、最適化に役立つ便利なツールです。

制御フローグラフ

ループ最適化

ほとんどのプログラムは、システム内でループとして実行されます。 CPUサイクルとメモリを節約するために、ループを最適化することが必要になります。 ループは、次の手法で最適化できます。

• 不変コード：ループ内に存在し、各反復で同じ値を計算するコードのフラグメントは、ループ不変コードと呼ばれます。 このコードは、反復ごとにではなく、一度だけ計算されるように保存することで、ループの外に移動できます。
• 誘導分析：ループ不変値によってループ内で値が変更される場合、変数は誘導変数と呼ばれます。
• 強度の削減：より多くのCPUサイクル、時間、およびメモリを消費する式があります。 これらの式は、式の出力を損なうことなく、より安価な式に置き換える必要があります。 たとえば、乗算（x * 2）は（x << 1）よりもCPUサイクルの点で高価であり、同じ結果をもたらします。

デッドコード除去

デッドコードは、次の1つまたは複数のコードステートメントです。

• 実行されていないか到達不能であるか、 *または、実行された場合、それらの出力は使用されません。

したがって、デッドコードは、プログラムの操作には何の役割も果たさないため、単純に排除できます。

部分的にデッドコード

計算された値が特定の状況でのみ使用されるコードステートメントがいくつかあります。つまり、値が使用される場合と使用されない場合があります。 このようなコードは、部分デッドコードとして知られています。

部分的にデッドコード

上記の制御フローグラフは、変数「a」を使用して式「x* y」の出力を割り当てるプログラムのチャンクを示しています。 「a」に割り当てられた値がループ内で使用されることはないと仮定しましょう。コントロールがループを抜けた直後に、「a」には変数「z」の値が割り当てられます。これはプログラムで後で使用されます。 ここでは、「a」の割り当てコードはどこでも使用されないため、削除する資格があると結論付けています。

デッドコード

同様に、上の図は、条件ステートメントが常にfalseであることを示しています。これは、trueケースで記述されたコードが実行されないため、削除できることを意味します。

部分的な冗長性

冗長式は、オペランドを変更せずに、並列パスで複数回計算されます。一方、部分冗長式は、オペランドを変更せずに、パスで複数回計算されます。 例えば、

a	冗長表現 {空} [冗長表現] a

ループ不変コードは部分的に冗長であり、コードモーション手法を使用して排除できます。

部分的に冗長なコードの別の例は次のとおりです。

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

オペランド（ y および z ）の値は、変数 a から変数 c への割り当てから変更されないと仮定します。 ここで、条件ステートメントが真の場合、y OP zは2回計算され、そうでない場合は1回計算されます。 以下に示すように、コードモーションを使用してこの冗長性を排除できます。

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

ここで、条件が真か偽か。 y OP zは一度だけ計算する必要があります。