Hallo Leute,
bin gerade dabei ein LCD-Display mit einem AVR32-Board zu programmieren.
Soweit so gut... Display läuft... leider braucht das Bild etwa 4-5 sek
bis es aufgebaut ist.
Nun möchte ich mein C-Code optimieren.
die dafür nötige Code Zeile ist folgende. (Anhang)
"Befehl" ist ein 18 Bit langes Wort.
Die einzelnen "AVR32_PIN_PBXX" geben an an welcher stelle sich dieses
Pin befindet.
Nun zu meiner Frage. Hat jemand Ideen oder Vorschläge wie ich diese paar
Zeilen kürzer, schöner bzw. schnelle berechnen kann. Ich vermute das die
Shifts sehr lange brauchen.
Danke und Gruß Adam
Hallo Stefan,
wenn es dieser Code nicht ist kann ich mir fast nicht vorstellen was es
sonst sein kann.
- Vielleicht die Funktionsaufrufe?
- Schleifen habe ich wenige.
Der Code (Funktion) unter den defines wird pro Pixel einmal aufgerufen.
Das Display ist 128x160 Pixel groß.
20480 Pixel x 18 Bit/p = 368,640 kBit/Bild
Der µC läuft mit 12 MHz.
Das sind 2343,75 Takte pro Pixel.
Gruß Adam
Adam wrote:
> Ich vermute das die> Shifts sehr lange brauchen.
Warum guckst Du nicht einfach mal ins Assemblerlisting, wieviel Code
erzeugt wird und ob er Unterfunktionen aufruft oder Loops enthält.
Wenn man den Verdacht hat, daß etwas viel Zeit verbraucht, dann
kommentiert man es aus und mißt, ob es deutlich schneller geht.
Peter
Ich war mir nicht mehr sicher mit meiner Antwort und habe sie gelöscht.
Ich hatte nämlich beim ersten Lesen vorschnell gedacht, dass der
Compiler das meiste zur Compilezeit berechnen kann und dass dein
Zeitfresser woanders (in dem nicht angegebenen Codestück) sitzt.
Dann habe ich beim Scrollen der ewig langen Zeile gesehen, dass du die
Variable befehl bitweise auseinander pfriemelst und war mir unsicher
geworden, ob das mit der Compilezeit noch stimmt. Man müsste das im
Assemblerlistung nachschauen, was da abgeht.
Bei anderen µC macht man das üblicherweise etwas anders. Man arbeitet
dort mit Bitmasken und versucht möglichst viele Bits möglichst wenigen
Maschinen Anweisungen (XOR, OR, AND) zugleich zu manipulieren. Es gibt
den Artikel Bitmanipulation in der Artikelsammlung, der dir eine
Idee geben kann, wie das funktioniert.
Für diesen Weg ist es günstig, wenn die Bits von Quelle und Ziel
möglichst aufeinanderfolgende Bits sind und nicht wild durcheinander
gemixt werden muss. Soweit ich deinen Code sehe, könnte das bei dir der
Fall sein.
Es hat sich schon immer bewährt, Hardwaredatenbits nicht wild
durcheinander an die Ports zu hängen. Bring die Bits in die richtige
Reihenfolge, und schieb dann ganze bytes raus.
Wenn das gar nicht geht, schau mal in den Befehlssatz des AVR32, ob der
in einem Befehl beliebig shiften kann (ich kenn den Prozessor nicht).
Wenn nicht, ist es effektiver, statt der aufeinanderfolgenden befehl>>1,
befehl>>2, usw. immer nur um ein bit zu shiften, und sich das
Zwischenergebnis zu merken.
Oliver
Was auch helfen kann: Papier und Bleistift!
Man macht sich eine Zeichnung mit den Quellbits, so wie sie in der
Variable stehen, und dem Ziel entsprechend.
Beim Striche ziehen zwischen beiden, merkt man, was man in einem Rutsch
übertragen kann und was man dabei vor Veränderungen mit einer Maske
schützen muss.
Oliver wrote:
> Es hat sich schon immer bewährt, Hardwaredatenbits nicht wild> durcheinander an die Ports zu hängen. Bring die Bits in die richtige> Reihenfolge, und schieb dann ganze bytes raus.
Kann man nicht so generell sagen. Es kommt darauf an, ob sich dadurch
der Code verlängert und ob diese Verlängerung relevant ist.
Z.B. beim Schalten eines Relais ist die Verlängerung nicht relevant.
Und bei einer 7-Segment Anzeige kann man die Pins würfeln, wie man will,
man braucht eh ne 7-Segment Tabelle, es ergibt sich also keine
Codevergrößerung.
Ich benutze daher die freie Pinzuweisung sehr gerne, wenn sich das
Layout vereinfacht.
Wenn man aber ne Peripherie hat, auf die sehr häufig zugegriffen wird
und die obendrein ein Byteinterface hat, dann schließt man die natürlich
Memory-mapped an (MMIO).
Große MCs haben ja in der Regel einen externen Memory-Bus.
Und dann geht der Transfer ruckzuck per DMA ganz ohne irgendwelches
umständliches Bitgewackel. Die CPU kann dabei sogar was anderes machen.
Peter
Hallo nochmal...
vielen Dank für die Zahlreichen Tipps und Ratschläge. Habe einiges
Ausprobiert und geringe Beschleunigung erhalten.
Außerdem habe ich einen kleinen Test gemacht. Hab einfach mal nen Toggle
in eine While(1) schleife eingefügt.
Mein Oszi hat eine Frequenz von 560 kHz gemessen.
560 000 Hz / 20 000 Pixel = 28 Umschaltungen pro Pixel
Wenn ich jetzt daran denke das ich schon 16 GPIO stellen muss + 4
Steuerleitung. Dann überlege ich ob ich nicht schon recht weit am
Optimum bin?
Was meint ihr?
Gruß Adam
Adam Adam wrote:
> Wenn ich jetzt daran denke das ich schon 16 GPIO stellen muss + 4> Steuerleitung. Dann überlege ich ob ich nicht schon recht weit am> Optimum bin?>> Was meint ihr?
Die Frage wird dir nur ein Blick in den erzeugten Code bringen, und ob
der Compiler die Sequenz (quasi) optimal übersetzt bzw. die Maschine
optimal ausnutzt.
Mit fortschreitender Compilerentwicklung wird der erzeugte Code immer
unabhängiger von der Quelle, will meinen durch die Quelle lässt sich
kaum noch die Erzeugung bestimmer Codesequenzen immer weniger
kontrollieren.
GCC 4.x zB zerfleddert alle Ausdrücke in simpelste Zuweisungen à la
a = b+c und goto und dann folgt eine Optimierungs-Wumme nach der
anderen...
@ Johann L. (gjlayde) Benutzerseite
>> Was meint ihr?>Die Frage wird dir nur ein Blick in den erzeugten Code bringen, und ob>der Compiler die Sequenz (quasi) optimal übersetzt bzw. die Maschine>optimal ausnutzt.
NEIN! Die Frage kann man (leider) sehr leicht beim Blick auf den
Quelltext beantworten, siehe mein anderes Posting.
>Mit fortschreitender Compilerentwicklung wird der erzeugte Code immer>unabhängiger von der Quelle, will meinen durch die Quelle lässt sich>kaum noch die Erzeugung bestimmer Codesequenzen immer weniger>kontrollieren.
Der beste Compiler kann dermassen schlechte Programmierung nicht
optimieren.
Brain 2.0 schlägt immer noch locker GCC 100.0.
MFG
Falk
@ Adam Adam (Firma Privat) (bolepl)
>Steuerleitung. Dann überlege ich ob ich nicht schon recht weit am>Optimum bin?
Du bist meilenweit davon entfernt. Deine Routine ist sowas von schlecht,
das geht gar nicht.
Tut mir leid, muss man einfach so sagen.
Wie Peter bereits feststellte, mach man sowas memory mapped, dann geht
das ratz fatz. Schliesslich braucht so ein popeliges LCD mit seinen 20K
Pixel gerade mal bissel mehr als 50kB, die schiebt ein uC von dem
Kaliber in ein paar Dutzend us rüber. Wenn mans richtig macht!
Und selbst ohne Memory Mapped IO geht das WESENLICH besser.
1
//1st transfer (Upper)
2
3
gpio_port->ovr=rs<<(RS&0x1F)|
4
(1<<(RD&0x1F))|
5
(0<<(WR&0x1F))|
6
((befehl>>2)&0x0001)<<(DB0&0x1F)|
7
((befehl>>3)&0x0001)<<(DB1&0x1F)|
8
((befehl>>4)&0x0001)<<(DB2&0x1F)|
9
((befehl>>5)&0x0001)<<(DB3&0x1F)|
10
((befehl>>6)&0x0001)<<(DB4&0x1F)|
11
((befehl>>7)&0x0001)<<(DB5&0x1F)|
12
((befehl>>8)&0x0001)<<(DB6&0x1F)|
13
((befehl>>9)&0x0001)<<(DB7&0x1F)|
14
((befehl>>10)&0x0001)<<(DB8&0x1F)|
15
((befehl>>11)&0x0001)<<(DB9&0x1F)|
16
((befehl>>12)&0x0001)<<(DB10&0x1F)|
17
((befehl>>13)&0x0001)<<(DB11&0x1F)|
18
((befehl>>14)&0x0001)<<(DB12&0x1F)|
19
((befehl>>15)&0x0001)<<(DB13&0x1F)|
20
((befehl>>16)&0x0001)<<(DB14&0x1F)|
21
((befehl>>17)&0x0001)<<(DB15&0x1F);
So eine Monsterzeile sieht nicht nur schlecht aus, sie ist es auch.
Warum packst du nicht einfach die 18 Bit Daten DIREKT an einen 32 Bit
Port, sinnvollerweise Bits 0..17, setzt mit zwei anderen IOs die
Steuersignale zur Datenübernahme und fertig. Dauert ein paar Dutzend
Takte. Zwar immernoch schnarchlangsam im Vergleich zu Memory Mapped IO
aber tausendmal schneller als 2300 Takt/Pixel!
Und die Bits online über Schiebeoperation EINZELN zu kopieren ins nun
GANZ doof! Das dauert auf der besten Maschine ewig. Hast du dir mal
überlegt, wieviel sinnlose Operationen du durchführst?
Als ersten Workaround könnte man das so machen.
Falk Brunner wrote:
> @ Johann L. (gjlayde) Benutzerseite>>>> Was meint ihr?>>>Die Frage wird dir nur ein Blick in den erzeugten Code bringen, und ob>>der Compiler die Sequenz (quasi) optimal übersetzt bzw. die Maschine>>optimal ausnutzt.>> NEIN! Die Frage kann man (leider) sehr leicht beim Blick auf den> Quelltext beantworten, siehe mein anderes Posting.
Du kannst an der Quelle nicht erkennen, was ein Compiler daraus macht,
weil das nicht spezifiziert ist. Es ist spezifiziert, wie das Resultat
auf die Maschine ist, aber nicht, wie ein Compiler das erreicht.
Von daher kann auch Code, der in C hübsch und knackig aussieht, zu
suboptimaler asm-Ausgabe führen.
>>Mit fortschreitender Compilerentwicklung wird der erzeugte Code immer>>unabhängiger von der Quelle, will meinen durch die Quelle lässt sich>>kaum noch die Erzeugung bestimmer Codesequenzen immer weniger>>kontrollieren.>> Der beste Compiler kann dermassen schlechte Programmierung nicht> optimieren.> Brain 2.0 schlägt immer noch locker GCC 100.0.
Erstens ist es nicht prinzipiell ausgeschlossen.
Zweitens hab ich nix gegenteiliges behauptet aber
Drittens stellt man sich mitunter selbst ein Bein, wenn man nicht genau
weiß, wie ein Compiler arbeitet.
Hier mal ein konkretes Beispiel für AVR: Eine Funktion soll 0 returnen,
wenn Bit 6 eines SFR 0 ist, ansonsten 1.
Jeder der sich etwas mit AVR auskennt würde folgenden "optimalen" Code
hinschreiben:
1
#include<avr/io.h>
2
3
unsignedcharfoo(void)
4
{
5
unsignedchara=0;
6
if(PIND&(1<<PD6))a=1;
7
8
returna;
9
}
der in 4 Instruktionen abgearbeitet werden kann:
1
ldi r24, 0
2
sbic 0x09, 6
3
ldi r24, 1
4
ret
gcc 4.3.2 mach sowohl bei Optimierung auf Codegröße als auch bei
Optimierung auf Geschwindigkeit (-O2 und -O3) daraus:
1
foo:
2
in r24,41-32
3
ldi r25,lo8(0)
4
ldi r18,6
5
1: lsr r25
6
ror r24
7
dec r18
8
brne 1b
9
andi r24,lo8(1)
10
ret
Frage:
Wie musst du die C-Quelle hinschreiben, um optimalen Code zu bekommen?
Du kannst rumprobieren oder in die Compilerquellen schauen, aber a
priori ist die Frage ohne Kenntnis der Arbeitsweise des verwendeten
Compilers nicht beantwortbar.
@ Johann L. (gjlayde) Benutzerseite
>Jeder der sich etwas mit AVR auskennt würde folgenden "optimalen" Code>hinschreiben:>gcc 4.3.2 mach sowohl bei Optimierung auf Codegröße als auch bei>Optimierung auf Geschwindigkeit (-O2 und -O3) daraus:>foo:> in r24,41-32> ldi r25,lo8(0)> ldi r18,6>1: lsr r25> ror r24> dec r18> brne 1b> andi r24,lo8(1)> ret>Frage:>Wie musst du die C-Quelle hinschreiben, um optimalen Code zu bekommen?
Falsche Frage. Die Frage lautet richtig:
Wie lange muss der Compiler bauer geprügelt werden, damit solcher Unsinn
nicht wieder vorkommt? Die Laufzeitberechnung einer Konstanten (1<<PD6)
ist schlicht eine Frechheit! So dumm kann ein Compiler heutzutage doch
gar nicht sein.
MFG
Falk
P S Kann es sein, dass ader AVR GCC in letzter Zeit eher kaputtoptimiert
wird? In fast jeder neuen Release wird der Code grösser und es kommen
Fehler hoch, die vorher nicht da waren.
Falk Brunner wrote:
> Wie lange muss der Compiler bauer geprügelt werden, damit solcher Unsinn> nicht wieder vorkommt?
Es ist kein Unsinn. Es ist korrekter Code.
> Die Laufzeitberechnung einer Konstanten (1<<PD6)> ist schlicht eine Frechheit! So dumm kann ein Compiler heutzutage doch> gar nicht sein.
Ich sag mal so; der Compiler ist nicht dumm, er ist überschlau.
> P S Kann es sein, dass der AVR GCC in letzter Zeit eher kaputtoptimiert> wird? In fast jeder neuen Release wird der Code grösser und es kommen> Fehler hoch, die vorher nicht da waren.
Die maschinenunabhängigen Optimierungen zielen vor allem auf 32-Bitter,
und die maschinenabhängigen GCC-Teile der kleinen µC müssen das dann
verdauen.
Ich selbst verwende daher immer noch gcc 3.4.6, weil der 4.x für AVR
rund 10% ineffizienteren Code macht quer durch meine Projekte.
Zu den Fehlern: Bei einer Software wie GCC (weit über 4.000.000 Zeilen
Quelle in über 15000 Dateien) -- dabei sind libs (libc, libm, ...) und
binutils (Assembler, Linker) nicht mitgezählt -- kommt es bei Änderungen
natürlich zu Fehlern oder zu Änderungen im erzeugten Code, die für
normalsterbliche C-Progger nicht nachvollziehbar sind.
In der Testsuite fallen solche Klopper nicht auf, weil der Code ja
compilerbar ist, und selbst wenn es Laufzeittests dafür gäbe, würde es
nicht auffallen, da er korrekt übersetzt wird.
Zudem kann ein Compilerentwickler nicht für alle Eingaben (C, C++, Java,
Ada, ...) und alle zig Targets (AVR, AVR32, ARM, Alpha, ...) übersehen,
welche Änderung wann wo bei welcher Quelle wie wirkt.
Konkret im vorliegenden Fall (GCC 4.x) wird folgende Sequenz an den
maschinenabhängigen Teil von GCC gereicht:
1
x1 = (u8) * ((u8 volatile*) &SFR)
2
x2 = (u16) x1
3
x3 = (u16) x2 >> 6
4
x4 = (u8) ((u8) x3)) & 1
5
return x4
Für 32-Bit Kerne, die in einer Instruktion shiften können, ist das easy
und guter Code, aber für AVR wird's eben grauslig, und im Backend
sammelt man sowas exterm schwer bis garnicht wieder ein...
@ Johann L. (gjlayde) Benutzerseite
>Ich sag mal so; der Compiler ist nicht dumm, er ist überschlau.
Was praktisch von Dummheit nicht zu unterscheiden ist.
>Zudem kann ein Compilerentwickler nicht für alle Eingaben (C, C++, Java,>Ada, ...) und alle zig Targets (AVR, AVR32, ARM, Alpha, ...) übersehen,>welche Änderung wann wo bei welcher Quelle wie wirkt.
Schon klar.
>Für 32-Bit Kerne, die in einer Instruktion shiften können, ist das easy>und guter Code,
Aber eine KONSTANTE ist und bleibt ein KONSTANTE! Auch auch einem
schnellen 32 Bit Shifter! Die direkte "unoptimierte" Lösung ist
gleichzeitig auch die beste, egal auf welcher Plattform. Register
lesen, UND Verknüpfung, fertig.
K I S S!
> aber für AVR wird's eben grauslig, und im Backend>sammelt man sowas exterm schwer bis garnicht wieder ein...
Erklärung richig, nütz aber praktisch nichts. Was kommt denn raus bei
Optimierung -Os? Die verwendet ich meistens. Ist nicht -O2 und -O3
sowieso nach allgemeinem Veratändnis ungünstig für den AVR? Also
sinnvoll nur -O1 oder -Os?
MFG
Falk
Falk Brunner wrote:
> Aber eine KONSTANTE ist und bleibt ein KONSTANTE! Auch auch einem> schnellen 32 Bit Shifter! Die direkte "unoptimierte" Lösung ist> gleichzeitig auch die beste, egal auf welcher Plattform. Register> lesen, UND Verknüpfung, fertig.
Nix fertig. Danach steht ein bedingter Sprungbefehl an, alternativ die
bedingte Ausführung des Folgebefehls. Bedingte Auführung (predication)
beherrschen nur recht wenige Architekturen, vor den mir bekannten sind
das vor allem IA64 und ARM, sehr stark eingeschränkt auch AVR.
Sprungbefehle wiederum sind auf den für die GCC Optimierung vorrangigen
High-Performance Architekturen sehr teuer. Vor allem wenn sie schlecht
vorhersagbar sind. Folglich besteht ein Trend bei Compilern, Sprünge so
weit wie möglich zu vermeiden.
Die hier zuschlagende "Optimierung" ist offenkundig generischer Natur,
also im von der Zielarchitektur unabhängigen Bereich angesiedelt. Viele
solche Optimierungen lassen sich selektiv aus- und einschalten. Aber
leider wurde eine solche Option manchmal vergessen und da sollte man
jedenfalls entsprechend nachbessern.
Es wäre mithin der Job des Programmierers der AVR-Zielarchitektur, für
AVR sinnlose Optimierungsansätze von vorneherein abzuschalten. Ich weiss
allerdings nicht, inwieweit das Framework vom GCC das überhaupt möglich
macht, ohne in den sensibleren maschinenunabhängigen Teil einzugreifen.
Ja, es scheint so, daß die GCC-Entwickler der allgemeinen 32Bit-Hype
verfallen sind und den AVR nur noch stiefmütterlich behandeln.
Also alle auf zur 128Bit-Hype, 8Bit war ja schon bei den Neandertalern
veraltet.
Jörg wird gleich schreiben, mach nen Bugreport oder schreib nen Patch.
Aber Bugreports, die nur die Optimierung betreffen, haben schlechte
Chancen, bearbeitet zu werden.
Und nen Patch zu schreiben, ist nur für einen kleinen Kreis der
Eingeweihten möglich. Der gemeine C-Programmierer steht davor, wie die
Kuh vorm neuen Tor.
Vielleicht hat jemand nen Link zu nem verständlichen Tutorial über
Aufzucht und Hege eines Patch. Also wie schreibt man nen Patch und wie
fügt man ihn in den WINAVR ein.
Oder gibt es ein Patch-Lehrbuch, wie es ja auch ein C-Lehrbuch gibt.
Aber warscheinlich ist das nur für jemanden verständlich, der schonmal
nen Compiler selber gebaut hat.
Peter
Peter Dannegger wrote:
> Ja, es scheint so, daß die GCC-Entwickler der allgemeinen 32Bit-Hype> verfallen sind und den AVR nur noch stiefmütterlich behandeln.
Das war noch nie anders. GCC war von Anfang an ein Compiler für
Unix-Workstations und für 32bit Systeme, später dann die Grundlage des
GNU/Linux Systems. Alles anderen Verwendungen sind ein Nebeneffekt. AVR
ist m.W. die einzige Portierung von GCC für ein 8bit System, jedenfalls
die einzige die es in den offziellen Code geschafft hat.
Peter Dannegger wrote:
> Aber Bugreports, die nur die Optimierung betreffen, haben schlechte> Chancen, bearbeitet zu werden.
Bei fehlender Optimierungmöglichkeit ja, sowas kann jahrelang liegen
bleiben. Hier aber ist das u.U. anders. Wenn der Code schweinemässig
schlechter ist als in Vorgängerversionen, dann ist das ein regression
bug und da sind die Jungs und Mädels etwas sensibler.
Falk Brunner wrote:
> Aber eine KONSTANTE ist und bleibt ein KONSTANTE! Auch auch einem> schnellen 32 Bit Shifter! Die direkte "unoptimierte" Lösung ist> gleichzeitig auch die beste, egal auf welcher Plattform. Register> lesen, UND Verknüpfung, fertig.
Nö, wenn man einfach schieben kann, dann ist die Lösung gut.
> Was kommt denn raus bei Optimierung -Os?
Wie gesagt, -Os, -O2 und -O3 liefern gleiches ab, selbst wenn die für
4.x empfohlenen Schalter
-fno-inline-small-functions
-fno-split-wide-types
-fno-tree-scev-cprop
aktiv sind.
-fno-thread-jumps
-fno-if-conversion
-fno-if-conversion2
sind zwecklos, und die beiden letzten will man auch nicht wirklich
setzen.
A. K. wrote:
> Bedingte Auführung (predication)...
bietet AVR nicht (nicht im Sinne von GCC)
> Die hier zuschlagende "Optimierung" ist offenkundig generischer Natur,> also im von der Zielarchitektur unabhängigen Bereich angesiedelt.
Das Problem ist weit "verschmiert" über die rund 100
maschinenunabhängigen SSA-Passes. Irgendwann ist das, was im if-Block
steht, tot. Und dann fliegt es eben in die Tonne...
> Viele solche Optimierungen lassen sich selektiv aus- und einschalten.
Direkt die Wumme auspacken und Optionen abschalten schüttet manchmal das
Kind mit dem Bade aus. SSA endet mit
1
foo()
2
{
3
unsignedcharD.1348;
4
5
<bb2>:
6
D.1348={v}*41B;
7
return((int)D.1348&64)!=0;
8
}
und diese Bit-Extraktion wird erst von AVR-Teil in den >>6 &1 umgesetzt.
Der aktuelle WINAVR hat aber auch einige Vorteile:
Er hat endlich damit aufgehört, char Returnwerte sinnlos nach int zu
erweitern (3 Befehle) und man kann das unerwünschte Inlining von nicht
static Funktionen abschalten.
Und das Switch/Case ist auch nicht mehr so int-lastig. Er optmiert sogar
Cases mit gleichen Codesequenzen am Ende. Man muß also nicht mehr auf
unleserliche If/Else-Monster ausweichen.
In der Summe bin ich damit oft bei fast 0 Codevergrößerung (bin
Funktions-Junki, mache gerne viele kleine char Funktionen, teile und
herrsche-Prinzip).
Peter
Peter Dannegger wrote:
> Mangels eines Patch kann man den GCC austricken, indem man mehr als ein> Bit setzt:
Deine Funktion tut aber was anderes.
> Ich habs bei meinem Encoder-Interrupt so gemacht, der Zweck heilig die> Mittel.
Ich setze wie gesagt 3.4.6 ein und schaue nur hin und wieder auf die 4.x
und was die so treibt mit meinem Code. Zugegeben, er ist so
hingeschrieben, daß er für gcc 3.x gut verdaulich ist, vielleicht gibt's
auch deshalb die inakzeptablen +10% bei 4.x.
Das Beispiel war konstruiert und kommt nicht aus der Praxis.
Dort ist für Byte- und Tick-Fuchser folgendes machbar:
Johann L. wrote:
> return ((int) D.1348 & 64) != 0;> und diese Bit-Extraktion wird erst von AVR-Teil in den >>6 &1 umgesetzt.
Nein. Steckt direkt in der tree=>rtl Umsetzung.
Siehe gcc/expr.c:do_store_flag().
If this is an equality or inequality test of a single bit, we can
do this by shifting the bit being tested to the low-order bit and
masking the result with the constant 1. If the condition was EQ,
we xor it with 1. This does not require an scc insn and is faster
than an scc insn even if we have it.
Wenn man das auskommentiert oder mit einem Flag bewaffnet, dürfte Ruhe
sein. Man hätte da ruhig mal nach den Kosten der beteiligten Operationen
fragen können, irgendwo gibt's sowas doch.
Interessanterweise steht das in 3.4.6 auch schon drin.
A. K. wrote:
> Johann L. wrote:>>> return ((int) D.1348 & 64) != 0;>> und diese Bit-Extraktion wird erst von AVR-Teil in den >>6 &1 umgesetzt.>> Nein. Steckt direkt in der tree=>rtl Umsetzung.
Kann sein, daß er nur dorthin kommt, weil ihm Pattern fehlen? Im Backend
seh ich zB keine insn zu "extv" over "extz", möglicherweise entscheidet
sich weils dafür keinen expander/insn gibt für den shift, weil das
Standard-Pattern sind. Man könnte zB zu was wie das RTL untern ausgeben.
> Siehe gcc/expr.c:do_store_flag().>> If this is an equality or inequality test of a single bit, we can> do this by shifting the bit being tested to the low-order bit and> masking the result with the constant 1. If the condition was EQ,> we xor it with 1. This does not require an scc insn and is faster> than an scc insn even if we have it.>> Wenn man das auskommentiert oder mit einem Flag bewaffnet, dürfte Ruhe> sein. Man hätte da ruhig mal nach den Kosten der beteiligten Operationen> fragen können, irgendwo gibt's sowas doch.>> Interessanterweise steht das in 3.4.6 auch schon drin.
Der kannte andere Pattern, womöglich käme man dem mit combiner-Pattern
bei, aber kann ich von hier nicht beurteilen, hab keine build-Umgebung
hier.
So was (schematisch):
Stefan Ernst wrote:
> Nur zur Info, so wird es optimal übersetzt
Interessanter ist der Fall, wo es mies übersetzt wird, weil man daran
sieht, wo in gcc was gemacht werden muss/sollte.
Johann L. wrote:
> Kann sein, daß er nur dorthin kommt, weil ihm Pattern fehlen?
Glaube ich nicht. Patterns greifen m.E. erst wenn der Code schon in RTL
umgesetzt ist. Dieser Schmutzfuss sitzt aber exakt da, wo aus dem
ursprünglichen Baum erst das RTL erzeugt wird.
Ich hatte schon früher mal danach gesucht und meine mich erinnern zu
können, dass in Vorversionen der ifcombine pass noch nicht existierte,
und erst damit wird aus dem
y=0;if(x&64)y=1
das kritische
y=(x&64)!=0
A. K. wrote:
> Johann L. wrote:>>> Kann sein, daß er nur dorthin kommt, weil ihm Pattern fehlen?>> Glaube ich nicht. Patterns greifen m.E. erst wenn der Code schon in RTL> umgesetzt ist. Dieser Schmutzfuss sitzt aber exakt da, wo aus dem> ursprünglichen Baum erst das RTL erzeugt wird.
An einigen Stellen schaut gcc nach, was für Pattern es gibt. Einen
gewissen Satz von Standardpattern muss man zur Verfügung stellen, aber
nicht alle Pattern mit Standardnamen muss man schreiben. Wenn die
Maschine etwas nicht kann oder man sich nicht den Wolf machen will, ist
es uU besser, die Beschreibung wegzulassen.
ZB in ./gcc/expmed.c
http://gcc.gnu.org/viewcvs/trunk/gcc/expmed.c?revision=141960&view=markup
Suchen nach
CODE_FOR_insv
CODE_FOR_extv
CODE_FOR_extzv
Da geht's nämlich gerade um Bitfeld-Manipulation, was in avr.md nicht
beschrieben ist. Ich weiss auch nicht, ob man bei den Pattern FAILen
darf.
expmed ist nur ein Beispiel, das ich recht beliebig angeclickt hab.
Die Defines kommen AKAIR aus optabs.h, welches zur Buildzeit automatisch
generiert wird.
Johann L. wrote:
> Interessanter ist der Fall, wo es mies übersetzt wird, weil man daran> sieht, wo in gcc was gemacht werden muss/sollte.
Zugegeben, ich kenne mich in den gcc-Innereien nicht aus, aber ich hatte
einfach gedacht, dass das unterschiedliche Verhalten bezüglich ">0" bei
?-Operator und if-Konstrukt auch ein Hinweis sein könnte, wo das Problem
zu suchen sein könnte. Schließlich produzieren 3 von 4 Varianten
identischen Code, und nur eine den Optimalen:
if ohne >0 : Bit-Geschiebe
if mit >0 : Bit-Geschiebe
?-Op ohne >0: Bit-Geschiebe
?-Op mit >0 : Optimal
Das ist allerdings ein Wettrennen rückwärts, denn wer weiss wie lange es
dauert, bis GCC dein redundantes Gedöns als solches erkennt und erneut
den problematischen Zwischencode erzeugt.
A. K. wrote:
> Das ist allerdings ein Wettrennen rückwärts, denn wer weiss wie lange es> dauert, bis GCC dein redundantes Gedöns als solches erkennt und erneut> den problematischen Zwischencode erzeugt.
Habe ich vielleicht irgendwo geschrieben "spart euch die Suche nach dem
Problem, man kann es ja auch so schreiben"???
Ich Dummerchen dachte einfach, dass diese Info die Suche erleichtern
könnte. Wenn es nicht so ist, dann ignoriert es doch einfach.
Sorry, war nicht bös gemeint.
Mir ist mittlerweile leidlich klar was da abläuft. Der ifcombine pass
erkennt bestimmte Codemuster und baut sie so um, dass daraus der
problematische Code entsteht, der dann ineffizient umgesetzt wird.
Deine Variationen spielen mit der Erkennung der Codemuster in diesem
ifcombine, wobei das aber völlig korrekt handelt und dessen Ergebnis
zunächst auch unproblematisch ist. Andererseits bin nicht sicher, ob der
ifcombine pass dem AVR wirklich gut tut, angesichts billiger
Sprünge/Skips und fehlender set-conditional Operationen. Könnte
interessant sein, den mal komplett abzuschalten.
ifcombine ist nicht unbedingt der wunde Punkt, weil es auch um Ausdrücke
geht, die kein if oder if-else sind wie folgendes nicht ganz so krasse
Beispiel:
1
struct
2
{
3
unsigned:6;
4
unsignedb:1;
5
unsigned:1;
6
}s;
7
8
voidfoo(uint8_ti)
9
{
10
s.b=i;
11
}
woraus wird
1
andi r24,lo8(1)
2
swap r24
3
lsl r24
4
lsl r24
5
andi r24,lo8(-64)
6
lds r25,s
7
andi r25,lo8(-65)
8
or r25,r24
9
sts s,r25
10
ret
Die Arithmetik braucht 7 Befehle, es ginge in 3 und mit 1 Register
anstatt mit 2, zudem wird r24 verändert, was nicht sein müsste
(schlecht, falls i noch gebraucht würde).
Daß der Code nicht so prockelnd ist dürfte nicht an ifcombine liegen,
sondern weil nicht beschrieben ist, wie 1-Bit breite Bitfelder
extrahiert/gesetzt werden können, was ja recht häufig vorkommt.
Während es im Backend praktisch unmöglich ist, Sprungsequenzen in
lineare Arithmetik zu wandeln, ist es vergleichsweise einfach,
Arithmetik in ne Sprungsequenz zu transformieren.
Johann L. wrote:
> Ich selbst verwende daher immer noch gcc 3.4.6, weil der 4.x für AVR> rund 10% ineffizienteren Code macht quer durch meine Projekte.
Etwas OT:
Hast du nur den Compiler gewechselt oder verwendest du eine komplette
alte WinAVR-Distribution, die diesen Compiler enthält? Würde gerne
wissen, ob man den Compiler alleine tauschen kann. Fürchte eher nicht,
aber habe nicht genügend Durchblick um das zu beurteilen.
Peter Dannegger wrote:
> Jörg wird gleich schreiben, mach nen Bugreport oder schreib nen Patch.grins :-))
900ss D. wrote:
> Etwas OT:> Hast du nur den Compiler gewechselt oder verwendest du eine komplette> alte WinAVR-Distribution, die diesen Compiler enthält? Würde gerne> wissen, ob man den Compiler alleine tauschen kann. Fürchte eher nicht,
Die Abhängigkeiten zwischen gcc/binutils/libc sind einfach zu groß. Ich
habe mehrer Toolchains parallel installiert und kann über ein
makefile-flas alles umschalten. Evtl nen eigenen Fred aufmachen und
(Jörg) fragen.
Etwas Platz kann man schon sparen, wenn man selbst geschriebene
EE-Routinen verwendet wie Peter, dürften rund 100 Bytes sein.
A. K. wrote:
> Ich hatte schon früher mal danach gesucht und meine mich erinnern zu> können, dass in Vorversionen der ifcombine pass noch nicht existierte,> und erst damit wird aus dem> y=0;if(x&64)y=1> das kritische> y=(x&64)!=0
Das ist nicht kritisch, sondern sogar für Backends wie avr gut: Aus
Sicht eines Backends ist es wünschenswert, Operationen/Ausdrücke etc. zu
kanonisieren.
Gerade das Setzen/Löschen/Testen/Kopieren/Einfügen eines Bits kommt sehr
oft in embedded-Programmen vor und kann auf 1001 Art in C ausgetextet
werden: als if-else, als condtional, als Masken-Grab, mit Shifts, etc.
Das auf eine Darstellung abzubilden ist/wäre ein großer Fortschritt
und die alte ifconversion (./gcc/ifcvt.c) war nicht seht gut darin. Wenn
das Target Ausdrücke wie (x&64)!=0 besser über nen Sprung macht, kann es
doch dahin expandieren. Oder? Ich würd eher mal schauen, wo gen_extzv
gebraucht wird.
Johann L. wrote:
> Das ist nicht kritisch, sondern sogar für Backends wie avr gut: Aus> Sicht eines Backends ist es wünschenswert, Operationen/Ausdrücke etc. zu> kanonisieren.
Sachte - "kritisch" ist es ja nur deshalb, weil der Code weiter hinten
dann so einen Müll draus macht. Nicht anders war das gemeint.
> Gerade das Setzen/Löschen/Testen/Kopieren/Einfügen eines Bits kommt sehr> oft in embedded-Programmen vor und kann auf 1001 Art in C ausgetextet> werden: als if-else, als condtional, als Masken-Grab, mit Shifts, etc.
Kann vorteilhaft sein, kann nachteilig sein. Generell scheint mir aber
die Strategie, Sprünge zugunsten von Rechenoperationen zu vermeiden,
beim AVR eher nachteilig zu sein, zumal das bischen predication was der
bietet dadurch möglicherweise eher verhindert als ermöglicht wird. Ich
fände es daher nicht uninteressant, das ifcombine mal abschaltbar zu
machen, um zu sehen was insgesamt dabei rauskommt.
> Das auf eine Darstellung abzubilden ist/wäre ein großer Fortschritt> und die alte ifconversion (./gcc/ifcvt.c) war nicht seht gut darin. Wenn> das Target Ausdrücke wie (x&64)!=0 besser über nen Sprung macht, kann es> doch dahin expandieren.
Aber klar doch. Wäre da nicht der Code in der tree->rtl expansion, der
m.E. verhindert, dass im AVR Backend dies überhaupt noch ankommt.
Der Kommentar deutet an, dass es sonst so vorhanden auf eine "scc"
Operation rausläuft (ich tippe dabei auf "set conditional" oder so,
gibt's ja in diversen Architekturen wie x86) und wenn es die nicht gibt,
greift bestimmt eine entsprechende Regel die das auf Grundoperationen
umbaut.
Und da wäre ich nun kein winziges bischen überrascht, wenn ein solcher
Umbau von "scc" zu Grundoperationen den Umbau von ifcombine exakt wieder
rückgängig macht. ;-)
Zu deiner These, dass fehlende bitfeld extracts als instruction
templates damit was zu tun haben könnten: Der für den Umbau zu shift
verantwortliche Code ist, neben der oben schon angeführten Erkennung des
Operationsmusters, in fold-const.c:fold_single_bit_test() zu finden. Und
darin kann ich keine Abfrage auf Existenz solcher Operationen entdecken.
Die Funktion geht ohne Rücksicht auf's target schlicht nach Schema vor.
Ok, weiter im Text.
Die schon erwähnte Funktion expr.c:do_store_flag(), die für die
tree->rtl expansion von Vergleichen zu 0/1 Werten zuständig ist,
interessiert sich nach dem hier greifenden Spezialcode zur Erkennung
solcher Einzelbit-Tests tatsächlich dafür, ob die Zielmaschine was mit
"set conditional" anfangen kann.
Und wenn dem nicht so ist, wird aus
y = (x & 64) != 0;
tatsächlich wieder
y = 0;
if ((x&64) == 0) goto temp;
y = 1;
temp:
wie ich vorhin schon vermutet hatte.
Und für solche Sequenzen existieren im AVR Backend eigens einige
templates, die daraus conditional skip instructions erzeugen.
Ohne ifcombine wäre also in diesem Fall alles den richtigen Weg
gegangen. Weglassen ist natürlich trotzdem nicht der beste Ansatz, denn
bevor ifcombine hinzukam dürfte der Quellcode
y = (x & 64) != 0
auch schon den bekannten Mist produziert haben.
Weshalb mancher Programmierer vielleicht erst auf die Idee gekommen war,
das zur Erzielung besseren Codes durch
y = 0; if (x & 64) y = 1;
zu ersetzen. Und durch die neue hinzugekommende Optimierung des
Compilers wieder eingeholt wurde, die ihn nun durchschaut hat. ;-)
Was ich mich nun frage: Wie kriegt man das so in die GCC bugreports
rein, das eine gewisse Aussicht auf Erfolg im Raum steht?
Der korrekte Ansatz bestünde darin, den Spezialcode für Einzelbittest
von den Kosten der Shift-Operation abhängig zu machen. Aber da muss
erstens jemand ran, der sich dabei auskennt, zweitens ist das ein seit
Äonen stabiler Code der jede Zielarchitektur betrifft, weshalb ich
Zweifel habe ob sich da jemand ohne Not (d.h. bloss wegen AVR) rantraut.
A. K. wrote:
> Zu deiner These, dass fehlende bitfeld extracts als instruction> templates damit was zu tun haben könnten: Der für den Umbau zu shift> verantwortliche Code ist, neben der oben schon angeführten Erkennung des> Operationsmusters, in fold-const.c:fold_single_bit_test() zu finden. Und> darin kann ich keine Abfrage auf Existenz solcher Operationen entdecken.
Ich auch nicht der Ort, weil fold_single_bit_test() auf tree-Ebene
operiert.
> Die schon erwähnte Funktion expr.c:do_store_flag(), die für die> tree->rtl expansion von Vergleichen zu 0/1 Werten zuständig ist,> interessiert sich nach dem hier greifenden Spezialcode zur Erkennung> solchen Einzelbit-Tests tatsächlich dafür, ob die Zielmaschine was mit> "set conditional" anfangen kann.
Aber doch erst nach
1
/* If this is an equality or inequality test of a single bit, we can
2
do this by shifting the bit being tested to the low-order bit and
3
masking the result with the constant 1. If the condition was EQ,
4
we xor it with 1. This does not require an scc insn and is faster
5
than an scc insn even if we have it.
6
7
The code to make this transformation was moved into fold_single_bit_test,
8
so we just call into the folder and expand its result. */
Und ./gcc/expr.h:expand_expr() ist hochgradig von der
Existenz/Nichtexistenz von Standard-Pattern abhängig.
Erst unterhalb dieser Funktion (hier Makro -> expand_expr_real()) wird
tree nach RTL entwickelt.
Johann L. wrote:
> Aber doch erst nach
Ja. Sag ich doch. Dieser Test greift aber nur, weil ifcombine den für
diesen Test völlig unverdächtigen
y = 0; if (x & 64) y = 1;
zu
y = (x & 64) != 0
umgebaut hat.
Ich hatte nun gedanklich durchgespielt, was passieren würde wenn dieser
Test nicht greift. Und es folglich dahinter weiter geht.
> Und ./gcc/expr.h:expand_expr() ist hochgradig von der> Existenz/Nichtexistenz von Standard-Pattern abhängig.
Ja, aber das nützt nichts mehr. Denn sobald &/!= zu >>/& umgebaut ist,
ist das Kind erst einmal im Brunnen. Und liesse sich nur durch ein
entspreched komplexes Pattern wieder rausfischen.
Johann L. wrote:
> Ich auch nicht der Ort, weil fold_single_bit_test() auf tree-Ebene> operiert.
Ok, stimmt, dann ist das der falsche Ort. Was es leider deutlich
schwieriger macht, eine saubere Lösung dafür zu finden.
Denn es hängt ja nun von den Kosten einer Shift-Operation ab, ob das
wirklich sinnvoll ist.
Und im tree code gibt es zwar auch Kostenrechnungen, aber was davon zu
halten ist weiss man spätestens seit der Diskussion um
-fno-inline-small-functions (das betrifft auch nicht nur AVR, ARMs geht
es bei der Kostenrechnung rund ums Inlining auch nicht unbedingt
besser).
A. K. wrote:
> Ok, stimmt, dann ist das der falsche Ort. Was es leider deutlich> schwieriger macht, eine saubere Lösung dafür zu finden.
Ich nehme mal an die die fold_single_bit_test() erzeugt den shift und
nicht der expand_expr(). Man könnte alternativ nen zero_extract erzeugen
und dessen RTX_COSTS mit denen des (and (lshiftrt (x) (n)) (1))
vergleichen.
> Denn es hängt ja nun von den Kosten einer Shift-Operation ab, ob das> wirklich sinnvoll ist.
Nur an den Kosten sieht man das ja nicht, weil x >> 6 teurer ist als was
komplexeres wie (x >> 6) & 1.
> Und im tree code gibt es zwar auch Kostenrechnungen, aber was davon zu> halten ist weiss man spätestens seit der Diskussion um> -fno-inline-small-functions (das betrifft auch nicht nur AVR, ARMs geht> es bei der Kostenrechnung rund ums Inlining auch nicht unbedingt> besser).
An der Stelle hat mal eben nur RTL, und dessen Kosten anzugeben ist
recht esoterisch...
Als Lösung scheidet eine "extzv" wohl aus, weil man die komplett
unterstützen müsste (also auch für Feldbreiten > 1) und ich nicht weiß,
ob HAVE_extzv das Ergebis überhaupt beeinflusst.
Was funktionieren könnte und das Middleend unberührt lässt wäre wie
gesagt combiner-Pattern auf den shift. Das ist zwar nicht der hype, aber
die Änderungen sind recht lokal. Dazu kann man combine.c patchen und
sich anschauen, was der Combiner so erzeugen möchte und wenn was nicht
klappt weil das Backend ne Isns nicht bietet, die das Target kann, dann
macht man diese Insn dazu und Ruhe ist.
Allerdings kann ich die Effekte nicht abschätzen, ob das schlechten Code
macht, weil ja in Abfragen wie SBIC, SBRC auch (implizit wohl) solche
Bitextraktionen stecken.
== Edit ==
Un laut Doku darf die extzv FAILen :-)))
http://gcc.gnu.org/onlinedocs/gccint/Expander-Definitions.html#Expander-Definitions
Johann L. wrote:
> Ich nehme mal an die die fold_single_bit_test() erzeugt den shift und> nicht der expand_expr().
Das kannst du so oder so sehen.
expand_expr() (=expand_expr_real) ruft expand_expr_real_1() auf, das
ruft do_store_flag() auf und das wiederum ruft fold_single_bit_test()
auf.
> An der Stelle hat mal eben nur RTL, und dessen Kosten anzugeben ist> recht esoterisch...
Ist das nicht zufällig genau andersrum? avr_rtx_costs() klingt eher nach
RTL Kostenrechnung. Die müsste man eigentlich einigermassen hinkriegen.
Das Inlining dürfte jedoch noch in der Tree-Phase greifen, und da ist
das wirklich weit esoterischer.
A. K. wrote:
> Johann L. wrote:>> An der Stelle hat mal eben nur RTL, und dessen Kosten anzugeben ist>> recht esoterisch...>> Ist das nicht zufällig genau andersrum? avr_rtx_costs() klingt eher nach> RTL Kostenrechnung. Die müsste man eigentlich einigermassen hinkriegen.
Ja, es ist Kostenrechnung. Mit "esoterisch" meinte ich, daß RTL-Kosten
i.d.R wenig mit asm-Kosten (egal wie die Bewertung ist) zu tun haben. Um
die Kosten treffgenau geben zu können, reicht es meist nicht aus, auf
ein RTX zu schauen. Man müsste auch wissen, was mit dem Wert geschieht,
d.h. wie er verwendet wird.
Der >> ist wie gesagt nichts schlimmes; blöd ist, daß er vom &1 getrennt
auftaucht. Die Kosten von >> und &1 ist ja nicht COST(>>) + COST(&1).
> Das Inlining dürfte jedoch noch in der Tree-Phase greifen, und da ist> das wirklich weit esoterischer.
Wie gesagt non-strict RTL hat wenig mit dem Code zu tun, der hinten
rauskommt...
Was gcc bräuchte wäre die Möglichkeit, spekulativ zu übersetzen, d.h.
mehrere Pfade auszuprobieren und am Ende auf BasicBlock-, Funktions-
oder Modulebene die beste (im Sinne der gewünschten Bewertung wie Os,
O2) Lösung zu wählen.
Für den vorliegenden Fall einfach mal nen "extzv"-Expander schreiben und
schauen, ab er für das Progrämmle durchrauscht (printf, oder abort oder
so). Falls ja, ist das die Lösung.
und mit den neuen Pattern folgende. Für 4.3.2 dürfte es änlich werden.
Leider hab ich nicht die Möglichkeit das zu testen. Ich weiß auch nicht
ob das an ner anderen Stelle schlechteren Code gibt, weil combine
Pattern anders zusamensetzen darf.