Was heisst das bitte : --max-allocs-per-node 100000

[Peter B. (funkheld)]

Hallo, guten Tag.

Was heisst das bitte beim Compiler SDCC.
Ich spiele mit dem ZX Spectrum 128.
-------------------------
sdcc -mz80 --reserve-regs-iy --opt-code-speed --max-allocs-per-node 
100000 --code-loc 0x8000 --data-loc 0 --no-std-crt0 crt0.rel
-------------------------

Diesen Text verstehe ich nicht für das oben beschriebene:
https://www.embeddedrelated.com/showthread/comp.arch.embedded/225684-1.php

Wer kann das bitte einmal Technisch erklären was da gemacht wird?

Danke.

[Klaus W. (mfgkw)]

Peter B. schrieb:
> Hallo, guten Tag.
>
> Was heisst das bitte beim Compiler SDCC.
> Ich spiele mit dem ZX Spectrum 128.
> -------------------------
> sdcc -mz80 --reserve-regs-iy --opt-code-speed --max-allocs-per-node
> 100000 --code-loc 0x8000 --data-loc 0 --no-std-crt0 crt0.rel
> -------------------------
>
> Diesen Text verstehe ich nicht für das oben beschriebene:
> https://www.embeddedrelated.com/showthread/comp.arch.embedded/225684-1.php
>
> Wer kann das bitte einmal Technisch erklären was da gemacht wird?
>
> Danke.

http://sdcc.sourceforge.net/doc/sdccman.pdf sagt dazu:

--max-allocs-per-node Setting this to a high value will result in 
increased compilation time and more optimized code being generated. 
Setting it to lower values speed up compilation, but does not optimize 
as much.The default value is 3000.  This option currently only affects 
the hc08, s08, z80, z180, r2k, r3ka and gbz80 ports.

Weiter hinten kommt dann:
8.1.15    Register Allocation
SDCC currently has two register allocators.  One of them is optimal when 
optimizing for code size.  This register allocator is used by default on 
the hc08, s08, z80, z180, ez80_z80, r2k, and r3ka ports. For the gbz80, 
stm8,pdk13, pdk14 and pdk15 ports it is the only available register 
allocator. Even though it runs in polynomial time, it can bequite slow; 
therefore the--max-allocs-per-node command line option can be used for a 
trade-off between compilation speed and quality of the generated code: 
Lower values result in faster compilation, higher values can result in 
better code being generated. It first creates a tree-decomposition of 
the control-flow graph, and then uses dynamic programming bottom-up 
along the tree-decomposition.  Optimality is achieved through the use of 
a cost function, which gives cost for instructions under register 
assignments.  The cost function is target-specific and has to be 
implemented for each port; in all current SDCC ports the cost function 
is integrated into code generation. For more details on how this 
register allocator works, see: Philipp Klaus Krause, ”Optimal Register 
Allocationin Polynomial Time”, Compiler Construction - 22nd 
International Conference, CC 2013, Held as Part of the European Joint 
Conferences on Theory and Practice of Software, ETAPS 2013. Proceedings, 
Lecture Notes in Computer Science, volume 7791, pp. 1-20. Springer, 
2013. Also: Philipp Klaus Krause, ”Bytewise Register Allocation”, 
Pro-ceedings of the 18th International Workshop on Software and 
Compilers for Embedded Systems, SCOPES ’15, pp22–27. Association for 
Computing Machinery, 2015.

Wenn man es nicht versteht, ist es auch nicht schlimm - geht ums 
Optimieren.

[Peter B. (funkheld)]

Es betrifft also nur den Code genauer machen ? und hat nichts mit 
irgendeiner Speicherreservierung im ZX Specrum zu tun ?

Danke.

[Fpgakuechle K. (Gast)]

Peter B. schrieb:
> Was wird da bitte optiemiert?

Der Speicherort der Variablen, mglw.!?

