2

このCコードを考えてみましょう。

int sum=0;
for(int i=0;i<5;i++)
    sum+=i;

これは、（疑似）アセンブリで次のように変換できます（ループ展開なし）。

% pseudo-code assembly
ADDI $R10, #0   % sum
ADDI $R11, #0   % i
LOOP:
ADD $R10, $R11
ADDI $R11, #1
BNE $R11, #5 LOOP

したがって、私の最初の質問は、これら2つの方法の間で、ループ展開を使用してこのコードをどのように変換するかです。

1）

ADDI $R10, #0
ADDI $R10, #0
ADDI $R10, #1
ADDI $R10, #2
ADDI $R10, #3
ADDI $R10, #4

2）

   ADD $R10, #10

コンパイラーはコードを最適化し、すべての合計を実行せずに10を追加する必要があることを直接知ることができますか？

また、分岐命令でパイプラインをブロックする可能性はありますか？私はそれをこのように書く必要がありますか？

% pseudo-code assembly
ADDI $R10, #0   % sum
ADDI $R11, #0   % i
LOOP:
ADD $R10, $R11
ADDI $R11, #1
NOP   % is this necessary to avoid the pipeline blocking?
NOP
NOP
NOP
BNE $R11, #5 LOOP

fetch-decode-exe-mem-write backサイクルがブランチによって中断されないようにするには？

4

4 に答える 4

10

これは、すべてのコンパイラが実行することではなく、コンパイラが実行できることを示すためのものです。起源：

#include <stdio.h>

int main(void)
{
    int i, sum = 0;

    for(i=0; i<5; i++) {
        sum+=i;
    }

    printf("%d\n", sum);
    return 0;
}

printf私が追加したことに注意してください。変数が使用されていない場合、コンパイラーはループ全体を最適化します。

-O0を使用したコンパイル（最適化なし）

gcc -Wall -O0 -S -c lala.c：

.L3:
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
.L2:
    cmpl    $4, -8(%rbp)
    jle .L3

-8(%rbp)ループは、変数である「ダム」の方法で発生しますi。

-O1を使用したコンパイル（最適化レベル1）

gcc -Wall -O1 -S -c lala.c：

movl    $10, %edx

ループは完全に削除され、同等の値に置き換えられました。

展開時に、コンパイラーは何回の反復が発生するかを確認し、実行する反復回数を減らして展開を試みます。たとえば、ループ本体が2回複製されると、ブランチの数が半分になります。Cのそのような場合：

int i = 0, sum = 0;

sum += i;
i++;

for(; i<5;i++) {
    sum+=i;
    i++;
    sum+=i;
}

ループから1回の反復を抽出する必要があることに注意してください。これは、5が奇数であるため、内容を複製するだけでは作業を半分にすることができないためです。この場合、ループは2回だけ入ります。によって生成されたアセンブリコード-O0：

    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    jmp .L2
.L3:
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
.L2:
    cmpl    $4, -8(%rbp)

Cで完全に展開：

for(i=0; i<5;i++) {
    sum+=i;
    i++;
    sum+=i;
    i++;
    sum+=i;
    i++;
    sum+=i;
    i++;
    sum+=i;
}

今回は、ループは実際には1回だけ入ります。で作成されたアセンブリ-O0：

.L3:
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
.L2:
    cmpl    $4, -8(%rbp)
    jle .L3
于 2012-04-24T16:06:03.703 に答える
2

基本的なレベルでは、ループ展開の概念は、ループの本体を必要に応じて複数回コピーするだけです。コンパイラーは他の最適化（計算からの固定値の挿入など）も実行できますが、ループを展開することとは見なされませんが、ループをすべて一緒に置き換える可能性があります。しかし、それは最終的には使用されるコンパイラとフラグに依存します。

Cコード（展開のみ）は次のようになります。

int sum = 0;
int i = 0;
for ( ; i < (5 & ~(4-1)); i += 4) /* unrolling 4 iterations */
{
    sum+=(i+0);
    sum+=(i+1);
    sum+=(i+2);
    sum+=(i+3);
}
for ( ; i < 5; i++)
{
    sum+=i;
}

ここでは、コンパイラーがさらに多くの最適化を行う機会がたくさんありますが、これは1つのステップにすぎません。

于 2012-04-24T16:06:32.550 に答える
2

したがって、私の最初の質問は、これら2つの方法の間で、ループ展開を使用してこのコードをどのように変換するかです。

この種の最適化は通常、出力コード（アセンブリなど）レベルではなく、ASTレベルで実装されます。ループの展開は、反復回数が固定され、コンパイル時にわかっている場合に実行できます。たとえば、私はこのASTを持っています：

Program
|
+--For
   |
   +--Var
   |  |
   |  +--Variable i
   |
   +--Start
   |  |
   |  +--Constant 1
   |
   +--End
   |  |
   |  +--Constant 3
   |
   +--Statements
      |
      + Print i

コンパイラーは、ForのStartとEndが定数であることを認識しているため、ステートメントを簡単にコピーして、Varのすべての出現箇所を各呼び出しの値に置き換えることができます。上記のASTの場合、次のように変換されます。

Program
|
+--Print 1
|
+--Print 2
|
+--Print 3

コンパイラーはコードを最適化し、すべての合計を実行せずに10を追加する必要があることを直接知ることができますか？

はい、そのような機能を持つように実装されている場合は可能です。これは、実際には上記の場合よりも改善されています。あなたの例の場合、展開を行った後、コンパイラは、r値が定数である間、すべてのl値が同じままであることを確認できます。したがって、定数畳み込みと組み合わせたのぞき穴最適化を実行して、単一の追加を生成できます。のぞき穴の最適化で宣言も考慮される場合は、単一の移動命令にさらに最適化することができます。

于 2012-04-24T16:10:54.193 に答える
0

これについて可能な一般的な答えはありません、異なるコンパイラ、それらの異なるバージョン、異なるコンパイラフラグは異なります。コンパイラの適切なオプションを使用して、アセンブラの結果を確認します。gccと親戚の場合、これは-Sオプションです。

于 2012-04-24T15:55:57.367 に答える