186

最適化された関数を書いているときに、ftolで非常に奇妙な動作を見つけましたGCC 4.6.1。最初にコードをお見せしましょう (わかりやすくするために違いをマークしました):

fast_trunc_one、C:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;                       /* diff */
    } else {
        r = mantissa >> exponent;                        /* diff */
    }

    return (r ^ -sign) + sign;                           /* diff */
}

fast_trunc_two、C:

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent) ^ -sign;             /* diff */
    } else {
        r = (mantissa >> exponent) ^ -sign;              /* diff */
    }

    return r + sign;                                     /* diff */
}

同じですよね？まあGCCは同意しません。これでコンパイルした後gcc -O3 -S -Wall -o test.s test.cのアセンブリ出力は次のとおりです。

生成された fast_trunc_one:

_fast_trunc_one:
LFB0:
    .cfi_startproc
    movl    4(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %edx
    andl    $8388607, %edx
    sarl    $23, %eax
    orl $8388608, %edx
    andl    $255, %eax
    subl    %eax, %ecx
    movl    %edx, %eax
    sarl    %cl, %eax
    testl   %ecx, %ecx
    js  L5
    rep
    ret
    .p2align 4,,7
L5:
    negl    %ecx
    movl    %edx, %eax
    sall    %cl, %eax
    ret
    .cfi_endproc

fast_trunc_two、生成:

_fast_trunc_two:
LFB1:
    .cfi_startproc
    pushl   %ebx
    .cfi_def_cfa_offset 8
    .cfi_offset 3, -8
    movl    8(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %ebx
    movl    %eax, %edx
    sarl    $23, %ebx
    andl    $8388607, %edx
    andl    $255, %ebx
    orl $8388608, %edx
    andl    $-2147483648, %eax
    subl    %ebx, %ecx
    js  L9
    sarl    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_remember_state
    .cfi_def_cfa_offset 4
    .cfi_restore 3
    ret
    .p2align 4,,7
L9:
    .cfi_restore_state
    negl    %ecx
    sall    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_restore 3
    .cfi_def_cfa_offset 4
    ret
    .cfi_endproc

それは極端な違いです。これは実際にプロファイルにも表示され、fast_trunc_oneよりも約 30% 高速ですfast_trunc_two。今私の質問：何が原因ですか？

4

3 に答える 3

261

OPの編集と同期するように更新

コードをいじることで、GCC が最初のケースを最適化する方法を確認できました。

なぜそんなに違うのかを理解する前に、まず GCC がどのように最適化するかを理解する必要がありますfast_trunc_one()。

信じられないかもしれませんfast_trunc_one()が、次のように最適化されています。

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

これにより、元のアセンブリとまったく同じアセンブリが生成fast_trunc_one()されます-名前とすべてを登録します。

xorのアセンブリにがないことに注意してくださいfast_trunc_one()。それが私にそれを与えたものです。

どうして？

ステップ1： sign = -sign

signまず、変数を見てみましょう。以来、取ることができるsign = i & 0x80000000;可能な値は 2 つだけです。sign

  • sign = 0
  • sign = 0x80000000

どちらの場合も、sign == -sign. したがって、元のコードを次のように変更すると:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;
    } else {
        r = mantissa >> exponent;
    }

    return (r ^ sign) + sign;
}

元の とまったく同じアセンブリが生成されfast_trunc_one()ます。アセンブリは割愛しますが、それは同じです-名前とすべてを登録します。

ステップ 2:数学的還元:x + (y ^ x) = y

signは 2 つの値0またはのいずれかのみを取ることができます0x80000000。

  • の場合x = 0、x + (y ^ x) = y自明なことが成り立ちます。
  • 加算と xor0x80000000は同じです。符号ビットを反転します。したがって、 のx + (y ^ x) = y場合も成り立ちますx = 0x80000000。

したがって、 にx + (y ^ x)減少しyます。コードは次のように簡略化されます。

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent);
    } else {
        r = (mantissa >> exponent);
    }

    return r;
}

繰り返しますが、これはまったく同じアセンブリにコンパイルされます-名前とすべてを登録します。

この上記のバージョンは、最終的に次のようになります。

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

これは、GCC がアセンブリで生成するものとほとんど同じです。

では、なぜコンパイラfast_trunc_two()は同じものに最適化しないのでしょうか?

の重要な部分fast_trunc_one()はx + (y ^ x) = y最適化です。式ではfast_trunc_two()、x + (y ^ x)ブランチ全体に分割されています。

GCCを混乱させてこの最適化を行わないようにするのに十分かもしれないと思います。(^ -signブランチから を持ち上げて、最後に にマージする必要がありr + signます。)