Also welche variable kann in einem CPU-Register gehalten werden und was 
muss auf den Stack (und braucht dann ein mehrfaches an Takten zum Lesen 
und schreiben.

https://de.wikipedia.org/wiki/Registerzuteilung
https://www.tcs.ifi.lmu.de/lehre/ws-2011-12/compiler_alt/folien-11.pdf
https://ls12-www.cs.tu-dortmund.de/daes/media/documents/teaching/courses/ws0910/cb/cb-falk-7.pdf

Wer register allocation und spilling nicht kennt oder nicht sauber 
implementieren kann, steht schnell auf Linus seiner 'Abschussliste'.
https://www.bitblokes.de/linus-torvalds-nennt-gcc-4-9-grosse-scheisse-und-warnt-vor-einer-benutzung/

[Fpgakuechle K. (Gast)]

Peter B. schrieb:
> Es betrifft also nur den Code genauer machen ? und hat nichts mit
> irgendeiner Speicherreservierung im ZX Specrum zu tun ?

Njein, Register sind auch Speicher. Und der Code wird nicht genauer, 
sondern schneller mit der Richtigen Registerallocation.

Aber es stimmt schon, es sollte nicht mit malloc() (Memory-Allocation) 
verwechselt werden.

Wobei die Frage ist, wieviel CPU-Register der Z80 überhaupt hat und ob 
daher eine Optimierung diesbezüglich lohnt.
http://www.righto.com/2014/10/how-z80s-registers-are-implemented-down.html

[Fpgakuechle K. (Gast)]

BTW: Da das eine Frage ist, die mit Wissen aus dem Fach 'Compilerbau' zu 
beantworten ist, wäre vielleicht die (Softwerker-) Kategorie 
https://www.mikrocontroller.net/forum/gcc

besser geeignet als dieses (Elektroniker/Hardwerker) Forum 
"Mikrocontroller und Digitale Elektronik".

[Philipp Klaus K. (pkk)]

Peter B. schrieb:
> Hallo, guten Tag.
>
> Was heisst das bitte beim Compiler SDCC.
> Ich spiele mit dem ZX Spectrum 128.
> -------------------------
> sdcc -mz80 --reserve-regs-iy --opt-code-speed --max-allocs-per-node
> 100000 --code-loc 0x8000 --data-loc 0 --no-std-crt0 crt0.rel
> -------------------------
>
> Diesen Text verstehe ich nicht für das oben beschriebene:
> https://www.embeddedrelated.com/showthread/comp.arch.embedded/225684-1.php
>
> Wer kann das bitte einmal Technisch erklären was da gemacht wird?
>
> Danke.

-mz80: Erzeuge Code für Z80.

--reserve-regs-iy: Benutze Registerpaar iy nicht (ich kenne den ZX 
Spectrum 128 nicht - eventuell ist iy dort für ein BIOS oder OS 
reserviert?).

--opt-code-speed: Im Zweifelsfalle optimiere auf möglichst schnellen 
Code, ohne sehr auf Codegröße zu achten.

--code-loc 0x8000: Das Programm soll ab Adresse 0x8000 im Adressraum 
liegen.

--data-loc 0: Der RAM und damit die globalen variablen liegt ab Adresse 
0 im Adressraum.

--no-std-crt0: Verwende nicht die crt0 von SDCC (sondern eine für den ZX 
Spectrum 128 - wohl die direkt darauf angegebene crt0.rel).

--max-allocs-per-node 100000: Gibt an, wie viele Teilergebnisse in 
Berechnungen in manchen Optimierungen berücksichtigt werden sollen. 
Größere Werte führen üblicherweise zu besserem (schnellerem, kleinerem) 
Code, aber SDCC braucht mehr Zeit und Speicher während des Kompilierens. 
3 Optimierungen sind davon betroffen, bei weitem am wichtigsten darunter 
ist aber die Registerallokation.

[Philipp Klaus K. (pkk)]

Fpgakuechle K. schrieb:
> Wobei die Frage ist, wieviel CPU-Register der Z80 überhaupt hat und ob
> daher eine Optimierung diesbezüglich lohnt.
> http://www.righto.com/2014/10/how-z80s-registers-are-implemented-down.html

SDCC verwendet die Register des Z80 wie folgt:

ix: Dieses 16-Bit-Register wird ausschließlich als Framepointer 
verwendet.

a, bc, de, hl, iy: Diese insgesamt 9 Bytes an Registern stehem dem 
Registerallokator zur Verfügung, und können relativ frei verwendet 
werden:

a', bc', de', hl': Diese Register werden von SDCC nicht verwendet. Eine 
dadurch mögliche Nutzung ist für schnelle Interruptroutinen: statt die 
Register af, bs, de, hl auf den Stack zu speichern, können mittels ex 
af, af' und exx innerhalb der Routine die Register a', bc', de', hl' 
verwendet werden.

Gerade aufgrund der geringen Anzahl an Registern und der 
nichtorthogonalen Architektur (d.h. bestimmte Befehle lassen nur 
bestimmte Register als Operanden zu oder sind schneller / effizienter 
für bestimmte Operanden) ist ein guter Registerallokator beim Z80 
wichtig.

[peter bierbach (Gast)]

Ja danke für die ausführliche Erklärung.

Gruss

[Fpgakuechle K. (Gast)]

Philipp Klaus K. schrieb:
> Fpgakuechle K. schrieb:
>> Wobei die Frage ist, wieviel CPU-Register der Z80 überhaupt hat und ob
>> daher eine Optimierung diesbezüglich lohnt.

> Gerade aufgrund der geringen Anzahl an Registern und der
> nichtorthogonalen Architektur (d.h. bestimmte Befehle lassen nur
> bestimmte Register als Operanden zu oder sind schneller / effizienter
> für bestimmte Operanden) ist ein guter Registerallokator beim Z80
> wichtig.

Stimmt natürlich auch, verlangt eben das man einiges an Rechenleistung 
in den Compiler steckt. Die für den Compilerbauer einfachere Variante 
ist natürlich die Variblen in den Memory zu packen. Jedenfalls sieht 
mancher dissassemblierte Code stark danach aus.

Mich würden mal Erfahrungswerte interessieren, um wieviel schneller ein 
(Alltags-) C-Code durch gute Registerwahl/-optimierung wird.

Mich wundert etwas, das der Akku A mit bei der Optimierung betrachtet 
wird, weil dessen Verwendung bei den Arithmetikbefehlen 'unausweichlich' 
ist.

> statt die
> Register af, bs, de, hl auf den Stack zu speichern, können mittels ex
> af, af' und exx innerhalb der Routine die Register a', bc', de', hl'
> verwendet werden.

Ja, 'mein' Buch weiß das ;-) siehe Anhang.

