Unsigned 64-Bit-Doppelwandler: warum dieser Algorithmus von g ++

Question

g Mit ++ 4.9.2 wenn ich

bool int_dbl_com(const unsigned long long x, const double y) 
{ 
    return x <= y; 
} 

kompilieren

dann der Assembler Ausgabe lautet:

testq  %rcx, %rcx 
js  .L2 
pxor  %xmm0, %xmm0 
cvtsi2sdq %rcx, %xmm0 
ucomisd %xmm0, %xmm1 
setae  %al 
ret 

Der Befehl cvtsi2sdqunterzeichnet Umwandlung, und die erste Test- und Sprungkombination ist zu prüfen, ob %rcx < 0. Wenn ja, gehen wir zu L2, und das verstehe ich nicht:

.L2: 
movq  %rcx, %rax 
andl  $1, %ecx 
pxor  %xmm0, %xmm0 
shrq  %rax 
orq  %rcx, %rax 
cvtsi2sdq %rax, %xmm0 
addsd  %xmm0, %xmm0 
ucomisd %xmm0, %xmm1 
setae  %al 
ret 

Naiv Sie %rcx halbieren könnte, konvertieren zu einem Doppel in %xmm0, und fügen Sie dann %xmm0 sich den ursprünglichen Wert zurück (Akzeptieren Sie natürlich, dass Sie eine Genauigkeit niedriger Ordnung verloren haben, die von einer 64-Bit-Ganzzahl in eine 64-Bit-Gleitzahl übergeht.

Aber das ist nicht, was der Code tut: Es scheint das niedrigste Bit von %rcx zu speichern und dann zurück zum Ergebnis. Warum?? Und warum sollten Sie sich die Mühe machen, wenn diese Bits niedriger Ordnung sowieso verloren gehen (oder irre ich mich hier)?

(Der gleiche Algorithmus scheint unabhängig von der Optimierung verwendet werden, ich O3 hier verwendet, um es einfacher zu sehen.)

Answer 1

.L2: 
movq  %rcx, %rax 
andl  $1, %ecx  ; save the least significant bit of %rax 
pxor  %xmm0, %xmm0 
shrq  %rax   ; make %rax represent half the original number, as a signed value 
orq  %rcx, %rax  ; “round to odd”: if the division by two above was not exact, ensure the result is odd 
cvtsi2sdq %rax, %xmm0 ; convert to floating-point 
addsd  %xmm0, %xmm0 ; multiply by two 
ucomisd %xmm0, %xmm1 ; compare … 
setae  %al 
ret 

Die letzten drei Befehle <= und return aus dem Quellcode implementieren. Die anderen sind alle Teil der Umwandlung von uint64_t zu double.

Der schwierig zu verstehende Schritt ist der, den ich als "rund zu ungerade" kommentiert habe. "Rounding to Odd" ist eine Technik, die die unangenehmen Effekte von “double rounding” verhindert.

Im Endeffekt wird der Algorithmus von 64-Bit zu 63-Bit und dann von 63 Bits zu IEEE 754 binary64 konvertieren. Wenn diese beiden Konvertierungen naiv implementiert werden, können sie in einigen Fällen zu einem Ergebnis führen, das sich von einer direkten Einzelkonvertierung von 64-Bit-Ganzzahl in Fließkommazahl unterscheidet. Dies wird als "Doppelrundung" bezeichnet.

Rounding to odd ensures das Ergebnis der Zwischenrundung nicht auf einen Wert, der bei Doppelrundung in die falsche Richtung gerundet würde. Das ist genug, um die folgenden Sequenzen äquivalent für alle Eingänge zu machen:

64-bit ---(round to odd)---> 63-bit ---(round to nearest even)----> binary64 
64-bit -(round-to-nearest-even,the conversion the compiler wants)-> binary64 

andere Aspekte Ihrer Frage zu beantworten:

Aber das ist nicht das, was der Code tut: es scheint, die niedrigste Ordnung zu sparen Bit %rcx und dann ors das zurück zum Ergebnis. Warum?? Und warum sollten Sie sich die Mühe machen, wenn diese Bits niedriger Ordnung sowieso verloren gehen (oder irre ich mich hier)?

Dies ist genau, wie in diesem bestimmten Fall Round-to-Odd zu implementieren. Das niedrigstwertige Bit von %rcx ist eins, wenn die Verschiebung keine exakte Division durch zwei ist, und in diesem Fall muss das Ergebnis ungerade gemacht werden.

Derselbe Algorithmus scheint unabhängig von der Optimierung verwendet zu werden; Ich habe -O3 hier benutzt, um es leichter zu sehen.

Die Befehlssequenz ist optimal (so weit wie I, für moderne Prozessoren sehen) und entspricht die Source-Level-Umwandlung von uint64_tdouble Int. Es erfordert keinen Aufwand vom Compiler, um es sogar auf der niedrigsten Optimierungsebene zu verwenden. Was mit der Optimierung passieren könnte (aber hier nicht passiert), ist, dass die Anweisungen mit anderen Anweisungen, die anderen Konstrukten auf Quell-Ebene entsprechen, verschmolzen werden. Aber es hat keinen Sinn, eine andere Befehlsfolge zu haben als die optimale, die für Konvertierungen unter -O0 erzeugt werden muss.