たとえば、次のように同じアセンブリが生成されfast_trunc_one()ます。

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = ((mantissa << -exponent) ^ -sign) + sign;             /* diff */
    } else {
        r = ((mantissa >> exponent) ^ -sign) + sign;              /* diff */
    }

    return r;                                     /* diff */
}
于 2012-04-20T17:52:51.157 に答える
64

これがコンパイラの性質です。彼らが最速または最良の道をたどると仮定することは、まったく間違っています。「最新のコンパイラ」が空白を埋め、最高の仕事をし、最速のコードを作成するなどの理由で、コードを最適化するために何もする必要がないことを意味する人. 実際、私は gcc が 3.x から少なくとも腕の 4.x。この時点で 4.x は 3.x に追いついたかもしれませんが、早い段階でより遅いコードが生成されました。練習を積むことで、コードの書き方を学ぶことができるので、コンパイラーはそれほど苦労する必要がなくなり、その結果、より一貫性のある期待される結果が得られます。

ここでのバグは、実際に生成されたものではなく、生成されるものに対する期待です。コンパイラに同じ出力を生成させたい場合は、同じ入力を与えます。数学的には同じではありませんが、実際には同じであり、異なるパスはなく、あるバージョンから別のバージョンへの操作の共有や配布はありません。これは、コードの書き方を理解し、コンパイラがそれをどのように処理するかを理解するための良い練習になります。ある日、1 つのプロセッサ ターゲットに対して 1 つのバージョンの gcc が特定の結果を生成したため、それがすべてのコンパイラとすべてのコードのルールであると仮定するのを間違えないでください。何が起こっているのかを把握するには、多くのコンパイラと多くのターゲットを使用する必要があります。

gcc はかなり厄介です。カーテンの裏側を見て、gcc の内臓を見て、ターゲットを追加したり、自分で何かを変更したりしてみてください。ダクトテープとベイリングワイヤーでかろうじてまとめられています。重要な場所で余分なコード行が追加または削除され、それが崩壊します。他の期待に応えられなかった理由を心配するのではなく、使用可能なコードがまったく生成されたという事実は喜ばしいことです。

gcc が生成するさまざまなバージョンを見ましたか? 3.x と 4.x 特に 4.5 対 4.6 対 4.7 など? 異なるターゲット プロセッサ、x86、arm、mips など、または使用するネイティブ コンパイラが 32 ビットか 64 ビットかなどの x86 の異なるフレーバーについては? そして、異なるターゲットのllvm（clang）？

Mystical は、コードの分析/最適化の問題を解決するために必要な思考プロセスにおいて優れた仕事をしてきました。コンパイラがそのいずれかを考え出すことを期待していますが、それは「最新のコンパイラ」には期待されていません。

数学のプロパティに入ることなく、この形式のコード

if (exponent < 0) {
  r = mantissa << -exponent;                       /* diff */
} else {
  r = mantissa >> exponent;                        /* diff */
}
return (r ^ -sign) + sign;                           /* diff */

コンパイラを A に導きます。その形式で実装し、if-then-else を実行してから共通コードに収束して終了し、戻ります。または B: これは関数の末尾であるため、ブランチを保存します。また、r の使用や保存を気にしないでください。

if (exponent < 0) {
  return((mantissa << -exponent)^-sign)+sign;
} else {
  return((mantissa << -exponent)^-sign)+sign;
}

次に、Mystical が指摘したように、記述されているコードの符号変数がすべて一緒に消えます。コンパイラが符号変数が消えるのを見るとは思わないので、コンパイラにそれを理解しようと強制するのではなく、自分でそれを行うべきでした。

これは、gcc のソース コードを掘り下げる絶好の機会です。オプティマイザーがあるケースで 1 つのことを認識し、別のケースで別のことを認識したケースを見つけたようです。次に、次のステップに進み、gcc でそのケースを確認できないかどうかを確認します。すべての最適化は、一部の個人またはグループが最適化を認識し、意図的にそこに置いたために存在します。この最適化がそこにあり、誰かがそこに置く必要があるたびに機能するために (そして、それをテストし、将来に向けて維持する必要があります)。

コードが少ないほど速く、コードが多いほど遅いとは絶対に思い込まないでください。そうでない例を作成して見つけるのは非常に簡単です。多くの場合、コードが少ないほどコードが多い場合よりも高速になる場合があります。最初から示したように、その場合の分岐やループなどを保存するコードをさらに作成し、最終的により高速なコードにすることができます。