[Philipp Klaus K. (pkk)]

Fpgakuechle K. schrieb:
>
> Mich würden mal Erfahrungswerte interessieren, um wieviel schneller ein
> (Alltags-) C-Code durch gute Registerwahl/-optimierung wird.

Aus der Anfangszeit, des aktuell in SDCC verwendeten Registerallokators, 
also nicht mehr ganz aktuell:

https://www.semanticscholar.org/paper/Optimal-Register-Allocation-in-Polynomial-Time-Krause/085a44a84ce12b0c1e2594e655beb50451c93312

Wenn man sich dort Abbildungen 3 und 5 ansieht, erkennt man wie sich der 
Parameter für --max-allocs-per-node auf die Codegröße auswirkte.

Auch dass SDCC für STM8 im Vergleich zu anderen Compilern recht guten 
Code generiert (http://www.colecovision.eu/stm8/compilers.shtml) liegt 
zum Großteil an besserer Registerallokation.

> Mich wundert etwas, das der Akku A mit bei der Optimierung betrachtet
> wird, weil dessen Verwendung bei den Arithmetikbefehlen 'unausweichlich'
> ist.
>

Dennoch kann es z.B. sinnvoll sein, das Ergebnis einer Berechnung teils 
in a zu speichern, wenn die danach einige folgen, die a nicht benötigen 
(z.B. weil sie nur Ladebefehle verwenden, oder für Arithmetik add hl, ss 
etc verwenden).

Mehr Flexibilität bei der Registerallokation, insbesondere auch bei der 
Verwendung von a und iy war ein wichtiger Aspekt beim Erreichen der 
Verbesserungen des erzeugten Codes für Z80 in den letzten Jahren in 
SDCC.