6

私はコース用のコンパイラを書いています。最適に処理する方法がわからないいくつかの最適化の問題に遭遇しました。レジスタに保持する必要がある (または高速計算のために保持する必要がある) N 個のローカル変数を使用する、入力言語からの while ループがあるとします。レジスタ数 N > K と仮定します。while ループの終わり近くで条件付きレジスタが変更される可能性があります。

たとえば、x のレジスタ (i386 では %eax としましょう) が次のステートメントの前に決定されたとします。

while ( x ) { x = x - 1 ; /* more statements */ }

more ステートメント コードでは、x がスタックにスピル バックされる可能性があります。コードが x を再評価するために while ループの先頭に戻ると、%eax を使用しようとしますが、これは x の値を保持していない可能性があります。だから私たちは次のようなものを持つことができます

        movl -8(%ebp), %eax        # eax <- x
        ....                       # do stuff but let x stay in %eax
_LOOP1: cmpl $0, %eax
        ....
        movl -12(%ebp), %eax       #eax now holds something else
        ....
        jmp _LOOP1

私が使用している 1 つの解決策は、while ステートメントの前に変更されたすべてのレジスタを強制的にスピルすることです (したがって、レジスタはコード ジェネレーターの観点からは空と見なされます)。while ループのラベルの後、コードは必要に応じてすべてをレジスタにロードする必要があります。

私の解決策は次のようなものです：

        movl -8(%ebp), %eax        # eax <- x
        ....                       # do stuff but let x stay in %eax
        movl %eax, -8(%ebp)        # spilling and clearing all registers
_LOOP1: movl -8(%ebp), %eax        # get a register for x again
        cmpl $0, %eax
        ....
        movl -12(%ebp), %eax       # eax now holds something else
        ....
        movl %eax, -8(%ebp)        # spill to prevent overwrite
        jmp _LOOP1

私の解決策は少し無関係または不必要であるようです。ここで忘れている一般的な最適化のトリックはありますか?

編集: if や if else などの条件文でも同様のことが発生することにも注意してください。これは、レジスタが条件のブロック内の変数に割り当てられる可能性があるため発生しますが、コード ジェネレーターは、その後の他のすべてのためにレジスタがそこに移動されたと想定します。私はその場合に対処するためのほぼ同じアプローチを持っています。

4

1 に答える 1

4

ここで探している一般的な手法は、通常「ライブレンジ分割」と呼ばれます。その用語をグーグル検索すると、さまざまな論文へのポインタが表示されます。基本的には、単一の変数（この例ではx）を複数の変数に分割し、それぞれが分割ポイントで次の変数にコピーされる、互いに素なライブ範囲を使用するという考え方です。したがって、ループの前にx.0があり、ループの直前にx.1にコピーされwhile、ループ内で使用されます。次に、ループの直後に、x.1をx.2にコピーし、ループの後でそれを使用します。分割された各変数は、異なるレジスタ（またはスタックスロット）に割り当てられる可能性があります。

ここには多くのトレードオフがあります。分割が多すぎると、コード内の変数が（多く）増え、レジスタ割り当てが非常に遅くなり、不要なコピーが発生する可能性があります。

于 2010-09-26T21:33:04.217 に答える