肝心なのは、コンパイラに異なるソースを供給し、同じ結果を期待していたことです。問題はコンパイラの出力ではなく、ユーザーの期待です。特定のコンパイラとプロセッサについて、関数全体を劇的に遅くする 1 行のコードを追加することを実証するのはかなり簡単です。たとえば、なぜ a = b + 2; を変更するのですか? a = b + c + 2; 原因 _fill_in_the_blank_compiler_name_ は根本的に異なる、より遅いコードを生成しますか? もちろん、答えはコンパイラーが入力時に異なるコードを供給されたため、コンパイラーが異なる出力を生成することは完全に有効です。(さらに良いのは、無関係な 2 行のコードを入れ替えて、出力を劇的に変化させる場合です) 入力の複雑さとサイズと出力の複雑さとサイズの間には、予想される関係はありません。

for(ra=0;ra<20;ra++) dummy(ra);

60 ～ 100 行のアセンブラーが作成されました。ループを展開しました。私は行を数えませんでした。考えてみれば、追加し、結果を関数呼び出しの入力にコピーし、関数呼び出しを行い、最低 3 つの操作が必要です。したがって、ターゲットによっては、少なくとも 60 命令、ループごとに 4 つの場合は 80、ループごとに 5 つの場合は 100 などです。

于 2012-04-20T20:48:14.467 に答える
23

Mysticial はすでに素晴らしい説明を提供していますが、FWIW として、コンパイラが一方を最適化して他方を最適化しない理由について、基本的なことは何もないことを追加したいと思いました。

たとえば、 LLVM のclangコンパイラは、(関数名を除いて) 両方の関数に対して同じコードを提供し、次のようにします。

_fast_trunc_two:                        ## @fast_trunc_one
        movl    %edi, %edx
        andl    $-2147483648, %edx      ## imm = 0xFFFFFFFF80000000
        movl    %edi, %esi
        andl    $8388607, %esi          ## imm = 0x7FFFFF
        orl     $8388608, %esi          ## imm = 0x800000
        shrl    $23, %edi
        movzbl  %dil, %eax
        movl    $150, %ecx
        subl    %eax, %ecx
        js      LBB0_1
        shrl    %cl, %esi
        jmp     LBB0_3
LBB0_1:                                 ## %if.then
        negl    %ecx
        shll    %cl, %esi
LBB0_3:                                 ## %if.end
        movl    %edx, %eax
        negl    %eax
        xorl    %esi, %eax
        addl    %edx, %eax
        ret

このコードは、OP の最初の gcc バージョンほど短くはありませんが、2 番目ほど長くはありません。

x86_64 用にコンパイルする別のコンパイラ (名前は付けません) からのコードは、両方の関数に対してこれを生成します。

fast_trunc_one:
        movl      %edi, %ecx        
        shrl      $23, %ecx         
        movl      %edi, %eax        
        movzbl    %cl, %edx         
        andl      $8388607, %eax    
        negl      %edx              
        orl       $8388608, %eax    
        addl      $150, %edx        
        movl      %eax, %esi        
        movl      %edx, %ecx        
        andl      $-2147483648, %edi
        negl      %ecx              
        movl      %edi, %r8d        
        shll      %cl, %esi         
        negl      %r8d              
        movl      %edx, %ecx        
        shrl      %cl, %eax         
        testl     %edx, %edx        
        cmovl     %esi, %eax        
        xorl      %r8d, %eax        
        addl      %edi, %eax        
        ret

これは、 の両辺を計算ifし、最後に条件付き移動を使用して正しい方を選択するという点で魅力的です。

Open64 コンパイラは以下を生成します。

fast_trunc_one: 
    movl %edi,%r9d                  
    sarl $23,%r9d                   
    movzbl %r9b,%r9d                
    addl $-150,%r9d                 
    movl %edi,%eax                  
    movl %r9d,%r8d                  
    andl $8388607,%eax              
    negl %r8d                       
    orl $8388608,%eax               
    testl %r8d,%r8d                 
    jl .LBB2_fast_trunc_one         
    movl %r8d,%ecx                  
    movl %eax,%edx                  
    sarl %cl,%edx                   
.Lt_0_1538:
    andl $-2147483648,%edi          
    movl %edi,%eax                  
    negl %eax                       
    xorl %edx,%eax                  
    addl %edi,%eax                  
    ret                             
    .p2align 5,,31
.LBB2_fast_trunc_one:
    movl %r9d,%ecx                  
    movl %eax,%edx                  
    shll %cl,%edx                   
    jmp .Lt_0_1538

と同様ですが、同一ではありませんfast_trunc_two。

とにかく、最適化に関して言えば、それは宝くじです — それが何であるかです... コードが特定の方法でコンパイルされる理由を知ることは必ずしも容易ではありません。

于 2012-04-30T05:40:17.557 に答える