5

コンパイラを作成するためにx86アセンブラを学習しています。特に、さまざまなコンパイラーによって生成されるアセンブラーの種類をよりよく理解するために、さまざまな単純な再帰関数を取得し、それらをさまざまなコンパイラー（OCaml、GCCなど）にフィードしています。

簡単な再帰整数フィボナッチ関数があります。

int fib(int x) { return (x < 2 ? x : fib(x-1)+fib(x-2)); }

私の手書きのアセンブリは次のようになります。

fib:
    cmp eax, 2
    jl  fin
    push    eax
    dec eax
    call    fib
    push    eax
    mov eax, [esp+4]
    add eax, -2
    call    fib
    add eax, [esp]
    add esp, 8
fin:
    ret

を使用してその関数をIntel-syntaxアセンブラにコンパイルすると、次のgcc -O2謎めいたコードが生成されます。

_fib:
    push    edi
    push    esi
    push    ebx
    sub esp, 16
    mov edi, DWORD PTR [esp+32]
    cmp edi, 1
    jle L4
    mov ebx, edi
    xor esi, esi
L3:
    lea eax, [ebx-1]
    mov DWORD PTR [esp], eax
    call    _fib
    sub ebx, 2
    add esi, eax
    cmp ebx, 1
    jg  L3
    and edi, 1
L2:
    lea eax, [esi+edi]
    add esp, 16
    pop ebx
    pop esi
    pop edi
    ret
L4:
    xor esi, esi
    jmp L2

[esp+4]したがって、呼び出し規約はでの引数であり、の戻り値だと思いますeax。edi、、esiを押すことから始まりebxます。次に、スタックフレームに対してさらに16バイトを要求します。これは、4つの一時的なintに十分です。次に、引数である、ediから読み取られます。[esp+32]引数がの場合、引数だけであるセットにジャンプする前に、ゼロになる（？）<=1にジャンプします。引数がだった場合、引数はにコピーされ、ゼロになってからになります。では、計算のために再帰する前に、結果（n-1）をスタックフレームに設定して格納します。結果はに追加されますL4esiL2eax=esi+ediedi>1ebxesiL3L3eax=ebx-1espfib(n-1)esi、ebxに設定されn-2、ループバックします。そうでないL3場合は、にフォールスルーする前にebx>1の下位ビットを抽出します。ediL2

このコードが非常に複雑なのはなぜですか（たとえば、実行された最適化の名前が表示されていないのですか？）？

再帰呼び出しfib(n-2)は、蓄積するループに置き換えられたようですesiが、その呼び出しはテール位置になかったので、これはどのように行われましたか？

の目的は何and edi, 1ですか？

の目的は何mov DWORD PTR [esp], eaxですか？

スタックフレームがこんなに大きいのはなぜですか？

このアルゴリズムをCに分解して、何が起こっているのかを明確にすることはできますか？

私の予備的な印象は、GCCがかなり貧弱なx86アセンブラーを生成するということです。この場合、同等のパフォーマンスを実現するために2倍以上のコードが必要です（両方のプログラムでこの1.6GHz Atomのfib（40）の場合は3.25秒）。それは公平ですか？

4

3 に答える 3

8

上記のコメントに加えて、再帰は次のように置き換えることで末尾呼び出しに巻き戻されていることに注意してください。

return x < 2 ? x : fib(x - 2) + fib(x - 1);

と：

if ((xprime = x) < 2) {
    acc = 0;
} else {
    /* at this point we know x >= 2 */
    acc = 0; /* start with 0 */
    while (x > 1) {
       acc += fib(x - 1); /* add fib(x-1) */
       x -= 2; /* now we'll add fib(x-2) */
    }
    /* so at this point we know either x==1 or x==0 */
    xprime = x == 1 ? 1 : 0; /* ie, x & 1 */
}
return xprime + acc;

このかなりトリッキーなループは、複数の最適化ステップから生じたのではないかと思います。gcc2.3については、gcc最適化をいじっていたわけではありません（現在はすべて非常に異なっています！）。

于 2012-04-07T22:07:43.380 に答える
2

非常に簡単に言えば、fib(x-2)等しいfib(x-3) + fib(x-4)、fib(x-4)等しいfib(x-5) + fib(x-6)などであるため、 （等しい）fib(x)として計算されます。つまり、gccはへの呼び出しをインライン化します。これは再帰関数に対して行う非常に賢い方法です。fib(x-1) + fib(x-3) + fib(x-5) + ... + fib(x&1)fib(x&1)x&1fib(x-2)

于 2012-04-07T22:14:19.170 に答える
2

この最初の部分は、呼び出し規約に従って保持する必要のあるレジスターが破棄されないようにすることです。ここで使用されている呼び出し規約はですcdecl。

_fib:
    push    edi
    push    esi
    push    ebx
    sub esp, 16

DWORD PTR[esp+32]あなたのx：

    mov edi, DWORD PTR [esp+32]
    cmp edi, 1
    jle L4

xが1以下の場合（これはあなたに対応しますx < 2）、次のいずれかに移動しますL4。

L4:
    xor esi, esi
    jmp L2

これはゼロになり、次のようesiに分岐しL2ます。

L2:
    lea eax, [esi+edi]
    add esp, 16
    pop ebx
    pop esi
    pop edi
    ret

これによりeax、（戻り値）が。で設定されesi+ediます。esiはすでに0なのでedi、0と1の場合にロードされるだけです。これはに対応しx < 2 ? xます。

x次に、そうでない場合を見てみましょう< 2。

    mov ebx, edi
    xor esi, esi
L3:
    lea eax, [ebx-1]
    mov DWORD PTR [esp], eax
    call    _fib

最初にxにコピーされebx、次にesiゼロにされます。

次に、eaxに設定されx - 1ます。この値はスタックの一番上に移動され、_fib呼び出されます。これはに対応しfib(x-1)ます。

    sub ebx, 2
    add esi, eax

ebxこれにより、 （ ）から2が差し引かれxます。次に（以前は0に設定されていた呼び出しeaxからの戻り値_fibがに追加されます）。esiしたがってesi、の結果が保持されfib(x-1)ます。

    cmp ebx, 1
    jg  L3
    and edi, 1

ebxは1と比較されます。1より大きい場合は、にループバックしL3ます。それ以外の場合（0または1の場合）、実行and edi, 1してフォールスルーしますL2（これが以前に行ったことを分析しました）。は、でを実行するのand edi, 1と同じです。%2x

大まかに言えば、これはコードが行うことです。

  • スタックフレームを設定し、レジスタを保存します
  • の場合x < 2、を返しxます。
  • 2未満になるfib(x-...)まで呼び出しと合計を続けます。この場合、ケースにフォールスルーします。xx < 2

最適化は、GCCx >= 2が再帰的にではなくループでそれらを実行することによってケースを巻き戻すことです。

于 2012-04-07T22:15:29.357 に答える