最適化された関数を書いているときに、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
。ここでの質問は、何が原因なのでしょうか?
ベストアンサー1
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
0
2 つの値のうち1 つだけを取ることができます0x80000000
。
- のとき
x = 0
、x + (y ^ x) = y
次のことが成り立ちます。 - による加算と排他的論理
0x80000000
和は同じです。符号ビットを反転します。したがって、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)
間で分割されています。
^ -sign
GCC を混乱させてこの最適化を行わないようにするには、これで十分ではないかと考えています。(をブランチから取り出して、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 */
}