Um bei der Berechnung von schwach besetzten Matrizen Zeit zu sparen
(floating point Matrizen auf einem ATmega64 sind ja eh schon
sadistisch), mache ich vor jeder Multiplikation einen schnellen
Vergleich, ob einer der beiden Faktoren 0 ist, um in diesem Fall statt
der Multiplikation einfach eine Zuweisung von 0.0 an die
Ergebnisvariable zu machen.
Beim betrachten der Compilerausgabe (.lss) ist mir allerdings
aufgefallen, dass dieser Vergleich längst nicht so schnell ist wie
gedacht, denn statt die 4 Bytes eines jeden Werts einfach auf 0 zu
testen und dann zu verzweigen, wird jeweils 0x00000000 in vier Register
geladen und anschließend __cmpsf2 aufgerufen.
Hier eine der betreffenden Stellen:
und was daraus (aus dem Vergleich) in der .lss wird:
1
9c4e: ld r14, Y
2
9c50: ldd r15, Y+1 ; 0x01
3
9c52: ldd r16, Y+2 ; 0x02
4
9c54: ldd r17, Y+3 ; 0x03
5
9c56: subi r28, 0xAD ; 173
6
9c58: sbci r29, 0x01 ; 1
7
9c5a: movw r24, r16
8
9c5c: movw r22, r14
9
9c5e: ldi r18, 0x00 ; 0
10
9c60: ldi r19, 0x00 ; 0
11
9c62: ldi r20, 0x00 ; 0
12
9c64: ldi r21, 0x00 ; 0
13
9c66: call 0xca94 ; 0xca94 <__cmpsf2>
Wie kann man dem Compiler klar machen, dass er in diesem speziellen Fall
bitte die deutlich einfachere und schnellere Variante nehmen soll?
Mir fällt nur die Möglichkeit ein, eine eigene Funktion dafür zu
schreiben, da ein typecast auf einen int Typ ja wieder eine
Konvertierungsfunktion aufrufen würde.
GCC Version ist 4.5.3 unter Kubuntu mit Kernel 2.6.32-34, Optimierung
steht auf Level 3.
Flockinger schrieb:> Wie kann man dem Compiler klar machen, dass er in diesem speziellen Fall> bitte die deutlich einfachere und schnellere Variante nehmen soll?
Compiler umschreiben. ;-)
> schreiben, da ein typecast auf einen int Typ ja wieder eine> Konvertierungsfunktion aufrufen würde.
Nicht bei sowas wie
A. K. schrieb:> Flockinger schrieb:>>> Wie kann man dem Compiler klar machen, dass er in diesem speziellen Fall>> bitte die deutlich einfachere und schnellere Variante nehmen soll?>> Compiler umschreiben. ;-)>>> schreiben, da ein typecast auf einen int Typ ja wieder eine>> Konvertierungsfunktion aufrufen würde.>> Nicht bei sowas wie
1
> #define FloatIsNull(x) (*(int32_t*)&(x) == 0)
• Erstens macht es nicht das, was es soll denn die
Darstellung der 0 ist nicht eindeutig.
• Und Zweitens kollidiert das mit den Aliasing-Regeln:
long ist kein Alias für float.
Johann L. schrieb:> • Erstens macht es nicht das, was es soll denn die> Darstellung der 0 ist nicht eindeutig.
Da es hier nur zur Beschleunigung von teilweise mit 0 besetzten Matrizen
vorgesehen war ist das weniger relevant.
Allgemein betrachtet sind die Operatoren == und != bei Fliesskommadaten
ohnehin problematisch.
> • Und Zweitens kollidiert das mit den Aliasing-Regeln:> long ist kein Alias für float.
Stimmt.
Vielen Dank für eure Tipps. Leider führt die Variante über Pointer
casten dazu, dass die Werte - obwohl gerade erst in Register geladen -
erneut aus dem SRAM geladen werden, was wieder 8 ClkCycles zusätzlich
braucht. Das ist zwar gegenüber der __mulsf3 kaum was (2*8/138=11,6%),
aber dennoch wollte ich nicht einsehen, kostbare Rechenzeit zu
verschwenden.
Daher habe ich doch eine Funktion geschrieben, allerdings als inline
Funktion mit inline assembler:
1
inlineuint8_tFloatIsNull(floatvalue_to_test){
2
uint8_ttestresult;
3
asm(" BST %D1,7 ;store sign bit for restoration ""\n\t"
4
" CBR %D1,0x80 ;clear sign bit to detect 0.0 and -0.0 ""\n\t"
5
" SUBI %A1,0 ;test low byte ""\n\t"
6
" SBCI %B1,0 ; ""\n\t"
7
" SBCI %C1,0 ; ""\n\t"
8
" SBCI %D1,0 ;Flag Z is set if all bytes were 0x00 ""\n\t"
9
" LDI %0,1 ; ""\n\t"
10
" BREQ 1f ;Skip if Flag Z is set ""\n\t"
11
" CLR %0 ; ""\n\t"
12
"1: ""\n\t"
13
" BLD %D1,7 ;restore sign bit ""\n\t"
14
:[retval]"=d"(testresult)
15
:[testval]"d"(value_to_test));
16
returntestresult;
17
}
alternative:
1
inlineuint8_tFloatIsNull(floatvalue_to_test){
2
uint8_ttestresult;
3
asm(" BST %D1,7 ;store sign bit for restoration ""\n\t"
4
" LSL %D1 ;clear sign bit to detect 0.0 and -0.0 ""\n\t"
5
" CP %A1,__zero_reg__ ;test low byte ""\n\t"
6
" CPC %B1,__zero_reg__ ; ""\n\t"
7
" CPC %C1,__zero_reg__ ; ""\n\t"
8
" CPC %D1,__zero_reg__ ;Flag Z is set if all bytes were 0x00 ""\n\t"
9
" LDI %0,1 ; ""\n\t"
10
" BREQ 1f ;Skip if Flag Z is set ""\n\t"
11
" CLR %0 ; ""\n\t"
12
" LSR %D1 ;restore highest byte if not Null ""\n\t"
13
"1: ""\n\t"
14
" BLD %D1,7 ;restore sign bit ""\n\t"
15
:[retval]"=d"(testresult)
16
:[testval]"r"(value_to_test));
17
returntestresult;
18
}
Die obere Variante braucht ein Wort und einen Takt weniger, dafür müssen
sowohl Input als auch Output im oberen Registerbereich liegen. Die
zweite Variante erlaubt zu genau diesem Preis die allokation der float
Variable im gesamten Registerbereich.
Das ist nicht korrekt:
%0 ist earl-clobber, die Constraint muss also "=&d" sein anstatt "=d".
Beispielsweise wird es falsch, wenn der Compiler value_to_test nach R16
leht und value_to_test nach R17. Dies ist möglich, falls value_to_test
nach dem test nicht mehr verwendet wird.
Denkst du, eine entsprechende Optimierung im Compiler wäre sinnvoll?
Was sind die Voraussetzungen dafür?
-funsafe-math-optimizations?
-ffinite-math-only?
-fno-signaling-nans?
Hallo Johann,
nach einigem überlegen hab ich herausgefunden, was du meinst (lies dir
bitte dein Posting nochmal durch und versuche zu erkennen, dass solche
Tippfehler ein Verständnis deines Postings erheblich erschweren).
Dein Argument ist also, dass die Wiederherstellung von %D1 zu einem
falschen Rückgabewert führen kann, wenn %0 und %D1 im selben Register
abgelegt werden. Da muss ich dir Recht geben. Mir schien es in dem
Moment wichtiger, dass die Gleitkommazahl auf jeden Fall erhalten
bleibt. Deiner Argumentation nach ist der Compiler aber wohl schlau
genug zu wissen, dass er das Ausgangsregister nicht auf den Eingang
legt, wenn er den Eingang danach noch benötigt.
Deine Variante das Carry-Bit zu benutzen ist gut, so kommt man um den
Branch rum, der bei Verwendung des Zero-Bits unvermeidbar ist.
Allerdings wird dabei - wie du in deinem Kommentar bereits angedeutet
hast - die Funktion invertiert, weil das Carry-Bit ja 1 wird, wenn die
Zahl ungleich 0 ist. Außerdem nimmt LSL nur ein Argument, das
_tmp_reg_ kannst du dir also sparen. Die gesamte Funktion würde dann
so aussehen und benötigt unabhängig vom Eingang immer 8 ClockCycles:
1
inlineuint8_tFloatIsNotNull(floatvalue_to_test){
2
uint8_ttestresult;
3
asm("MOV __tmp_reg__,%D1 ;store sign bit for restoration""\n\t"
4
"LSL %D1 ;clear sign bit to detect 0.0 and -0.0""\n\t"
5
"CP __zero_reg__,%A1 ;test low byte ""\n\t"
6
"CPC __zero_reg__,%B1 ; ""\n\t"
7
"CPC __zero_reg__,%C1 ; ""\n\t"
8
"CPC __zero_reg__,%D1 ;Flag C is set if any byte was >0x00""\n\t"
9
"MOV %D1,__tmp_reg__ ;restore sign bit ""\n\t"
10
"SBC %0,%0 ;-1 if Carry was set, 0 if not""\n\t"
11
:[retval]"=d"(testresult)
12
:[testval]"d"(value_to_test));
13
returntestresult;
14
}
Was deine Fragen bezüglich Compiler-Optimierung angeht, verstehe ich
deine Vorwürfe nicht. Die Funktion tut genau das, was ihr Name aussagt.
Dass z.B. eine Multiplikation 0*inf ein NaN ergibt und daher ausgeführt
werden sollte, obwohl einer der beiden Operanden 0 ist, liegt in der
Verantwortung des Benutzers. Hier kann man ja die bereits existierenden
Funktionen isnan() und isinf() heranziehen. Diese Fälle hatte ich bei
mir zwar nicht abgedeckt, aber das geht an der Aufgabe des Compilers
vorbei. Ich hatte eine Abfrage gestellt, ob der Wert 0 ist und genau das
war mir nicht schnell genug.
Flockinger schrieb:> Dein Argument ist also, dass die Wiederherstellung von %D1 zu einem> falschen Rückgabewert führen kann, wenn %0 und %D1 im selben Register> abgelegt werden. Da muss ich dir Recht geben. Mir schien es in dem> Moment wichtiger, dass die Gleitkommazahl auf jeden Fall erhalten> bleibt.
Beides ist wichtig. Unterschied ist nur, daß ein Fehler seltener
auftritt als der andere und nicht so leicht zu finden ist.
> Deiner Argumentation nach ist der Compiler aber wohl schlau> genug zu wissen, dass er das Ausgangsregister nicht auf den Eingang> legt, wenn er den Eingang danach noch benötigt.
Genau.
Wenn das Ausgangsregister sich allerdingsmit dem Eingangsregister
überlappt, und das E-Register verwendet wird, nachdem das A-Register
verändert wurde, gibt es ein Problem ohne early-clobber.
> Deine Variante das Carry-Bit zu benutzen ist gut, so kommt man um den> Branch rum, der bei Verwendung des Zero-Bits unvermeidbar ist.> Allerdings wird dabei - wie du in deinem Kommentar bereits angedeutet> hast - die Funktion invertiert, weil das Carry-Bit ja 1 wird, wenn die> Zahl ungleich 0 ist.
Ja, der Schnippel liefert quasi
1
wert != 0 ? -1 : 0;
> Was deine Fragen bezüglich Compiler-Optimierung angeht, verstehe ich> deine Vorwürfe nicht.
Vorwürfe??
> Dass z.B. eine Multiplikation 0*inf ein NaN ergibt und daher ausgeführt> werden sollte, obwohl einer der beiden Operanden 0 ist, liegt in der> Verantwortung des Benutzers. Hier kann man ja die bereits existierenden> Funktionen isnan() und isinf() heranziehen. Diese Fälle hatte ich bei> mir zwar nicht abgedeckt, aber das geht an der Aufgabe des Compilers> vorbei.
Auch Vergleiche können gegen eine INF oder NaN gehen.
> Ich hatte eine Abfrage gestellt, ob der Wert 0 ist und genau das> war mir nicht schnell genug.
Meine Frage war, unter welchen Bedingungen es legitim ist, eine solche
Optimierung bereits im Compiler zu machen. Der Code ist ja recht einfach
und zudem weiß der Compiler, ob er die Eingabe zerstören darf weil die
nicht mehr benötogt wird, oder eben nicht.
Momentan ist es so, das der AVR-Teil im GCC keine float-Vergleiche
unterstützt, und diese Vergleiche einfach auf Aufrufe von
Bibliotheksfunktionen wie __eqsf2 für a == b abgebildet werde.
Fasst man diese Vergleiche im AVR-Teil an und sagt "Ja, avr-gcc kann
Floats gegeneinander vergleichen", dann ist es nicht möglich, sich
spezielle Vergleiche rauszupicken. Stattdessen muss man alle
float-Vergleiche implementieren — zumindest alle ordered Comparisons
gegen alle Werte.
Johann L. schrieb:> Vorwürfe??
Deine Optionen klangen so, als würdest du mir vorwerfen, unsauberen Code
zu schreiben, der z.B. bei +-INF oder NaN nicht funktioniert.
Sorry, falls ich da etwas zu negativ in der Interpretation war.
> Auch Vergleiche können gegen eine INF oder NaN gehen.
Das ist richtig, aber mir gings ja wie gesagt nur um den Spezialfall
==0.0 und das funktioniert (zumindest die hier gezeigte Variante) auch
gegen INF und NaN.
> Meine Frage war, unter welchen Bedingungen es legitim ist, eine solche> Optimierung bereits im Compiler zu machen. Der Code ist ja recht einfach> und zudem weiß der Compiler, ob er die Eingabe zerstören darf weil die> nicht mehr benötogt wird, oder eben nicht.>> Momentan ist es so, das der AVR-Teil im GCC keine float-Vergleiche> unterstützt, und diese Vergleiche einfach auf Aufrufe von> Bibliotheksfunktionen wie __eqsf2 für a == b abgebildet werde.
OK, das ist die Erklärung, warum der Compiler einfach alles auf die
__cmpsf2 biegt.
> Fasst man diese Vergleiche im AVR-Teil an und sagt "Ja, avr-gcc kann> Floats gegeneinander vergleichen", dann ist es nicht möglich, sich> spezielle Vergleiche rauszupicken. Stattdessen muss man alle> float-Vergleiche implementieren — zumindest alle ordered Comparisons> gegen alle Werte.
Du meinst also, es ist nicht möglich eine Abfrage in den Compiler
einzubauen, die spezielle Vergleiche (wie z.B. auf ==0.0 oder !=0.0)
durch Kurzlösungen ersetzt und nur den Rest an die allgemeine
Bibliotheksfunktion weiter reicht?
Vielleicht sollte man dann die obige Funktion als solche in die avr-libc
mitaufnehmen, analog zu isnan() oder isinf() um auch Benutzern, die kein
Assembler können und diesen Thread nicht finden, die Möglichkeit zu
geben, einen schnellen Vergleich von floats auf ==0.0 in ihren
Programmen zu verwenden.
Flockinger schrieb:> Johann L. schrieb:>> Fasst man diese Vergleiche im AVR-Teil an und sagt "Ja, avr-gcc kann>> Floats gegeneinander vergleichen", dann ist es nicht möglich, sich>> spezielle Vergleiche rauszupicken. Stattdessen muss man alle>> float-Vergleiche implementieren — zumindest alle ordered Comparisons>> gegen alle Werte.>> Du meinst also, es ist nicht möglich eine Abfrage in den Compiler> einzubauen, die spezielle Vergleiche (wie z.B. auf ==0.0 oder !=0.0)> durch Kurzlösungen ersetzt und nur den Rest an die allgemeine> Bibliotheksfunktion weiter reicht?
Möglich ist es. GCC ist ja kein Hexenwerk sondern von Menschenhand.
Aber es ist nicht einfach im AVR-Teil zu machen.
Dokumentiert ist es in can_compare_p in optabs.c:
1
Nonzero if we can perform a comparison of mode MODE straightforwardly.
2
PURPOSE describes how this comparison will be used. CODE is the rtx
3
comparison code we will be using.
4
5
??? Actually, CODE is slightly weaker than that. A target is still
6
required to implement all of the normal bcc operations, but not
7
required to implement all (or any) of the unordered bcc operations. */
http://gcc.gnu.org/viewcvs/trunk/gcc/optabs.c?content-type=text%2Fplain&view=co
Um es einfach zu machen, müsste erst diese Restruktion beseitigt werden.
Aber ähnlich Restriktonen gibt es für viele andere Pattern auch:
Entweder alles oder nix, Rosinen rauspicken geht nur bei wenigen Pattern
wie zB Rotate.
Leider ist es auch nicht möglich, einen Combine-Pattern zu schreiben,
weil ds erzeugte Pattern einen Fuktionsaufruf darstellt.
> Vielleicht sollte man dann die obige Funktion als solche in die avr-libc> mitaufnehmen, analog zu isnan() oder isinf() um auch Benutzern, die kein> Assembler können und diesen Thread nicht finden, die Möglichkeit zu> geben, einen schnellen Vergleich von floats auf ==0.0 in ihren> Programmen zu verwenden.
Die avr-libc kann bereits float-Vergleiche, zumindest hab ich da ein
__gesf2 gesehen. Was genau unterstützt wird weiß ich aber nicht;
ebensowenig, ob sich diese Funktionen die Operanden explizit anschauen
und abkürzen, falls mindestens einer 0.0 ist.
Thread beobachten
Seitenaufteilung abschalten