Bastelboy schrieb:> Wie kann ich den (Attiny) GCC dazu bringen den ASM-Befehl SWAP zu> nehmen?
Solche Fragen stellen sich nicht wenn man gleich Assembler nimmt.
Ist unter dem Strich auch einfacher mit viel weniger Schreibaufwand.
Hast Du denn schon mal probiert, was bei dem C-Code ganz oben rauskommt?
Normalerweise ist der Compiler so schlau, dass er den SWAP-Befehl nutzt,
wenn es möglich ist.
Bastelboy schrieb:> Swap niblles würde ich in C so schreiben:
Dann machs doch.
Erst wenn Du diesen Code zich tausende male / s brauchst, lohnt sich
über Optimieren vielleicht nachzudenken.
Bastelboy schrieb:> Swap niblles würde ich in C so schreiben:> Bla = ((Bla >> 4) and 0x0F) | (Bla << 4) and 0xF0);> Wie kann ich den (Attiny) GCC dazu bringen den ASM-Befehl SWAP zu
Indem du die beiden "and" durch "&" ersetzt und dafür sorgst, dass der
GCC mindestens die Version 4.4 hat.
klausr schrieb:> Gar nicht so dumm, der gcc ;-)
Findest du?
;implizit mindestens ein "rcall" ;3
> swap r24 ;1> ret ;4
;-
;8
->unnützer Overhead mindestens 700% (!!). Und dabei ist noch nichtmal
der Overhead eingerechnet, den der Compiler betreibt, um seine
Funktionsparameter immer wieder nach r24 (und folgende) zu bringen bzw.
diese zu nullen.
Garnicht so dumm wäre er, wenn er selber rausbekommen hätte, daß der
Callframe hier so nützlich ist wie ein Loch im Kopf. Aber nein, er
fordert vom Programmierer, daß DER weiß, daß er noch ein "inline" vor
die Funktion zu schreiben hat, wenn die Sache nicht effizienzmäßig im
Desaster enden soll.
c-hater schrieb:> Aber nein, er> fordert vom Programmierer, daß DER weiß, daß er noch ein "inline" vor> die Funktion zu schreiben hat, wenn die Sache nicht effizienzmäßig im> Desaster enden soll.
Dein Hass in Ehren, aber wärs nicht besser du bliebest bei der Wahrheit?
Inlining macht GCC sehr wohl selbtstätig, und nicht zu knapp.
c-hater schrieb:> klausr schrieb:>>> Gar nicht so dumm, der gcc ;-)>> Findest du?>> ;implizit mindestens ein "rcall" ;3>> swap r24 ;1>> ret ;4> ;-> ;8>> ->unnützer Overhead mindestens 700% (!!). Und dabei ist noch nichtmal> der Overhead eingerechnet, den der Compiler betreibt, um seine> Funktionsparameter immer wieder nach r24 (und folgende) zu bringen bzw.> diese zu nullen.>> Garnicht so dumm wäre er, wenn er selber rausbekommen hätte, daß der> Callframe hier so nützlich ist wie ein Loch im Kopf. Aber nein, er> fordert vom Programmierer, daß DER weiß, daß er noch ein "inline" vor> die Funktion zu schreiben hat, wenn die Sache nicht effizienzmäßig im> Desaster enden soll.
c-hater, ich fürchte du hast das alles nicht wirklich verstanden...
Du könntest ja mal versuchen, die Funktion tatsächlich zu verwenden,
auch ohne 'inline' davor. Und du würdest erkennen dass der gcc das alles
so macht wie du es gerne hättest.
>->unnützer Overhead mindestens 700% (!!)
Also wenn man schon eine optimierte Nibble-Swap Operation haben will,
dann packt man das ganze nicht in eine Overhead generierende Funktion,
sondern macht sich gleich ein Makro!
@c-hater:
Mit einem dezenten "static" wäre die Funktion für andere Compile-Units
(klingt doch irgendwie nach TP) nicht sichtbar und müsste deshalb auch
nicht als eigenständige "call unit" vorhanden sein.
Irgendwie hab ich eh den Eindruck, daß manche Probleme mancher Sprachen
auf dem expliziten Nichtwissen der Problemhaber basieren!
c-hater schrieb:> wenn die Sache nicht effizienzmäßig im> Desaster enden soll.
C ist schon sehr effizient, wenn man die Entwicklungszeit einer
Applikation als Maßstab nimmt, was ja selbstverständlich sein sollte.
Ineffizient ist dagegen, wenn man an Sachen unnütz rumoptimiert, die
vielleicht 0,01% der gesamten CPU-Zeit benötigen. Das ist pure
Zeitverschwendung, also Bestehlen des Auftraggebers.
Deine 700% kannst Du also getrost in der Pfeife rauchen.
wird vom GCC in folgenden Assembler-Code übersetzt:
1
main:
2
ldi r24,lo8(-1)
3
out 0x11,r24
4
.L2:
5
in r24,0x15
6
swap r24
7
out 0x12,r24
8
rjmp .L2
C-hater, wenn du das in Hand-Assembler auch nur 1 Taktzyklus pro
Schleifendurchlauf besser hinbekommst, melde dich bitte noch einmal.
Wenn nicht, halte dich mit deinen Kommentaren einfach mal etwas zurück
und lerne erst einmal, mit C und GCC umzugehen.
Yalu X. schrieb:> C-hater, wenn du das in Hand-Assembler auch nur 1 Taktzyklus pro> Schleifendurchlauf besser hinbekommst, melde dich bitte noch einmal.
Kein Problem:
in r24,0x15
swap r24
out 0x12,r24
in r24,0x15
swap r24
out 0x12,r24
in r24,0x15
swap r24
out 0x12,r24
in r24,0x15
swap r24
out 0x12,r24
in r24,0x15
swap r24
out 0x12,r24
in r24,0x15
swap r24
out 0x12,r24
...
Könnte mir aber denken, dass GCC mit -O2 oder -O3 statt -Os ansatzweise
auf ähnliche Gedanken verfällt.
A. K. schrieb:> Könnte mir aber denken, dass GCC mit -O2 oder -O3 statt -Os ansatzweise> auf ähnliche Gedanken verfällt.
Nein, für eine Endlosschleife nicht, denn irgendwann wird ja doch
ein „teurer“ Rücksprung gebraucht.
Eine abgezählte Schleife würde er aber in der Tat bei -O3 entrollen.
Moby schrieb:> Bastelboy schrieb:>> Wie kann ich den (Attiny) GCC dazu bringen den ASM-Befehl SWAP zu>> nehmen?>> Solche Fragen stellen sich nicht wenn man gleich Assembler nimmt.> Ist unter dem Strich auch einfacher mit viel weniger Schreibaufwand.
Wir haben das Jahr 2013.
c-hater schrieb:> klausr schrieb:>>> Gar nicht so dumm, der gcc ;-)>> Findest du?>> ;implizit mindestens ein "rcall" ;3>> swap r24 ;1>> ret ;4> ;-> ;8>> ->unnützer Overhead mindestens 700% (!!). Und dabei ist noch nichtmal> der Overhead eingerechnet, den der Compiler betreibt, um seine> Funktionsparameter immer wieder nach r24 (und folgende) zu bringen bzw.> diese zu nullen.
Wo, aus Projektsicht gesehen, entsteht eigentlich genau dieser Overhead?
A) Wird die Entwicklungszeit länger weil C statt ASM genutzt wird?
B) Wird eine Anwendung, die bei MCUs meist zu 90% aus sleep mode
besteht, dadurch langsamer?
C) Wird das Programm so viel größer, das ein anderer Mikrocontroller
genutzt werden muss?
Oder
D) Die Entwicklungszeit verkürzt sich gegenüber ASM
E) Der Code wird portierbar
F) Der Code wird wartbar
A-C) NEIN
D-F) JA
6:0 für C in kommerziellen oder sonstigen Projekten, bei denen
Entwicklungseffizienz eine Rolle spielt.
Jörg Wunsch schrieb:> A. K. schrieb:>> Könnte mir aber denken, dass GCC mit -O2 oder -O3 statt -Os ansatzweise>> auf ähnliche Gedanken verfällt.>> Nein, für eine Endlosschleife nicht, denn irgendwann wird ja doch> ein „teurer“ Rücksprung gebraucht.
Wenn man die Schleife wirklich teilweise unrollen will, kann ja im
C-Quellcode die Zeile
1
PORTD=swap(PORTC);
mehrmals hintereinander schreiben. Entsprechendes müsste der C-Hater
auch in Assembler machen, um mehrere Swaps pro Schleifendurchlauf
auszuführen.
Tim . schrieb:> Welche Kriterien sprechen genau dagegen?
Na wenn man nicht gerade auf Massenproduktion geht und jeder Cent zählt,
kann man zB auch kleine ARM's (wie die STM32) nehmen und sich daran
erfreuen dass man viel leichter viel mehr Rechen&Peripherie-Leistung
bekommt... Die viel schnellere Interrupt-Behandlung, die effizientere
Datenverarbeitung macht die besonders schön für zeitkritische Sachen.
Kindergärtner schrieb:> Tim . schrieb:>> Welche Kriterien sprechen genau dagegen?> Na wenn man nicht gerade auf Massenproduktion geht und jeder Cent zählt,> kann man zB auch kleine ARM's (wie die STM32) nehmen und sich daran> erfreuen dass man viel leichter viel mehr Rechen&Peripherie-Leistung> bekommt... Die viel schnellere Interrupt-Behandlung, die effizientere> Datenverarbeitung macht die besonders schön für zeitkritische Sachen.
Ja, ich finde die kleine ARMS auch toll. Wenn Du auf den Hobbybereich
kommst, spricht allerdings noch einiges dagegen:
- Fast keine DIP Bausteine verfügbar.
- ISP Hardware teurer/schwerer zu bekommen.
- Kostenlose Entwicklungsumgebungen sind nicht so gut wie bei AVR.
- Die Peripherie der ARM Prozessoren ist deutlich komplexer als bei AVR.
- Für die meisten Controllanwendungen benötigt man weder 32bit, noch 30
MIPS.
Tim . schrieb:> - Fast keine DIP Bausteine verfügbar.
stimmt leider.
> - ISP Hardware teurer/schwerer zu bekommen.
Geht, bei den STM32 Discoveries ist sie dabei/integriert.
> - Kostenlose Entwicklungsumgebungen sind nicht so gut wie bei AVR.
Der ARM-GCC & eclipse sind schon ziemlich gut.
> - Die Peripherie der ARM Prozessoren ist deutlich komplexer als bei AVR.
Und auch mächtiger...
> - Für die meisten Controllanwendungen benötigt man weder 32bit, noch 30> MIPS.
Na die Statistik möchte ich sehen :o) Man braucht auch kein C für die
meisten Anwendungen, benutzt man aber trotzdem, weil es einfacher ist.
Genauso kann man 32bit-CPU's nutzen weil man einfach mehr Rechenleistung
hat und nicht auf jeden CPU-Zyklus achten muss (aber natürlich kann,
wenn man effizient sein möchte).
Jungs, es ging um den Swap hier … Threads, ob nun Controllerarchitektur
A oder B besser oder schlechter ist, haben wir wirklich schon zur
Genüge, und die Argumente bleiben auch jedesmal die gleichen.
Hallo allerseits,
da habe ich ja was schönes losgetreten.
Anstelle von:
1
Bla=((Bla>>4)and0x0F)|((Bla<<4)and0xF0);
wollte ich eigentlich schreiben:
1
Bla=((Bla>>4)&0x0F)|((Bla<<4)&0xF0);
nur leider habe ich auf meinem neuen billig-Smartphone das
& Symbol nicht gefunden.
Mir ging es halt darum, wie man da ein bischen Assembler in den C-Code
moggeln kann, und wie man da den Assembler-Befehlen Werte übergeben und
zurückbekommen kann. Und wie man wissen kann, welche Register man
überhaupt verfummeln darf.
Peter Zz schrieb:> Mir ging es halt darum, wie man da ein bischen Assembler in den C-Code> moggeln kann
OK, ein paar Links dafür hast du ja auch bekommen. ;-)
Generell: der GCC-Inline-Assembler ist reichlich komplex. Er ist
ziemlich weit unten im Compiler angebunden. Dadurch ist er zwar
sehr mächtig, weil man insbesondere noch dem Compiler die volle
Freiheit überlassen kann, wie er die Daten zu den möglichen Orten
(Register, Stack) zusortieren kann, aber andererseits ist das dafür
notwendige constraining nicht gerade auf den ersten Blick mental
erfassbar (um es mal vorsichtig zu formulieren ;-).
Kindergärtner schrieb:> Und hier ein paar Feinheiten für ARM's, das ist wohl sonst kaum bis gar> nicht dokumentiert:
Das wäre es doch eigentlich mal Wert, hier irgendwo im Wiki erwähnt
zu werden, oder?
Die einzelnen Nibble im 1.Parameter entscheiden welches Bit aus dem 2.P.
wo in den 3.P. eingefügt wird.
SWAP -> 0x32107654
BitReverse -> 0x01234567
BitReverse lower 4 bits -> 0x76540123
Sonderwert F für "nicht ändern":
(Bit)Wert aus 3.P. nach 2.P. übernehmen -> 0xffffffff
Klaus-Dieter schrieb:> und der Compiler meckert nicht!
Das ist bei asm Statements kein Argument. ARM hatte lange Zeit einen
ähnlichen Fehler im GCC Teil von CMSIS drin, der in bestimmten Fällen zu
falschem Code führte.
Die Spezifikationen in diesem Statement gehen davon aus, dass der darin
enthaltene Assembler-Code einen Input- und einen davon unabhängigen
Output-Operand hat. Also sowas wie swap %0,%1.
1
unsignedchartest_x,test_y;
2
unsignedcharf(unsignedcharx,unsignedchary)
3
{
4
test_x=x;
5
test_y=y;
6
asmvolatile(
7
" swap %0 \n\t"
8
:"=d"(y)
9
:"r"(y)
10
);
11
returny;
12
}
führt zu
1
sts test_x,r24
2
sts test_y,r22
3
swap r24
Hier wird also nicht y geswapped, sondern x.
Probiers mal so:
Auch wenn's schon nen Monat alt ist:
klausr schrieb:> klaus@LittlX:~/src$ avr-gcc -Os -S test_swap_avr.c> klaus@LittlX:~/src$ cat test_swap_avr.s
Du kannst übrigens den avr-gcc auch mit -o- aufrufen. Dann kommt das
Ergebnis gleich im Terminal raus, ohne den Umweg über ein File. Dann
kannst du dir das cat und das anschließende Löschen des Files sparen.
Jörg Wunsch schrieb:> A. K. schrieb:>> Könnte mir aber denken, dass GCC mit -O2 oder -O3 statt -Os ansatzweise>> auf ähnliche Gedanken verfällt.>> Nein, für eine Endlosschleife nicht, denn irgendwann wird ja doch> ein „teurer“ Rücksprung gebraucht.
Hmm, aber es wäre ja trotzdem von Vorteil, wenn der z.B. nur einmal alle
8 Durchläufe gebraucht wird statt bei jedem.
Leute, kommt mal wieder runter.
Ihr könnt nicht erwarten, daß eine Programmiersprache, die dazu erfunden
wurde, daß sie möglichst einigermaßen hardwareunabhängig sein soll,
spezielle Hardwareeigenschaften wie Swap oder das Arbeiten mit dem Carry
usw. berücksichtigt.
Wenn die Compilerprogrammierer so einige Sachen wie Multiplikation mit
2er potenzen usw. per Schift erledigen oder sehr spezielle Dinge
dediziert entdecken (wie die Verwendung von Swap), dann ist das schon
recht viel.
Mehr sollte man nicht wirklich erwarten, es sei denn, es steckt eine
wirklich bedeutsame Hardware-Eigenschaft dahinter (z.B. besondere
MAC-Register mit erhöhter Bitzahl für die Signalverarbeitung, SVC's,
schnelle Interrupts per Regitersatz-Umschaltung (was Rett- und
Restaurierzeit spart) usw.)
Vielleicht kennt jemand noch den "Lampe,Jorke,Wengel" und hat dort
gesehen, wie unglaublich effizient man mit Carry und Registerswap man in
Assembler programmieren kann. Das erreicht man mit C oder Pascal oder
compiliertem Basic udgl. nie und nimmer. Aber im Stile der heutigen Zeit
wird dann eher gesagt "nimm einen dickeren Controller".
W.S.
W.S. schrieb:> Leute, kommt mal wieder runter.
Verfolg mal c-haters Vorgeschichte. Er ist kein unbeschriebenes Blatt.
> Wenn die Compilerprogrammierer so einige Sachen wie Multiplikation mit> 2er potenzen usw. per Schift erledigen oder sehr spezielle Dinge> dediziert entdecken (wie die Verwendung von Swap), dann ist das schon> recht viel.
?
Das sind einfache Übungen im Compilerbau.
> Assembler programmieren kann. Das erreicht man mit C oder Pascal oder> compiliertem Basic udgl. nie und nimmer. Aber im Stile der heutigen Zeit> wird dann eher gesagt "nimm einen dickeren Controller".
Wie PeDa weiter oben schon gesagt hat:
Es bringt nichts, ein Codestück um 100% zu optimieren, wenn dieses
Codestück für nicht mehr als ein paar Prozent der kompletten Laufzeit
verantwortlich ist.
Hab ich ein Programm, dass 1 Stunde Laufzeit für 1 Durchgang benötigt
und habe ich ein Codestück, welches für 1 Sekunde davon verantwortlich
ist, dann ist das die falsche Stelle um mit einer Optimierung
anzusetzen. Selbst wenn ich die Laufzeit dieses Stücks von 1 Sekunde auf
0.1 Sekunden senken könnte (was viel ist), verringert sich die komplette
Laufzeit damit lediglich von 60 Minuten auf 59 Minuten und 59.1
Sekunden. Also praktisch nicht merkbar und völlig irrelevant.
Die meisten dieser 'cleveren' Hacks fallen in den meisten Programmen
(bis auf ein paar Sonderfälle abgesehen) genau in diese Kategorie.
Karl Heinz Buchegger schrieb:> Er ist kein unbeschriebenes Blatt.
Ach herrje, wir alle sind keine Neugeborenen, also was soll's.
Karl Heinz Buchegger schrieb:> Das sind einfache Übungen im Compilerbau.
Nana, SOOOO einfach ist der Compilerbau denn doch nicht.
Karl Heinz Buchegger schrieb:> Wie PeDa weiter oben schon..
Er hat auch schon mal sowas gesagt wie "wie gut, daß mein ATtiny davon
nix weiß.." als es um die maximal erfaßbare Zählrate an einem
Controllerpin ging und er partout nicht begreifen wollte, daß da maximal
Fsystem/2 drin ist (obwohl er genau dieses im Manual hätte nachlesen
können). Kurzum, von generalisierten Aussagen und naßforschen
Behauptungen halte ich überhaupt nix - auch dann nicht, wenn's mit
größter Inbrunst vorgetragen wird, aber ne sachliche Begründung fehlt.
Wenn es mal irgendwo klemmt und man mit einer Kleinigkeit die Sache aus
dem Sumpf gezogen kriegt, dann ist es gut. Beispiel: im CPLD eine
einzige MC eingespart und schon paßt es wieder rein. Wenn..wenn..wenn.
Wir gleiten hier ins Theoretisieren ab. Biertisch. Ach, gut Nacht für
heute.
W.S.
W.S. schrieb:>> Das sind einfache Übungen im Compilerbau.>> Nana, SOOOO einfach ist der Compilerbau denn doch nicht.
Der von oben dir beschriebene Kram schon. Sowas konnten C Compiler schon
zu einer Zeit, als die Storage Class "register" noch reale Bedeutung
hatte. Ersetzung bestimmter Rechenausdrücke durch einfachere ist eine
sehr einfache Optimierung, weil rein lokal auf den Ausdruck begrenzt.
Freilich hat man nicht alles getan, was man gekonnt hätte, denn wenn der
Compiler in 64K passen musste war für exotische Fälle kein Platz.
A. K. schrieb:> Ersetzung bestimmter Rechenausdrücke durch einfachere ist eine> sehr einfache Optimierung, weil rein lokal auf den Ausdruck begrenzt.
Genau. Das ist schon mal die 2-er Potenz Sache.
Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer
machen.
Jeder Student der das 1. Semster "Compilerbau" hinter sich hat, kann
diese Dinge problemlos realisieren. Zum Teil sind derartige
Optimierungen (und noch viele mehr) Teil der zugehörigen Übungen.
Karl Heinz Buchegger schrieb:> Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer> machen.
Eher nicht. Zwar hätte man Swap wohl nicht für lohnend erachtet, weil zu
exotisch, aber einen Baum aus ein paar OR/AND/SHIFT Ops mit bestimmten
Operanden zu identifizieren ist leichter, als den Kram hinterher im Code
zu erkennen. Zumal wenn Suboperandenausdrücke die Befehle trennen.
Peephole-Optimizer waren eher dort relevant, wo eben nicht innerhalb von
Ausdrücken optimiert wird, sondern übergreifend. So beispielsweise wenn
ein Load-Befehl genau das wieder läd, was der andere Ausdruck direkt
davor gespeichert hat, oder ein Sprungbefehl genau dahinter wieder
aufschlägt.
W.S. schrieb:> Er hat auch schon mal sowas gesagt wie "wie gut, daß mein ATtiny davon> nix weiß.." als es um die maximal erfaßbare Zählrate an einem> Controllerpin ging und er partout nicht begreifen wollte, daß da maximal> Fsystem/2 drin ist
Nö, ging es nicht.
Du mußt andere Leute nicht für dumm halten, ich kann Datenblätter lesen.
Karl Heinz Buchegger schrieb:> Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer> machen.
PS: Der Abschnitt "replacement rules" der Wikipedia(en) zur Peephole
Optimization ist schlichtweg Unsinn.
Karl Heinz Buchegger schrieb:> Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer> machen.>> Jeder Student der das 1. Semster "Compilerbau" hinter sich hat, kann> diese Dinge problemlos realisieren.
Wie schon oben geschrieben, musste der AVR-GCC immerhin die Version 4.4
erreichen, um den Ausdruck im Eröffnungsbeitrag als Swap zu erkennen.
Aber seither kann er es, weswegen mich mich die vielen Vorschläge,
Inline-Assembler zu verwenden, etwas wundern.
Yalu X. schrieb:> Aber seither kann er es, weswegen mich mich die vielen Vorschläge,> Inline-Assembler zu verwenden, etwas wundern.
Was will man machen. Dieses dauernde Ersetzen von Divisionen durch
Shifts, weil man ebenfalls meint klüger zu sein als der Compiler ist ja
auch nicht tot zu bekommen. Und diese Optimierung ist schon wesentlich
länger in dem AVR-GCC enthalten.
Yalu X. schrieb:> Wie schon oben geschrieben, musste der AVR-GCC immerhin die Version 4.4> erreichen, um den Ausdruck im Eröffnungsbeitrag als Swap zu erkennen.
Es gibt 2 Wege, wie so etwas in einem Compiler wie GCC landen kann.
(1) Im maschinenunabhängigen Teil werden Rotationen erkannt und im
maschinenabhängigen Teil wird eine Byte-Rotation um 4 durch Swap
ersetzt.
(2) Der Kram landet ziemlich originalgetreu im maschinenabhängigen Teil
und muss dort identifiziert werden.
Wie das hier abgeht weiss ich nicht. Methode (2) ist ziemlich speziell
und gehört eher nicht zu den vorrangigen Optimierungen. Methode (1)
lohnt eher, zumal davon alle profitieren.
Simon K. schrieb:> Was will man machen. Dieses dauernde Ersetzen von Divisionen durch> Shifts, weil man ebenfalls meint klüger zu sein als der Compiler ist ja> auch nicht tot zu bekommen.
Wobei man dabei aber aufpassen muss, dass einem die integer promotion
keinen Strich durch die Rechnung macht. Wenn der Compiler negative Werte
nicht aussschliessen kann wirds hässlicher.
W.S. schrieb:> Leute, kommt mal wieder runter.>> Ihr könnt nicht erwarten, daß eine Programmiersprache, die dazu erfunden> wurde, daß sie möglichst einigermaßen hardwareunabhängig sein soll,> spezielle Hardwareeigenschaften wie Swap oder das Arbeiten mit dem Carry> usw. berücksichtigt.
swap ist aus Sicht des Programmierers keine spezielle
Hardware-Eigenschaft, sondern eine Funktion, die man manchmal braucht,
unabhängig davon, ob der Prozessor dafür eine spezielle Instruktion
bietet. Wenn er das tut, soll die aber auch benutzt werden.
Yalu X. schrieb:> Wie schon oben geschrieben, musste der AVR-GCC immerhin die Version 4.4> erreichen, um den Ausdruck im Eröffnungsbeitrag als Swap zu erkennen.>> Aber seither kann er es, weswegen mich mich die vielen Vorschläge,> Inline-Assembler zu verwenden, etwas wundern.
Nicht jeder hat Lust, bei allen Operationen, die man in C nur indirekt
ausdrücken kann, erstmal nachzuschauen, ob der Compiler auch erkennt,
was eigentlich gemeint war und schlau genug ist, das in die passende
Assembler-Instruktion umzuformen.
Sich darauf zu verlassen klingt irgendwie so ähnlich wie bei DVDs und
modernen Festplatten Daten nur noch mit relativ geringer Sicherheit zu
speichern und sich dann darauf zu verlassen, daß die Fehlerkorrektur
sich schon drum kümmern wird, alle umgekippten Bits wieder zu beheben.
Auch wenn's wohl jeder inzwischen so macht, löst es bei mir ein gewisses
Unbehagen aus.
A. K. schrieb:> Wenn der Compiler negative Werte nicht aussschliessen kann wirds> hässlicher.
Kommt drauf an. Auf der einen Seite ist laut ISO C das Ergebnis eines
Rechtsshifts von negativen Werten eh implementationsspezifisch, so daß
es dem Compiler egal sein kann, wenn es nicht der Division entspricht.
Andererseits kennen viele CPU-Architekturen auch einen arithmetischen
Rechts-Shift, der auch mit negativen Werten umgehen kann.
A. K. schrieb:> Karl Heinz Buchegger schrieb:>> Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer>> machen.>> PS: Der Abschnitt "replacement rules" der Wikipedia(en) zur Peephole> Optimization ist schlichtweg Unsinn.
Sorry.
Nö, ist er nicht.
All diese Dinge KANN man mit Peephole Optimizern machen. Man muss nicht.
Aber man kann. Das der gcc manche Dinge anders erledigt, ist dabei kein
Argument.
Letzten Endes geht es beim Peephole Optimizing nur darum, ein bestimmtes
Muster im erzeugten 'Code' (das kann durchaus auch eine interne
Repräsentierung des Codes sein, die noch nicht auf den endgültigen
Opcodes basiert) zu finden und durch ein anderes funktional
gleichwertiges Muster zu ersetzen. Auch das Abklappern eines Baumes auf
bestimmte Knoten-Teibaum-konstellationen ist nichts anderes als eine
Form des Peephole-Optimizings.
Dein Denkfehler besteht darin, anzunehmen dass Peephole-Optimizer nur
auf Maschinencode-Ebene arbeiten. Das ist aber nicht der Fall. Der
entscheidende Punkt beim Peephole-Optimizing besteht darin, dass der
Optimizer ohne Ansehen der Sprachregeln einfach nur nach Mustern 'in den
Datenstrukturen' sucht und diese Muster durch andere ersetzt. Die
Sprachregeln sind, wenn überhaupt notwendig, implizit in den Mustern
enthalten. Der Optimizer muss sich nicht mehr darum kümmern.
Rolf Magnus schrieb:> Andererseits kennen viele CPU-Architekturen auch einen arithmetischen> Rechts-Shift, der auch mit negativen Werten umgehen kann.
Sicher, aber hast du mal die Resultate von
i / 2
und
i >> 1
bei ungeraden negativen Werten verglichen?
Ein arithmetischer Shift kann also nicht direkt eine Division mit
Vorzeichen ersetzen, sondern es wird eine Anpassung für negative Werte
erforderlich.
A. K. schrieb:> Simon K. schrieb:>> Was will man machen. Dieses dauernde Ersetzen von Divisionen durch>> Shifts, weil man ebenfalls meint klüger zu sein als der Compiler ist ja>> auch nicht tot zu bekommen.>> Wobei man dabei aber aufpassen muss, dass einem die integer promotion> keinen Strich durch die Rechnung macht. Wenn der Compiler negative Werte> nicht aussschliessen kann wirds hässlicher.
Die Frage ist dann aber eher:
Hat der 'clevere' Programmierer das überhaupt bedacht, dass das Ergebnis
eines Rechtsshifts bei negativen Zahlen im 2-er Komplement eben nicht
identisch ist mit einer Division.
Wenn ich dividieren will, weil das die richtige Operation an dieser
Stelle ist, dann ist man gut beraten, da auch eine Division
hinzuschreiben. Ist es möglich diese Division durch einen Shift zu
ersetzen (weil der Datentyp des beteiligten Operanden es erlaubt), dann
macht der Optimizer das (auch wenn ich, wie Rolf korrekterweise anmerkt,
mich nicht 100% darauf verlassen kann, dass der Compiler die Fähigkeit
dazu hat). Ist die Ersetzung nicht möglich, dann hat das auch einen
Grund. Meistens hat dann der Programmierer geschlafen und die falschen
Datentypen benutzt. Man kann aber einem Compiler nicht die mangelhafte
Ausbildung der Programmierer anlasten.
Rolf Magnus schrieb:> Nicht jeder hat Lust, bei allen Operationen, die man in C nur indirekt> ausdrücken kann, erstmal nachzuschauen, ob der Compiler auch erkennt,> was eigentlich gemeint war und schlau genug ist, das in die passende> Assembler-Instruktion umzuformen.
Ich verstehe dein Dilemma.
Trotzdem musst du dich auf einige Dinge verlassen können. Das ein
Compiler die neusten Optimierungstricks nicht unbedingt beherrscht,
davon muss man nicht ausgehen und sollte besser nachsehen, wenn man
darauf angewiesen ist. Es gibt allerdings auch einen Haufen
Optimierungen, die sind seit Jahrzehnten Standard. Wenn ein Compiler die
nicht beherrscht, dann ist das meistens deshalb weil es ganz einfach
noch keinem aufgefallen ist, dass hier eine mögliche Optimierung fehlt
oder weil der Leidensdruck nicht groß genug war (sprich die Operation
kommt nicht oft genug vor, als dass sich jemand ran gesetzt hätte und
sie schneller gemacht hat)
Das der gcc nicht unbedingt auf Spitzen-Leistungen im Bereich 8 Bit
Prozessoren getrimmt ist, wissen wir alle. Aber er schlägt sich nicht
schlecht. Als Faustregel würde ich für mich nehmen: Jede Optimierung auf
Anweisungsebene, auf die ein Neuling mit vielleicht 1 Jahr Erfahrung
auch kommt (oder die er irgendwo gesehen hat), kann ein ernstzunehmender
handelsüblicher Compiler genausogut auch in Eigenregie erledigen. Das
ist nichts, was einem groß Kopfzerbrechen machen müsste.
Trotzdem bleibt natürlich der von dir angesprochene schale
Nachgeschmack. Wenn mich der stört, dann bleibt mir aber in letzter
Konsequenz nicht viel anders übrig, als auf Hochsprachen zu verzichten
und auf direkten Assembler zu gehen. Und das will dann eigentlich keiner
wirklich.
Karl Heinz Buchegger schrieb:> Auch das Abklappern eines Baumes auf> bestimmte Knoten-Teibaum-konstellationen ist nichts anderes als eine> Form des Peephole-Optimizings.
Sorry, aber da bin ich anderer Ansicht. Dass ein Peephole-Optimizer
nicht nur auf dem Maschinecode aufsetzen muss ist richtig. Wobei er im
üblichen Verständnis aber nach einer Art von Codegenerierung greift,
was auch Zwischencode sein darf.
Wenn du aber bereits den vom Parser ausgeworfenen Baum als solchen
Zwischencode definierst, dann machst du den Parser zu einem
Codegenerator erster Stufe und alle lokalen Optimierungen in diesem Baum
werden zu Peephole-Optimierungen. Das wäre ziemlich quer zum üblichen
Verständnis von Abläufen in einem Compiler.
Die Wikipedia-Anmerkung zeigt auch, dass ich nicht der Einzige bin, der
mit der dortigen Definition nicht recht glücklich ist.
Dass man Optimierungen auch umständlich hinten durchführen kann, die man
einfacher vorne gemacht hätte, ist freilich richtig.
> Dieses dauernde Ersetzen von Divisionen durch Shifts, weil> man ebenfalls meint klüger zu sein als der Compiler ist ja> auch nicht tot zu bekommen.
Selbiges mit modulo und Verunden.
Ja, bei 2-er Potenzen und unsigned Typen stimmt diese Beziehung. Aber
auch nur dann.
Und? Das ist für einen Compiler nicht schwer rauszukriegen, ob diese
Voraussetzungen gegeben sind oder nicht und den Ersatz zu machen.
Es ist aber für einen (Nachfolge-)Programmierer nicht so einfach
rauszukriegen, warum in einem größeren System
1
#define QUEUE_SIZE 8
2
3
uint8_tqueue[QUEUE_SIZE];
4
uint8_tcount;
5
6
voidadd(uint8_tvalue)
7
{
8
queue[count++]=value;
9
if(count&(QUEUE_SIZE-1))
10
count=0;
11
}
die Operation so richtig in die Hose geht, wenn die QUEUE_SIZE von 8 auf
10 erhöht wird.
Der Code ist nur beispielhaft gemeint. Es geht darum, dass man hier im
Code eine Annahme versteckt hat, nämlich das QUEUE_SIZE eine 2-er Potenz
ist. Das kann gut gehen, aber wir alle wissen, dass die Dinge eben des
öfteren nicht gut gehen. Vor allen Dingen dann nicht, wenn der Code dann
auch schon ein paar Jahre auf dem Buckel hat und niemand mehr über die
Internals Bescheid weiß.
Zumal es hier keinen Grund für diese Annahme gibt. Solange die
Voraussetzung "ist 2-er Potenz" erfüllt ist, ersetzt mir der Optimizer
recht zuverlässig die Modulo-Rechnung durch ein &. Ist sie nicht
erfüllt, dann benutzt er die Divisions-Module-routine, wie auch immer
die aussieht. Das kostet mir zwar Laufzeit ist aber immer noch korrekt.
Das ist mir immer noch lieber, als ein Programm, welches dann Mist baut
und man dann erst mal (nach Jahren) suchen muss, was da schief ging.
Pastor Braune schrieb:> a = a^b> b = a^b> a = a^b
Ich hacke ja schon ewige Jahre. Aber das Ding war mir neu (kann man
manchmal sicher gut brauchen;-)
Thx 4 te hint
Grüße
Andreas
Andreas H. schrieb:> Pastor Braune schrieb:>> a = a^b>> b = a^b>> a = a^b>> Ich hacke ja schon ewige Jahre. Aber das Ding war mir neu (kann man> manchmal sicher gut brauchen;-)>> Thx 4 te hint
Das ist aber kein 4-Bit Swap, sondern ein Austausch der Inhalte von 2
Variablen. Und vermutlich ginge das sogar schneller, wenn man einfach
eine neue lokale Variable erzeugen und normal kopieren würde ;-)
Ein Problem bei der Optimierung von Mul/Div zu Shift ist, dass der mit
Shifts erzeugte Code länger sein kann als Mul/Div-Befehle oder der
Aufruf einer Laufzeitfunktion. Und avr-gcc daher in seiner üblicherweise
verwendeten -Os Variante zumindest früher oft den Aufruf wählte. Dem
Compiler ist da formal kein Vorwurf zu machen, aber ob der Programmierer
das auch so fundamentalistisch sieht?
Karl Heinz Buchegger schrieb:> A. K. schrieb:>>> Ersetzung bestimmter Rechenausdrücke durch einfachere ist eine>> sehr einfache Optimierung, weil rein lokal auf den Ausdruck begrenzt.>> Genau. Das ist schon mal die 2-er Potenz Sache.> Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer> machen.>> Jeder Student der das 1. Semster "Compilerbau" hinter sich hat, kann> diese Dinge problemlos realisieren. Zum Teil sind derartige> Optimierungen (und noch viele mehr) Teil der zugehörigen Übungen.
ALso ich finde siese Optimierung nicht trival. Klar, in einem eigenen
Mini-Compiler ist recht einfach zu hacken wenn man genau weiß wonach man
sucht. Aber die Anzahl der Regeln wechst schnell und ist irgendwann
nicht mehr zu überblicken -- man will ja nicht nur SWAP erkennen sondern
auch andere Instrktionen, und beileibe nicht jeder Instruktionssatz ist
so einfach wie bei AVRs.
Konkret für swap:
1
staticinlineunsignecharswap(unsignedcharx)
2
{
3
return(x<<4)|(x>>4);
4
}
Dies bringt folgende Operationen:
2 Promotionen 8 Bit -> 16 Bit
2 Shifts
1 Or
1 Truncation 16 Bit -> 8 Bit
Hinzu kommt die Fähigkeit früh zu inlinen und damit früh genug die
Kosten für eine Inline-Version vs. eine nicht-Inline Version bestimmen
zu können, also noch lange bevor mit dem eigentlichen
maschinenabhängigen Teil begonnen wird. Auch das ist nichttrivial.
Die o.g. swap-Darstellung geschieht im GCC im Instruction-Combiner
http://gcc.gnu.org/viewcvs/gcc/trunk/gcc/combine.c?content-type=text%2Fplain&view=co
bereits ein kurzes Überfliegen des Codes sollte klar werden lassen, daß
das kein triviales Stückchen Code ist. Der Instruction-Combiner des GCC
untersucht maximal 3 Pseudo-Instruktionen. Die Beschränkung auf 3 ist
dadurch begründet, daß die Laufzeit exponentiell mit Anzahl der
Instruktionen steigt. Zudem sind bereits bei nur 3 Instruktionen sehr
viele Sonderfälle zu berücksichtigen, und die Anzahl zu testenden
Combines ist selbst für kleine Routinen sehr hoch.
Konkret erkennt der Combiner, daß das Konstrukt einem 8-Bit Rotate um 4
entspricht, welches wiederum in AVR-Teil implementiert wird.
Ein Peephole würde an dieser Stelle nicht oder nur sehr schlecht
funktionieren.
Johann L. schrieb:> man will ja nicht nur SWAP erkennen sondern> auch andere Instrktionen, und beileibe nicht jeder Instruktionssatz ist> so einfach wie bei AVRs.
Eine solche Optimierung lohnt IMHO dann, wenn man eine zwar nicht
triviale aber strikt lokale generische Erkennung von
Rotationsoperationen durchführt. Zumal die in Crypto-Algorithmen nicht
selten sind. Daraus pickt man dann den Spezialfall für SWAP.
A. K. schrieb:> Johann L. schrieb:>> man will ja nicht nur SWAP erkennen sondern>> auch andere Instruktionen, und beileibe nicht jeder Instruktionssatz ist>> so einfach wie bei AVRs.>> Eine solche Optimierung lohnt IMHO dann, wenn man eine zwar nicht> triviale aber strikt lokale generische Erkennung von
Lokal muß es nicht sein, daß heißt im Codefluß können beliebig viele
andere, unbeteiligte Instruktionen auftreten. Was hier relevant ist,
ist der Datenfluß.
Johann L. schrieb:> Lokal muß es nicht sein, daß heißt im Codefluß können beliebig viele> andere, unbeteiligte Instruktionen auftreten. Was hier relevant ist,> ist der Datenfluß.
Mit "lokal" bezog ich mich auf die Auswirkungen, nicht auf den Raum.
Gleicher Input und Output, keine Seiteneffekte, ausser ggf. Flags.
Simon K. schrieb:> Das ist aber kein 4-Bit Swap, sondern ein Austausch der Inhalte von 2> Variablen.
Für Nibbleswap haben viele CPUs ja schon einen ASM Befehl. Da braucht
man es eher nicht, denk ich.
>Und vermutlich ginge das sogar schneller, wenn man einfach> eine neue lokale Variable erzeugen und normal kopieren würde ;-)
Unglücklicherweise arbeiten die meisten meiner Programme nicht mit
Vermutungen.
Und schneller als drei ASM Statement (nach -O2) wirds wohl auch nicht
oder ?
Grüße
Andreas
Andreas H. schrieb:> Simon K. schrieb:>> Das ist aber kein 4-Bit Swap, sondern ein Austausch der Inhalte von 2>> Variablen.> Für Nibbleswap haben viele CPUs ja schon einen ASM Befehl. Da braucht> man es eher nicht, denk ich.
Äh ja? Darum geht es doch hier. Siehe Eröffnungspost.
>>Und vermutlich ginge das sogar schneller, wenn man einfach>> eine neue lokale Variable erzeugen und normal kopieren würde ;-)> Unglücklicherweise arbeiten die meisten meiner Programme nicht mit> Vermutungen.> Und schneller als drei ASM Statement (nach -O2) wirds wohl auch nicht> oder ?
Nunja, wenn für die nachfolgenden Operationen keine bestimmten Register
benötigt werden, wird der "Variablenswap" unter Umständen sogar in 0
Instruktionen optimiert.
Es ist jedenfalls besser hinzuschreiben, was man meint und lässt den
Compiler überlegen, was in der Situation besser ist, als dass man
irgendwelche vorzeitigen Optimierungen einbaut, die unter Umständen
jedoch nachteiligen Code erzeugen könnten.
Andreas H. schrieb:> Und schneller als drei ASM Statement (nach -O2) wirds wohl auch nicht> oder ?
Je nach Aufbau der CPU geht das sehr wohl.
Diese 3 XORs sind sequentiell abhängig, also nicht in weniger als 3
Takten machbar, wenn eine ALU-Operation mindestens 1 Takt benötigt.
Im Gegensatz dazu ist die Variante mit 3 Transportbefehlen nicht
sequentiell abhängig, jedenfalls nicht vollständig, somit
parallelisierbar.
Überdies ist es bei Operanden in Registern prinzipiell möglich,
Transportbefehle vollständig über Register Renaming zu implementieren,
womit es aus der Sicht von Ausführungseinheiten und entsprechenden
Laufzeiten auf 0 Takte schrumpft, selbst wenn die Register wirklich
ihren Inhalt tauschen.
Das Ding mit den 3 EXORs ist vor allem interessant, wenn man 2 Register
tauschen möchte, ohne weiteren Platz zu benötigen.
Nur dafür kenne ich es.
Gruß
Jobst