Erzeuge den optimalen Code, um einen bekannten Wert in ein AVR
Register zu laden, wobei 1..4 aufeinander folgende GPRs zu setzen sind.
Der Code-Generator erzeugt zwar Code für AVR, läuft selbst aber auf einem PC; daher die Frage in "PC-Programmierung".
Beispiel in C-Speek: u32 R10 = 0x1ff.
CLR R13
CLR R12
MOVW R10, R12
INC R11
DEC R10
Für den Fall, dass zum Beispiel u16 R24 bereits den Wert 0 enthält:
MOVW R12, R24
MOVW R10, R24
INC R11
DEC R10
Vor allem die mögliche Verwendung von Arithmetic wie im letzten Beispiel (INC, DEC, COM, NEG, ASR, LSR, LSL, SWAP, BLD) macht es komplizierter, ebenso wenn Teile des Ziel-Registers wiederverwendet werden können.
Falls ein 8-Bit Scratch-Reg verfügbar ist, lässt sich jede n-Byte Konstante in maximal 2n Instruktionen setzen: n * (LDI + MOV). Falls kein Scratch-Register verfügbar ist, so braucht man 2 Instruktionen mehr, um temporär ein 8-Bit Scratch-Register in R16...R31 freizuschaufeln. Beispiel: u8 R10 = 42 und kein anderes GPR enthält bereits 42:
PUSH R31
LDI R31, 42
MOV R10, R31
POP R31
Falls z.B. R31 = 2, dann geht es auch schneller und ohne PUSH/POP:
Nein, er geht mir nicht um einen bestimmten Assembler Code, sondern für einen Generator dafür. Und der Generator steht weder in Assembler, noch läuft er auf einem AVR. Aber wenn es sich glücklich macht, dann schieb den Beitrag eben dort hin.
Größe. Und falls es mehrere Möglichkeiten gibt, die Größe zu minimieren, dann die schnellste Lösung. Wobei es hier immer so ist, dass kürzere Lösungen nie langsamer als lämgere Lösunge sind. Eine kürzeste Lösung ist also auch dicht am Speed-Optimum.
Außerdem kann davon ausgegangen werden, dass mindestens ein Register < R16 beteiligt ist (weil wenn alle Teil-Regs >= R16 sind, dann ist die Lösung nicht allzu schwer).
...und natürlich erwarte ich hier nicht, dass mir jemand den Code schreibt; es geht einfach um Anregungen / Algorithmen. Dabei ist dann die Laufzeit des Codes selbst auch nicht komplett egal; eine Brute-Force Suche ist zum Beispiel nicht praktikabel. Also
Code (auf PC): Hier sind die Nebenbedingungen nicht so einfach darzustellen. Eine Brute-Force Suche scheidet wie gesagt wegen der Performance aus. Der aktuelle Ansatz ist, a priori die beste Sequenz zu erzeugen, was aber wegen der vielen Möglichkeiten inpraktikabel / schlecht wartbar / noch unvollständig ist.
Code (auf PC): Hier sind die Nebenbedingungen nicht so einfach
darzustellen. Eine Brute-Force Suche scheidet wie gesagt wegen der
Performance aus.
Das glaube ich nicht. Der Suchraum kann ja bereits vorab ganz erheblich ausgedünnt werden. Was dann noch bleibt, sollte sich auf einem neuzeitlichen PC tatsächlich noch mittels BruteForce erschlagen lassen.
Und: Um wirklich garantiert die bestmögliche Lösung zu finden, ist es sogar der einzige Weg.
Alles andere kann die bestmögliche Lösung nur mit einer gewissen Wahrscheinlichkeit erreichen.
Allerdings: Hast du dir auch mal darüber Gedanken gemacht, dass es recht häufig vorkommt, dass SFIOR in einer bestimmten Reihenfolge beschrieben werden müssen? Oder in einem bestimmten zeitlichen Minimalabstand? Oder sogar auf irgendeine Antwort der Hardware gewartet werden muss, bevor der nächste Schreibvorgang getan werden kann?
Wenn du all diese Komplexität mit in deinem Generator unterbringen willst, dann wird es allerdings tatsächlich kompliziert und ist mittels BruteForce wohl auch auf einem PC nicht mehr sinnvoll lösbar.
Lässt sich das nicht auf einen kürzeste-Wege-Algorithmus zurückführen? Jeder Knoten ist ein Zustand der Register, beim Startknoten sind alle Register "unbekannt", die Kanten sind Instruktionen. Kantengewichte sind Größe der Instruktion im Programmspeicher. Im Zielknoten haben die Register den gewünschten Inhalt.
Vielleicht A* Algorithmus, mit dem Abstand der Registerinhalt zum gewünschten Zustand als Distanzheuristik.
Eine bizarre Methode, ein Doppelregister zu Nullen, ist mir im GCC der 16-Bit PICs begegnet: das Basisregister mit 0 multiplizieren. Da kommt man selten von alleine drauf, weil man das üblicherweise mit "langsam" verbindet, was da indes nicht zutrifft.
Tiefensuche mit Tree Pruning. Den Suchbaum zu stutzen und Bedingungen dafür anzugeben ist wesentlich einfacher, als kürzeste Sequenzen direkt zu erzeugen. Die Lösung entspricht i.w. dem was Ob S. beschreibt.
Zum Beispiel reduzieren die meisten Instrukionen einer Lösung die Hamming-Distanz, es gibt aber auch Fälle mit MOVW wie bei den obigen Beispielen, welche die Hamming-Distanz nicht verändern. Zum Glück gibt es keine Fälle, wo die Hamming-Distanz temporär zunimmt (zumindest sind mir keine eingefallen).
Der Suchraum kann ja bereits vorab ganz erheblich ausgedünnt
werden. Was dann noch bleibt, sollte sich auf einem neuzeitlichen
PC tatsächlich noch mittels BruteForce erschlagen lassen.
Im Kontext muss die Laufzeit effektiv O(1) sein, d.h. ab einer willkürlich festgelegten Grenze muss das Verfahren abrebrochen werden. In dem Fall gibt es evtl. nur eine suboptimale Lösung -- falls überhaupt. Wo genau diese Grenze liegt, kann ich erst festlegen, wenn alles fertig ist und ich profilen kann.
Hast du dir auch mal darüber Gedanken gemacht, dass es recht häufig
vorkommt, dass SFIOR in einer bestimmten Reihenfolge beschrieben
werden müssen?
Es geht um GPRs, nicht um SFRs.
Wenn du all diese Komplexität mit in deinem Generator unterbringen
willst, dann wird es allerdings tatsächlich kompliziert und ist mittels
BruteForce wohl auch auf einem PC nicht mehr sinnvoll lösbar.
Inzwischen habe ich genügend Constraints zusammen, um den Suchbaum hinreichend klein zu halten, von wenigen Ausreißern abgesehen.
Was noch fehlt ist die eigentliche Code-Generierung (Erzeugung der AVR-Instruktionen), aber das ist nur Schreibarbeit.
Lässt sich das nicht auf einen kürzeste-Wege-Algorithmus zurückführen?
Habe ich auch kurz drüber nachgedacht. Aber das Problem ist ja nicht, eine kürzeste Sequenz in einer vorgegebenen Menge zu finden, sondern überhaupt erst mal Kandidaten zu erzeugen. Zudem weiß man a priori nicht, wie lange eine kürzeste Sequenz sein wird. Es gibt lediglich eine weiche Obergrenze, die im Laufe des Algorithmus' (hoffentlich) immer kleiner wird.
Die beiden letzten Tests zeigen, dass die Optimierung auch über die Grenzen von Basic Blocks hinweg funktioniert. Programme, die mehr als einen Basic Block haben, als nicht praxisrelevant zu bezeichnen, zeugt nicht gerade von Erfahrung.
Wie wenn man Schweine in ein Uhrwerk schauen laesst: Da kommt halt nur
Grunzen, aber kein Verstaendnis.
OINK OINK ;-)
Ich hab zwar NULL Ahnung von C-Compilern, kann aber wohl deren Ergebnis im Fall eines AVR bewerten, denn AVR ASM kriegt ich gerade noch so auf die Reihe. Und da sehe ich relativ wenig Verbesserung. Die entscheidende Frage ist eher. Welches Optimierungspotential steckt überhaupt noch im avr gcc? Das Ding hat nun schon reichlich 20 Jahre Entwicklung hinter sich und ist, soweit ich das mit meinem begrenzten Horizont beurteilen kann, schon recht gut. Ich sehe da wenig Optimierungspotential, daß in vielen Fällen substantiell was verbessert. Diese Geschichte hier ist eher eine Fingerübung eines Compilerexperten. Man könnte ja noch 0,5% an Stellen rausholen, die 1% der Anwender nutzen . . . Die 3. Wachsschicht auf dem 5er BMW.
Die entscheidende
Frage ist eher. Welches Optimierungspotential steckt überhaupt noch im
avr gcc?
Jede Menge. Denn auch wenns den seit 20 Jahren gibt, hat wohl außer Johann niemand ernsthaft dran gearbeitet, und das Target war ja schonmal fast aus gcc rausgeflogen. Seit gcc 8 gehts ja zudem nur noch rückwärts mit der Optimierung bzgl. Codegröße. Alles, was am gcc verbessert wurde, ging in die X86/ARM-Architekturen, und bringt dem von-Neumann-Exoten AVR gar nichts.
Die Optimierung funktioniert unabhängig von der Komplexität des Codes. Was gemacht wird:
Jeder Block wird von oben nach unten durchgegangen, und es wird ausgenutzt, wenn es bekannte Werte in Registern gibt.
Es besteht die Möglichkeit, dass ein Registerwert bereits am Anfang eines Blocks bekannt ist. Dazu werden die Blöcke in reverse Post Order topologisch sortiert, um die Chance zu erhöhen, dass ein Register via aller eingehenden Kanten bekannt ist. (Die Werte von allen eingehenden Kanten müssen natürlich übereinstimmen, falls überhaupt bekannt).
Welches Optimierungspotential steckt überhaupt noch im avr gcc?
Das Ding hat nun schon reichlich 20 Jahre Entwicklung hinter sich
und ist, soweit ich das mit meinem begrenzten Horizont beurteilen
kann, schon recht gut.
Ich beschäftige mich mit dem Ding, und von daher ist meine Sicht darauf garantiert voreingenommen, weil ja Sachen im Fokus stehen, die nicht oder nur unzureichend funktionieren. Da hab ich bestimmt nen negativen Bias.
Und nicht alles is besser geworden. In wesentlichen Aspekten (Register-Allokation und Verwendung von Post-Increment etc) war die v3.4 von 2006 zum Beispiel besser als alle neuere Versionen, die SSA (Static Single Assignment) verwenden.
Ich sehe da wenig Optimierungspotential,
Das aktuelle Paradigma von Multi-Pass Compilern hat natürlich Grenzen. In GCC sind das aktuell über 300 Passes.
Wenn überhaupt sind signifikante Verbesserungen m.E. nur mit komplett anderen Paradigmen zu erreichen, zum Beispiel mit Machine Learning. Die hat aber das fundamentale Problem, dass der erzeugte Code nicht inhärent korrekt wäre -- und es auch keinen praktikablen Weg gibt, die Korrektheit a posteriori sicherzustellen (das ist grundlegend anders als zB bei AlphaGo etc, wo unvalide Züge einfach aussortiert werden können).
Welches Optimierungspotential steckt überhaupt noch im avr gcc?
Und nicht alles is besser geworden. In wesentlichen Aspekten
(Register-Allokation und Verwendung von Post-Increment etc) war die v3.4
von 2006 zum Beispiel besser als alle neuere Versionen, die SSA (Static
Single Assignment) verwenden.
Ja, aber zu DER alten Version will ja auch keiner zurück. Ich nutze noch die letzte 2010er Version regelmäßig für meinen Kram und bin damit zufrieden.
Ich sehe da wenig Optimierungspotential,
Das aktuelle Paradigma von Multi-Pass Compilern hat natürlich Grenzen.
In GCC sind das aktuell über 300 Passes.
Wenn überhaupt sind signifikante Verbesserungen m.E. nur mit komplett
anderen Paradigmen zu erreichen, zum Beispiel mit Machine Learning.
Das heißt aber im Umkehrschluß, die Kiste ist real ausgereizt und es gibt kein nennenswertes Optimierungspotential. Gut für die Anwender, sie haben einen guten, kostenlosen Compiler. Schlecht für die Entwickler, die müssen sich neue Herausforderungen suchen. Ces't la vie!
Die
hat aber das fundamentale Problem, dass der erzeugte Code nicht inhärent
korrekt wäre -- und es auch keinen praktikablen Weg gibt, die
Korrektheit a posteriori sicherzustellen (das ist grundlegend anders als
zB bei AlphaGo etc, wo unvalide Züge einfach aussortiert werden können).
Die entscheidende
Frage ist eher. Welches Optimierungspotential steckt überhaupt noch im
avr gcc?
Jede Menge.
Wirklich? Gefühlt oder real? Werd mal konkret.
Denn auch wenns den seit 20 Jahren gibt, hat wohl außer
Johann niemand ernsthaft dran gearbeitet, und das Target war ja schonmal
fast aus gcc rausgeflogen.
Nicht schön, aber am Ende verständlich, wenn sich keiner drum kümmert. Der 4004 wird vom gcc auch nicht unterstützt ;-)
Seit gcc 8 gehts ja zudem nur noch rückwärts
mit der Optimierung bzgl. Codegröße.
Man kann durchaus auch alte Versionen nutzen. Der Fetisch des dauernden Updates ist manchmal kontraproduktiv.
Alles, was am gcc verbessert wurde,
ging in die X86/ARM-Architekturen, und bringt dem von-Neumann-Exoten AVR
gar nichts.
Ist halt so, was will man daran ändern? Oder vielmehr, MUSS man daran was ändern? AVR ist auch kein Neuling mehr sondern seit über 25 Jahren sehr erfolgreich und massenhaft im Markt etabliert. Da gibt es bestenfalls Anpassungen für die neueren AVR-Kerne.
Ich sehe da schon einiges. Man könnte endlich mal den alten Zopf mit R0, R1 Doppelnutzung als Zero und SREG Sicherung abschneiden. Das ist immer ein elendiges Gefummel, weil R0 eben nicht sicher 0 ist und R1 durch MUL zerstört wird.
Z.B. auf R2, R3 umschwenken, würde alles wesentlich einfacher machen.
Man könnte auch noch ein Attribut für Interrupts als nicht unterbrechbar definieren, dann entfällt Push/Pop für die SREG Sicherung.
Man könnte endlich mal den alten Zopf mit R0, R1 Doppelnutzung
als Zero und SREG Sicherung abschneiden.
Weder R0 noch R1 ist in irgendeiner Weise mit SREG assoziiert.
Das ist immer ein elendiges Gefummel, weil R0 eben nicht sicher 0
ist und R1 durch MUL zerstört wird.
R1 enthält sicher 0 sowohl in Inline Assembler als auch am Beginn von (Assembler) Funktionen. Die einzigen Stellen, wo R1 (möglicherwise) nicht 0 enthält, sind zu Beginn einer ISR, oder wenn man Code verwendet, der nicht ABI-konform ist.
Und R0 wird nicht nur durch MUL zerstört, sondern auch an ganz vielen anderen Stellen (Load, Store, Shift, Sign-Extend, ...). Evtl. ist das, was du suchst, ein globales Register.
Man könnte auch noch ein Attribut für Interrupts als nicht unterbrechbar
definieren, dann entfällt Push/Pop für die SREG Sicherung.
Das würde nichts bringen, weil eine ISR den Inhalt von SREG nicht clobbern darf. Dafür spielt es keine Rolle, ob die ISR selbst unterbrochen wird oder nicht.
Das würde das "CLR ZERO_REG" nach (fast) jedem MUL sparen. Wozu ein zweites TMP-Register gut sein soll sehe ich jetzt nicht. Und wenn eine ISR ZERO_REG nicht braucht, dann wird es auch nicht gesichert, dito für TMP_REG:
1
#include<avr/interrupt.h>
2
3
uint8_tvolatilevx;
4
5
ISR(PCINT1_vect)
6
{
7
++vx;
8
}
wird zu:
1
00000056 <__vector_4>:
2
56: 8f 93 push r24
3
58: 8f b7 in r24, 0x3f ; SREG
4
5a: 8f 93 push r24
5
5c: 80 91 00 01 lds r24, 0x0100 ; 0x800100 <vx>
6
60: 8f 5f subi r24, 0xFF
7
62: 80 93 00 01 sts 0x0100, r24 ; 0x800100 <vx>
8
66: 8f 91 pop r24
9
68: 8f bf out 0x3f, r24 ; SREG
10
6a: 8f 91 pop r24
11
6c: 18 95 reti
SREG wird durch SUBI geclobbert und muss daher wie gesagt gesichert werden unabhängig davon, ob die ISR unterbrochen wird oder nicht. Ein spezielles (neues) fixes Register nur zur SREG-Sicherung zu verwenden bringt m.E. nicht viel. Wenn es auf jedes einzelne Tick ankommt, dann ist (Inline) Assembler dein Freund.
Z.B. auf R2, R3 umschwenken, würde alles wesentlich einfacher machen.
Der Blocker ist, dass das ein neues ABI wäre. Teile der LibC werden ungültig, dito für andere Libs wie für Arduino, oder generell Code, der Inline Asm enthält.
Dann die Frage, wie du das mit dem Startup-Code machen willst. R1 nullen oder R2? Ein Configure-Test funktioniert nicht, weil crt*.o per Device-Packs distribuiert werden kann. Binutils PR21683 setzt auch das aktuelle ABI voraus. crt*.o per Symbol zu bespaßen à la
1
.byte __0reg17, 0x24 ; CLR __0reg17 / 17
setzt voraus, dass man weiß, welches ABI aktiv ist, d.h. compiler definiert ein Symbol, das denn vom Default-Linkerskript definiert wird:
1
__0reg=DEFINED(__0reg)?__0reg:1;
2
__0reg17=DEFINED(__0reg17)?__0reg17:17*__0reg;
Ich wüsste jetzt niemand, der das Fass aufmachen möchte.
Man könnte auch noch ein Attribut für Interrupts als nicht unterbrechbar
definieren, dann entfällt Push/Pop für die SREG Sicherung.
Die würde nicht entfallen.
SREG wird nicht durch Unterbrechung überschrieben, sondern vom normalen Progammablauf durch Instruktionen, die Flags verändern.
SREG wird nicht durch Unterbrechung überschrieben, sondern vom normalen
Progammablauf durch Instruktionen, die Flags verändern.
Wird ein Interrupt nicht durch andere unterbrochen, reicht die Sicherung per IN/OUT in ein reserviertes Register (2 Zyklen) für alle Interrupts aus.
Erste bei Unterbrechbarkeit ist zusätzliches PUSH/POP (+ 4 Zyklen) notwendig.
Hier mal der Overhead, inklusive der Zero-Reg Arie:
