Hallo Community,
Wieso kompiliert AVR GCC(AVR Studio 5) meine Switch Case Anweisung(ca.
16 cases) nicht in eine Mehrfachverzweigung (Sprungtabelle) sondern in
lauter cpi,breq ?
Wie kann ich den Compiler davon überzeugen eine Mehrfachverzweigung mit
ijmp zu nehmen?
disassembler Ausschnitt:
1
00000121 LDS R24,0x01A2 Load direct from data space
2
00000123 MOV R24,R24 Copy register
3
00000124 LDI R25,0x00 Load immediate
4
00000125 CPI R24,0x08 Compare with immediate
5
00000126 CPC R25,R1 Compare with carry
6
00000127 BRNE PC+0x02 Branch if not equal
Ausschnitt aus meinem C- Code
1
switch(TWICSM_cnt)//
2
{
3
4
caseWii_NeWayInit_6_1_CMD:
5
/***** 6/1) I2C- Multiplexer(PCA9548) auf Kanal 0 umschalten *****/
6
if(!(CHECKBIT(PCA9548_State,PCA9548_ch0_sel)))//
7
{
8
TWI_Start_Transceiver_With_Data(send_me,2);// Multiplexer auf Kanal 0 umstellen
Hallo Alex,
Ich bin mir ziemlich sicher, dass die Übersetzung nicht fehlerhaft ist.
Der Compiler halt halt lediglich eine andere Wahl getroffen, deinen Code
in Maschinensprache umzusetzen, als du es dir erhofft hast.
Viele Grüße,
Lars
@ Johann L.
ich finde es nicht richtig, wenn statt einer einfachen Sprungleiste, ca.
60 Zeilen bestehend aus cpi,cpc,breq + rjmps entstehen. Dies wirkt sich
negativ als auf die codedichte, so auch auf die CPU-Zeit aus.
Mit Optimierungen kenne ich mich nicht aus. In den meisten Fällen sind
diese ausgeschaltet(none) oder -s, wenn code gespart wird. Beide
Einstellungen haben in diesen Fall keine Auswirkung auf die
realisierung(kompilierung) der switch case Anweisung.
Naja. So ernst darf man das nicht nehmen. Als Anfänger wählt man schon
mal das falsche Wort oder nimmt seine eigenen Annahmen darüber was
"richtig" ist wichtiger als es angemessen ist.
Ich mag mich darin irren, das der TO ein Anfänger ist, aber dann würde
mich interessieren, nach welchen Maßstäben er feststellt, das hier ein
Fehler vorliegt bzw. welche Annahmen bzgl. einer "richtigen" Übersetzung
er hier für korrekt hält.
Die Tatsache alleine, das im Quellcode ein switch vorkommt rechtfertigt
jedenfalls nicht die Annahme das dies in eine Sprungtabelle umgesetzt
werden muss um optimalen oder "richtigen" Code zu erzeugen.
Bitte erkläre Dich mal etwas ausführlicher, TO. Entweder lernen wir was
draus oder Du.
Inzwischen hast Du Johann geantwortet und ein weiteres Detail genannt,
das es Dich annehmen lässt das eine Sprungtabelle hier das "richtige"
ist.
Nun ist die Anzahl der cases alleine auch kein Maßstab dafür. Wenn
beispielsweise die cases keine oder nicht genug aufeinanderfolgenden
Werte betreffen kann diese breq doch besser sein.
@Noname (Gast)
Den größten Teil meines Wissens habe ich diesen Forum zu verdanken.
Im Artikel Mehrfachverzweigungen (
http://www.mikrocontroller.net/articles/AVR-Tutorial:_Mehrfachverzweigung
) steht, dass switch case –Anweisungen durch Sprungleisten realisiert
werden, wodurch bei mir die Erwartung entstand im disassembler auch
solche vorzufinden.
Besteht den eine Möglichkeit den Compiler auf Sprungleisten umzustellen?
>Im Artikel Mehrfachverzweigungen (...) steht, dass switch case >–Anweisungen
durch Sprungleisten realisiert
>werden, ...
Ganz genau sooo, steht das aber da nicht. ;-)
Vielmehr wurde das auf bestimmte Fälle eingegrenzt:
>Oft liegen die einzelnen Vergleichswerte nebeneinander (z. B. 7..15), ...>In so einem Fall kann man mittels einer Sprungtabelle das Programm >verkürzen,
beschleunigen
Das habe ich eben oben erwähnt.
Die Frage ist ob so ein Fall bei Dir vorliegt.
>Besteht den eine Möglichkeit den Compiler auf Sprungleisten umzustellen?
Das macht keinen Sinn. Es hängt eben, wiegesagt, von einigen Faktoren
ab.
Es wäre eine ganz nützliche Übung das mal selbst in Assembler zu
schreiben.
Was kommt dabei heraus:
A) 0, 1, 2, 3, 4,....
B) 17, 18, 19, 20, ...
C) 45, 68, 112, 10024,...
D) 0, 1, 2, 3, 4, 16, 17, 18, 19
Die ganz abgef... hier, wie P. Dannegger, oder vielleicht ich fangen
dann auch noch an, die Zeit die in den Fällen B und D nötig ist um
mittels Subtraktion den Wert auf die Tabelle auszurichten mit ausführung
mittels breq-Kette zu vergleichen. Und wenn das Fernsehprogramm schlecht
ist oder das Ganze bezahlt wird noch festzustellen, ob es gewisse
Häufigkeitsverteilungen gibt, die jeweils die eine oder andere Methode
oder Mischungen daraus ratsam machen.
Also so ganz trivial und mit einer einzigen Aussage zu erschlagen ist
das ganze nicht.
Hättest du mal ein übersetzbares Beispiel, wo es falsch ist, und die
Version vom GCC? Mit dem avr-gcc 4.5.3, der hier grad rumliegt, ist eher
die umgekehrte Richtung interessant, d.h. er produziert ineffiziente
Tables, obwohl so ziemlich jede Alternative besser wäre.
Noname schrieb:>>Besteht den eine Möglichkeit den Compiler auf Sprungleisten umzustellen?> Das macht keinen Sinn. Es hängt eben, wiegesagt, von einigen Faktoren> ab.
Doch, das könnte schon möglich sein. So gibt es mindestens einen
Schalter für die umgekehrte Richtung, nämlich -fno-jump-tables.
Ausserdem gibt per --param definierbare Parameter wie
"case-values-threshold", mit denen sich die interne Heuristik zur
Entscheidung der Codegenerierung möglicherweise beeinflussen lässt.
Aha. So ist das.
Und das sind alle Werte?
Ist für den Compiler erkennbar, das dies alle überhaupt auftretenden
Werte sind?
Mir fällt auf, das im Assemblercode ein 16-Bit Vergleich gemacht wird.
Was hat TWICSM_cnt für einen Datentyp?
Wie gross ist das grösste Codestück in den Cases?
Noname schrieb:> Also so ganz trivial und mit einer einzigen Aussage zu erschlagen ist> das ganze nicht.
Schade :-(
Ich finde diese Compilierungs- Geschichte ziemlich doof, weil meine
Zielanwendung auf Energie sparen ausgelegt ist, wobei jeder Zyklus als
Luxusgut eingestuft wird. Der MC sollte ja schlussendlich möglichst
lange im Sleepmode verweilen, statt sich mit ultralangen cpi,breqs –
sich herumprügeln.
Besser hätte ich nie mit assembler bekanntschaft gemacht :-)
A. K. schrieb:
>> Das macht keinen Sinn. Es hängt eben, wiegesagt, von einigen Faktoren>> ab.>Doch, das könnte schon möglich sein. So gibt es mindestens einen>Schalter für die umgekehrte Richtung, nämlich -fno-jump-tables.>Ausserdem gibt per --param definierbare Parameter wie>"case-values-threshold", mit denen sich die interne Heuristik zur>Entscheidung der Codegenerierung möglicherweise beeinflussen lässt.
Ja. Richtig. Da habe ich mich ein wenig weit aus dem Fenster gelehnt.
Ich habe auch so eben daran gedacht, das der gcc in einigen Fällen nicht
gerade optimalen avr code erzeugt.
Solange das komplette Listing des TO nicht vorliegt, kann man nur im
Trüben fischen. Jegliche Aussagen bezüglich des Kompilats sind reine
Spekulation. warum ein Compiler etwas macht, läßt sich nur aus dem
GESAMTEN Kontext bewerten.
Meine Güte. Habe mich heute schon wieder so über den IAR für ARM
geärgert das ich gcc schon wieder schöner finde, als er ist. Ersterer
macht Sprungtabllen wo immer es ein freies Byte gibt. :-)
Noname schrieb:> Mir fällt auf, das im Assemblercode ein 16-Bit Vergleich gemacht wird.> Was hat TWICSM_cnt für einen Datentyp?
Deine Feststellung ist richtig! der macht die ganze Zeit 16-Bit
Vergleiche, wobei im R25 eine 0 steht, weshalb auch 8-Bit Vergleiche
(cpi) ausreichen würden. Der Counter ist vom Typ uint8_t.
Das ist ein Case mit den meisten Codezeilen:
1
/***** Wii Controller ID Pointer Set *****/
2
caseWii_IdReq_4_1_CMD:// ID Pointeradresse 0xFA setzen
3
memcpy_P(tmparray,WiiInDev_IdPtr_Set,2);// Kopiere von Flash -> SRAM
Hm. Interessant.
"Counter" finde ich ein wenig irritieren. Die defines sehen ja so aus
als wenn da was empfangen wird. Das könnte bedeuten, das der Compiler
nicht erkennen kann, das nur ein subset von uint8_t benutzt wird.
Das implizite Verwenden von 16 Bit ist allerdings wirklich ein Problem.
Es sind ja noch Punkte offen.
1. Welche gcc version verwendest Du?
2. Kannst Du bitte mal kompilierbaren Code posten der das Problem zeigt?
Am besten ein komplettes AVR-Projekt.
3. Poste bitte die Kommandozeile für den Aufruf von gcc.
4. Kann der Compiler erkennen das es sich hier um ein Subset von uint8_t
handelt? Wenn ja, wie?
Ich esse erstmal was.
Mahlzeit.
alex schrieb:> Das ist ein Case mit den meisten Codezeilen:
Es ist völlig unwichtig, wieviele Zeilen hinter den einzelnen case
labels stehen. Sehr wichtig hingegen ist der komplette Rahmen des switch
Statements, also der Typ der Variablen und alle Werte der case labels,
bitte numerisch. Den Code darin kannst du weglassen.
A. K. schrieb:
>Es ist völlig unwichtig, wieviele Zeilen hinter den einzelnen case>labels stehen.
Meinst Du? Also die C-Zeilen sind wahrscheinlich weniger bedeutsam. Aber
ich habe überlegt, ob es sein kann, das er es mit den 16-Bit jmps nicht
mehr schafft aus dem switch herauszukommen und vielleicht deswegen das
ganze verweigert. Könnte natürlich auch die long jumps nehmen. Aber will
er oder kann er nicht?
Mag sein, das ich da falsch liege.
Die Gesamtdistanz kann vielleicht eine Rolle spielen, aber nur in der
umgekehrten Richtung. Bei kurzen Distanzen werden Einzelvergleiche
besser und schneller. Folglich kann es sein, dass dann Vergleiche
gegenüber einer Tabelle gewinnen. Du hast aber schon die Vergleiche,
trotz viel Code, willst aber eine Tabelle.
Wie sieht denn der komplete erzeugte compare-and-branch Code aus? Ist
der linear, also compare-branch-compare-branch, oder ist das ein
Entscheidungsbaum? So ein Baum kann nämlich recht effizient sein.
Ich habe gerade ein wenig herumgespielt: Es scheint so zu sein, dass der
GCC für AVRs mit mehr als 8 kiB Flash generell keine Sprungtabellen
generiert, unabhängig von der tatsächlichen Codegröße. 8 kiB ist die
Größe, wo mit RJMP gerade noch jede Stelle im Programmspeicher erreicht
werden kann. Ich habe mit GCC 4.5.3 getestet, neuere Versionen sind
gerade im Bau.
Edit 1: Bei 4.6.3 das gleiche Problem.
4.7.0 dauert noch etwas, weil der wohl neuere Binutils braucht.
Edit 2: Bei 4.7.0 das gleiche Problem.
-mshort-calls hilft — zumindest in dem von mir getesteten Fall — weiter.
Möglicherweise gibt es dann Einschränkungen, wenn die Switch-Anweisung
mehr als 8 kiB lang ist, aber so etwas sollte in gut strukturierten
Programmen kaum vorkommen.
alex schrieb:> Das ist ein Case mit den meisten Codezeilen:
Damit kann man nix anfangen.
1) Die Frage zu -mcall-prologues steht immer noch im Raum.
2) Optimierung vielleicht doch auf "none"? Wir wissen es nicht.
3) Wenn du eine definitive Aussage willst, dann:
A) Was sind die Compilerschalter?
B) Was ist die Compilerversion?
C) Wo ist ein compilierbares Beispiel zum Nachvollziehen?
A, B und C erhält du, indem -v -save-temps zu den Compileroptionen
zugegeben wird. A, B verrät die Kommandozeile und C wird also i-Datei
erzeugt; es ist die präprozesierte C-Quelle (Text).
Ok, besserer Testcode, allerdings kurzer Code. -O2, 4.7.0.
1
intf(chari,intx,inty)
2
{
3
switch(i){
4
case1:returnx+y;
5
case2:returnx-y;
6
case3:returnx&y;
7
case4:returnx|y;
8
case5:returnx^y;
9
case6:returnx<<y;
10
case7:returnx>>y;
11
case8:returnx*y;
12
case9:returnx/y;
13
default:return0;
14
}
15
}
Für Mega8 gibts eine Jumptable, insgesamt 23 1-Wort Befehle. Laufzeit 20
Takte. Bei mehr als 8KB würde sich das auf ca. 34 Worte und 23 Takte
verlängern.
Für Mega128 gibts einen Entscheidungsbaum mit 20 1-Wort Befehlen.
Laufzeit zwischen 3 und 12 Takten.
Also: Wer will hier wirklich einen Table-Switch?
PS: Anzahl Befehle und Laufzeit beziehen sich nur auf den switch code
selbs, nicht auf den Code in den case labels.
Ich würde das Ergebnis von eben so interpretieren: Bei kurzen Sprüngen
und grossen AVRs ist eine Jumptable nur bei grosser Anzahl von Fällen
besser als ein Entscheidungsbaum. Sowohl in Länge als auch in Laufzeit.
Und bis die fixe Laufzeit einer Jumptable kürzer wird als die mittlere
Laufzeit eines Entscheidungsbaums (O(log(N)) muss die Anzahl Fälle schon
recht extrem werden.
Ein wesentlich Anteil daran hat der Umstand, dass eine Jumptable bei
AVRs einen recht heftigen fixen Oberhead hat, der Baum hingegen keinen.
Johann L. schrieb:>> -mshort-calls>> Davon rate ich ab. Das Problem ist da:>> http://gcc.gnu.org/viewcvs/branches/gcc-4_7-branch...
Das habe ich auch nicht ganz verstanden. In der von dir verlinkten
Codestelle wird, wenn ich das richtig verstehe, die Anzahl der Cases
festgelegt, ab der eine Sprungtabelle verwendet wird.
Aber wie spielt hier -mshort-calls hinein bzw. was kann schlimmstenfalls
passieren, wenn man diese Option benutzt?
Edit:
Wahrscheinlich sollte man bei großen Programmen -mcall-prologues
weglassen, weil der Prolog/Epilog bei -mshort-calls vermutlich mit einem
RCALL aufgerufen wird, der evtl. nicht weit genug reicht.
Aber versuchen kann man -mshort-calls ja immer. Falls dabei etwas schief
läuft, sollte doch der Linker meckern, und man kann die Option dann ja
immer noch zurücknehmen.
Oder gibt es noch weitere Probleme damit?
alex schrieb:> Besteht den eine Möglichkeit den Compiler auf Sprungleisten umzustellen?
Es ist das Ziel eines guten Compilers, den im Sinn der gewählten
Optimierungsstrategie bestmöglichen Code zu generieren. Wenn er zum
Ergebnis kommt, dass ein compare/branch Schema effizienter ist als eine
Sprungleiste, weshalb sollte er dann eine Sprungleiste erzeugen?
D.h in die Kostenberechnung gehen -mcall-prologues ein und obs ein JMP
hat oder nicht.
Gibt's kein JMP oder ist -mshort-calls oder -mcall-prologues gesetzt,
dann ist der Threshold 8, ansonsten 17. Ab 4.7 stimmt der Threshold
nicht mehr, u.a. wegen http://gcc.gnu.org/PR49903
für ältere Versionen wird sich der Autor was dabei gedacht haben, für
neuere Versionen hat's der Autor verpennt. Mea culpa.
> bzw. was kann schlimmstenfalls passieren, wenn man diese> Option benutzt? Aber versuchen kann man -mshort-calls ja immer.> Falls dabei etwas schief läuft, sollte doch der Linker meckern,> und man kann die Option dann ja immer noch zurücknehmen.
Ja, aber die meisten Anwender verstehen die Linkermeldung nicht, und
daß -mshort-calls ein Problem ist. Um JMP auf RJMP abzubilden falls
möglich sollte man Jump-Relaxing verwenden; allerdings geht das nicht in
die Kostenberechnung des Compilers ein.
> Wahrscheinlich sollte man bei großen Programmen -mcall-prologues> weglassen, weil der Prolog/Epilog bei -mshort-calls vermutlich mit> einem RCALL aufgerufen wird, der evtl. nicht weit genug reicht.
Ob Call-Prologe günstig sind hängt auch von der Anwendung ab. In die
Kosten für den Prolog geht JMP/RJMP mit den entsprechenden Kosten ein.
@Johann L.
Danke für die Info!
Was mir aber in diesem Zusammenhang überhaupt noch nicht in den Kopf
geht: Warum wird der Case-Threshold von TARGET_CALL_PROLOGUES abhängig
gemacht? Das sind doch zwei völlig verschiedene Dinge.
Übrigens liefert obige Funktion nur die Vorbelegung für
case-values-threshold. Dies Schräubchen kann zum Beispiel getrimmt
werden per
--param case-values-threshold=8
o.ä. wobei der Default auf 0 steht, d.h. dann wird der Wert von obiger
Funktion aus dem avr-gcc verwendet.
Bei Tabellen, die >= case-values-threshold sind, wird eine Sprungtabelle
erzeugt und ansonsten ein if-else Binärbaum.
Yalu X. schrieb:> Was mir aber in diesem Zusammenhang überhaupt noch nicht in den Kopf> geht: Warum wird der Case-Threshold von TARGET_CALL_PROLOGUES abhängig> gemacht? Das sind doch zwei völlig verschiedene Dinge.
4.6 erzeugt folgenden Code für eine Tabelle mit 17 Einträgen 1..17 und
unsigned 8-Bit switch (R24):
1
ldi r25,lo8(0)
2
sbiw r24,1
3
cpi r24,17
4
cpc r25,__zero_reg__
5
brsh .L23
6
subi r24,lo8(-(gs(.L41)))
7
sbci r25,hi8(-(gs(.L41)))
8
movw r30,r24
9
lsl r30
10
rol r31
11
lpm __tmp_reg__,Z+
12
lpm r31,Z
13
mov r30,__tmp_reg__
14
ijmp
Und mit -mcall-prologues oder 4.7:
1
ldi r25,lo8(0)
2
sbiw r24,1
3
cpi r24,17
4
cpc r25,__zero_reg__
5
brsh .L23
6
subi r24,lo8(-(gs(.L41)))
7
sbci r25,hi8(-(gs(.L41)))
8
movw r30,r24
9
jmp __tablejump2__
Warum im alten Compiler nicht immer das __tablejump2__ aus der libgcc
verwendet wurde weiß ich auch net. Jedenfalls geht call-prologues immer
noch in die Kosten ein...
Yalu X. schrieb:> -mshort-calls hilft — zumindest in dem von mir getesteten Fall — weiter.
Diese Option sollte es gar nicht geben. Nun hat es auch noch ein
selten dämliches Rin^H^H^HEntwicklerchen geschafft, diese Option in
die GUI vom AVR Studio 5 zu verdrahten. Die Folge ist, dass die
Leute diesen Mist auch wirklich auswählen und dann natürlich in
Linkerfehler rennen, wenn der Code doch ein bisschen größer wird.
Jörg Wunsch schrieb:>> -mshort-calls hilft — zumindest in dem von mir getesteten Fall — weiter.>> Diese Option sollte es gar nicht geben.
Es ist natürlich i.Allg. nicht sehr sinnvoll, auch alle Unterprogramm-
aufrufe auf short umzustellen, wenn man eigentlich nur eine Switch-
Anweisung optimieren möchte. Da wäre es besser, wenn es eine Option
-mshort-jmptables gäbe, die nur die Switch-Anweisungen beeinflusst,
denn diese sind selten so lang, dass 12 Bit Sprungweite nicht ausrei-
chend wären.
Noch besser wäre es natürlich, wenn der Compiler selbst entscheiden
würde, ob in der Sprungtabelle 12-Bit-Sprünge (RJMP) ausreichen oder ob
es 22 Bits sein müssen (JMP). Bei If-Anweisungen ist er ja sogar in der
Lage, aus drei Alternativen (BRxx (6 Bit), RJMP (12 Bit) und JMP (22
Bit)) die jeweils beste auszuwählen. Nur bei den Jumptables gibt es
diese Unterscheidung wohl (noch) nicht.
> Nun hat es auch noch ein selten dämliches Rin^H^H^HEntwicklerchen> geschafft, diese Option in die GUI vom AVR Studio 5 zu verdrahten.> Die Folge ist, dass die Leute diesen Mist auch wirklich auswählen und> dann natürlich in Linkerfehler rennen, wenn der Code doch ein bisschen> größer wird.
Naja, wenn es dort wirklich als short-/calls/ angepriesen wird und nicht
als mögliche Optimierung wür Switch-Anweisungen, wird die Versuchung
nicht sehr groß sein, die Option zu aktivieren. Ich habe hier im Forum
jedenfalls noch keine Anfragen von Leuten gesehen, die sich deswegen
plötzlich über seltsame Linkermeldungen wundern.
Yalu X. schrieb:> Ich habe hier im Forum> jedenfalls noch keine Anfragen von Leuten gesehen, die sich deswegen> plötzlich über seltsame Linkermeldungen wundern.
Ich schon, zumindest bei avrfreaks. GUI-Nutzer klicken auf alles,
von dem sie sich erhoffen, dass es ihnen irgendeine Hilfe sein
könnte. :-)
Jörg Wunsch schrieb:> Ich schon, zumindest bei avrfreaks. GUI-Nutzer klicken auf alles,> von dem sie sich erhoffen, dass es ihnen irgendeine Hilfe sein> könnte. :-)
Ok, 1:0 für dich :)
Vielleicht sollte in das GUI ein Eignungstest eingebaut werden, der
immer dann aufgerufen wird, wenn die Option nicht innerhalb der letzten
paar Tage mindestens einmal erfolgreich verwendet wurde ;-)
Thread beobachten
Seitenaufteilung abschalten