WEBVTT
00:00:00.000 --> 00:00:09.705
32C3 Vorspannmusik
00:00:09.715 --> 00:00:14.550
Herald: Dann ist es mir jetzt eine ganz
besondere Freude Matthias Koch
00:00:14.550 --> 00:00:21.200
vorzustellen. Der wird über Compiler
Optimierung für Forth im Microcontroller
00:00:21.200 --> 00:00:25.140
sprechen. Bitte einen warmen
Applaus für Matthias.
00:00:25.140 --> 00:00:31.270
Applaus
00:00:31.270 --> 00:00:35.719
Matthias: Guten Tag, Hallo. Wie gesagt
Compileroptimierung für Forth im
00:00:35.719 --> 00:00:40.190
Microcontroller und ganz zur Eröffnung
habe ich eine Frage: Wer von euch kennt
00:00:40.190 --> 00:00:46.350
Forth eigentlich schon? Okay, so etwa die
Hälfte. Das bedeutet aber ich sollte
00:00:46.350 --> 00:00:50.480
besser noch einmal kurz erklären was
diese Sprache eigentlich ausmacht. Es ist
00:00:50.480 --> 00:00:56.059
eine Sprache die auf dem Modell eines
Stacks basiert. Vielleicht kennt ihr
00:00:56.059 --> 00:01:00.840
die umgekehrte polnische Notation wo es so
ist das erst die Parameter kommen und dann
00:01:00.840 --> 00:01:04.209
die Operatoren. Man legt also Werte auf
den Stack und von oben kommen die
00:01:04.209 --> 00:01:08.670
Operatoren, nehmen sich ewas und berechnen
ewas und legen es wieder darauf. Es gibt
00:01:08.670 --> 00:01:12.640
noch einen zweiten Stack, den Return-Stack
worüber die Rücksprungadressen
00:01:12.640 --> 00:01:17.200
gehandhabt werden. Das bedeutet man kann
nacheinander die verschiedenen Operatoren
00:01:17.200 --> 00:01:22.950
aufrufen und muss nicht wie bei C den
Stackframe hin und her kopieren. Der
00:01:22.950 --> 00:01:28.120
Compiler selbst ist sehr simpel aufgebaut.
Es basiert darauf, dass man den Eingabestrom
00:01:28.120 --> 00:01:34.470
was der Mensch tippt, in Wörter zerhackt,
also ein Space, Tabulator, Zeilenumbruch.
00:01:34.470 --> 00:01:38.050
Wenn ein Wort gefunden wird, wird es in
der Liste der bekannten Wörter gesucht
00:01:38.050 --> 00:01:42.710
entweder ausgeführt oder compiliert und
wenn es nicht gefunden werden kann wird es
00:01:42.710 --> 00:01:46.740
als Zahl interpretiert, auf den Stack
gelegt, oder es wird etwas kompiliert um
00:01:46.740 --> 00:01:49.950
diese Zahl dann später auf den Stack zu
legen. Das war eigentlich schon die
00:01:49.950 --> 00:01:54.820
Sprache. Das Besondere daran ist, dass
sie klein genug ist, dass sie in einem
00:01:54.820 --> 00:01:59.450
Mikrocontroller installiert werden kann.
Was dazu führt das man dann mit einem
00:01:59.450 --> 00:02:04.380
Terminal mit seinem Chip sprechen kann und
von innen heraus ausprobieren, ob der
00:02:04.380 --> 00:02:07.779
Hardwarecode funktioniert, weil man dann
nicht viele kleine Testprogramme schreiben
00:02:07.779 --> 00:02:11.800
muss, sondern ganz einfach von Hand an den
Leitungen wackeln kann und alle
00:02:11.800 --> 00:02:16.730
Definitionen die man geschrieben hat auch
sofort interaktiv ausprobieren kann. Das
00:02:16.730 --> 00:02:20.220
führt dann auch dazu, dass die
Definitionen natürlich gleich in der
00:02:20.220 --> 00:02:24.640
Hardware läuft und auch gleich mit
Echtzeit, so dass man die Fehlersuche
00:02:24.640 --> 00:02:31.784
stark vereinfachen kann. Das ist so ein
bisschen eine Einführung in Forth.
00:02:31.784 --> 00:02:34.640
Ich selbst habe diese Sprachen nicht
erfunden, die gibt es schon seit mehr als
00:02:34.640 --> 00:02:36.290
einem halben Jahrhundert.
00:02:36.290 --> 00:02:41.220
Aber ich habe Compiler geschrieben
für MSP430, ARM Cortex M0, M3
00:02:41.220 --> 00:02:46.910
und M4, M7 ist in Planung und es gibt noch
eine Variante, die in Zusammenarbeit mit dem
00:02:46.910 --> 00:02:50.720
Bowman gemacht habe, die auf einem
FPGA läuft. Aber dazu ein bisschen mehr
00:02:50.720 --> 00:02:55.200
später. Eigentlich ist das ungewöhnlich
sich selbst vorzustellen aber meine
00:02:55.200 --> 00:02:58.920
Freunde meinen das sollte man sagen. Ich
bin Diplomphysiker und habe Physik mit
00:02:58.920 --> 00:03:03.870
Nebenfach Gartenbau studiert, bin gerade in
meiner Doktorarbeit in der Laserspektroskopie
00:03:03.870 --> 00:03:08.030
habe gemischte Interessen durcheinander,
besonders Radionavigation
00:03:08.030 --> 00:03:12.400
und meine Lieblingssprachen
kann man hier sehen.
00:03:12.400 --> 00:03:17.010
Der Name mag vielleicht etwas ungewöhnlich
sein, aber die erste unterstützte
00:03:17.010 --> 00:03:22.550
Plattform war der MSP430 von MSP und
"écris" aus dem französischen kam der
00:03:22.550 --> 00:03:26.940
Name dann. Überschreibt den MSP430
weil es da innen drin ist und man schreibt
00:03:26.940 --> 00:03:32.600
direkt hinein. Unterstützt dann alle
MSP430-Launchpads, sehr viele ARM Cortex
00:03:32.600 --> 00:03:39.590
Architekturen und mit dem FPGA ein
bisschen mehr. Die klassischen
00:03:39.590 --> 00:03:44.120
Architekturen, also die auf denen Forth
normalerweise implementiert worden ist
00:03:44.120 --> 00:03:48.020
– so geschichtlich – waren eine virtuelle
Maschine. Wo eine Liste von Pointern
00:03:48.020 --> 00:03:52.850
drinen war, wo nacheinander diese Pointer
genommen worden sind und dann entweder wie
00:03:52.850 --> 00:03:58.560
eine Liste von Pointern zählten oder
aber eben ein Assemblerprimitive.
00:03:58.560 --> 00:04:03.490
Natürlich ist das sehr schön, wenn man
dann Fehler suchen möchte im Compiler, es
00:04:03.490 --> 00:04:06.770
wird sehr einfach dadurch und es lassen
sich auch einige ungewöhnliche Sachen
00:04:06.770 --> 00:04:12.989
dabei implementieren. Aber es frisst
viele viele Taktzyklen. Die ganz alten
00:04:12.989 --> 00:04:18.238
Systeme hatten sogar die Möglichkeit noch
einmal über eine Tabelle die ganzen
00:04:18.238 --> 00:04:22.550
verschiedenen Pointer umzuleiten, so dass
man Definitionen die schon liefen
00:04:22.550 --> 00:04:27.040
nachträglich noch ändern konnte, also
eine Definition ganz tief im System durch
00:04:27.040 --> 00:04:30.690
etwas neues austauschen. Die wird dann
sofort auch verwendet. Das ging mal.
00:04:30.690 --> 00:04:33.970
Ausserdem lässt sich Forth sehr leicht
dekompilieren, zumindest bei der
00:04:33.970 --> 00:04:39.250
klassischen Implementation, so das bei
einer Jupiter Ace. Man braucht ja keine
00:04:39.250 --> 00:04:43.749
Quelltexte, man hatte den Objektcode, man
konnte ihn desassemblieren zurück in den
00:04:43.749 --> 00:04:50.160
Quelltext, ändern und neu kompilieren
fertig. Die Optimierungen, die ich jetzt
00:04:50.160 --> 00:04:54.630
vorführen werde, zerstören diesen
interessanten Aspekt, weil da Maschinencode
00:04:54.630 --> 00:04:57.200
heraus kommt und weil da
auch Teile weg optimiert werden.
00:04:57.200 --> 00:05:00.340
Es gibt also nicht mehr so den eins zu eins
Zusammenhang zwischen dem was man
00:05:00.340 --> 00:05:04.580
geschrieben hat und dem was hinterher
tatsächlich im Prozessor ausgeführt wird.
00:05:04.580 --> 00:05:08.120
Anders herum jedoch, hatte Forth
lange auch mit dem Problem zu kämpfen,
00:05:08.120 --> 00:05:13.090
dass es immer auch ein bisschen langsam galt.
Das habe ich geändert. Und ich möchte
00:05:13.090 --> 00:05:17.950
gerne heute vorstellen was für
Optimierungen man im Chip selbst
00:05:17.950 --> 00:05:22.940
durchführen kann, natürlich aus der
Compilertheorie heraus sind das alles alte
00:05:22.940 --> 00:05:28.320
Hüte. Aber die meisten Compiler brauchen
sehr viel Speicher, laufen auf einem PC wo
00:05:28.320 --> 00:05:31.980
es ja fast unbegrenzt davon gibt. Ich
möchte aber einmal herausfinden welche
00:05:31.980 --> 00:05:35.840
Optimierungen man in den Arbeitsspeichern
eines kleinen Microcontrollers
00:05:35.840 --> 00:05:42.260
implementieren kann. Dazu gehören
Tail-Call, Konstantenfaltung, Inlining,
00:05:42.260 --> 00:05:48.190
Opcodierung und die Registerallokation. In
welcher Architektur diese jeweils
00:05:48.190 --> 00:05:51.880
implementiert sind steht da mit bei.
Nun will ich die ganzen einzelnen
00:05:51.880 --> 00:05:57.030
Optimierungen einmal vorstellen. Tail-Call
ist relativ simpel. Wenn das letzte in
00:05:57.030 --> 00:06:01.310
einer Routine ein Call ist und danach
direkt ein Return kommt, dann kann man das
00:06:01.310 --> 00:06:04.919
auch durch einen Sprungbefehl ersetzen.
man braucht dann nicht den Umweg über den
00:06:04.919 --> 00:06:09.030
Stack zu nehmen. Das ist eigentlich so
weit klar, nichts besonderes.
00:06:09.030 --> 00:06:14.500
Konstantenfaltung bedeutet: Manchmal
möchte man als Mensch etwas so schreiben,
00:06:14.500 --> 00:06:19.970
dass man ein paar Konstanten nimmt, die
multipliziert, zusammen verodert; all das
00:06:19.970 --> 00:06:23.320
immer mit zu kompilieren wäre ja
eigentlich Zeitverschwendung. Es steht ja
00:06:23.320 --> 00:06:28.530
schon während der Kompilierung fest, was
das Ergebnis dieser Berechnung sein wird,
00:06:28.530 --> 00:06:32.041
der Compiler kann also durchaus diese
Rechnung schon während dem kompilieren
00:06:32.041 --> 00:06:36.080
durchführen, nur noch das Ergebnis
einkompilieren. Hier sieht man mal ein
00:06:36.080 --> 00:06:40.880
kleines Beispiel, also Sechs auf dem Stack
legen, Sieben auf den Stack legen, beide
00:06:40.880 --> 00:06:44.910
Werte vertauschen, miteinander
multiplizieren und das ganze dann
00:06:44.910 --> 00:06:50.710
aufsummieren. Eigentlich stehen die ersten
Teile schon fest, das reicht wenn man 42
00:06:50.710 --> 00:06:54.919
plus kompilieren würde. Das ist die
Konstantenfaltung. Das ist jetzt ein
00:06:54.919 --> 00:06:59.230
glasklarer Fall, wo man das direkt sieht,
aber manchmal gibt es auch aus anderen
00:06:59.230 --> 00:07:02.210
Optimierungen heraus noch die
Möglichkeit, dass Konstantenfaltungen
00:07:02.210 --> 00:07:08.930
möglich werden kann. Das ist dann nicht
mehr ganz so offensichtlich. Dazu, wie das
00:07:08.930 --> 00:07:12.270
implementiert wird, möchte ich erst
einmal kurz zeigen wie der klassische
00:07:12.270 --> 00:07:17.500
Forth Compiler implementiert worden ist.
Es war so, dass der Eingabestrom den der
00:07:17.500 --> 00:07:22.790
Benutzer eingetippt hat in einzelne
Wörter, in Tokens zerhackt worden ist,
00:07:22.790 --> 00:07:27.020
dann wurde geprüft ob es in der Liste der
bekannten Definitionen auftaucht, oder
00:07:27.020 --> 00:07:31.580
eben auch nicht. Ist das der Fall, ist die
Frage ob kompiliert werden soll oder
00:07:31.580 --> 00:07:35.040
nicht. Es gibt einen Ausführ- und
einen Kompiliermodus, der eine interaktive
00:07:35.050 --> 00:07:40.449
Sprache. Im Kompiliermodus und was nicht
immer geht das – auch eine Spezialität
00:07:40.449 --> 00:07:44.930
von Forth. Dann wird ein Aufruf in der
Definition einkompiliert, also ein Call
00:07:44.930 --> 00:07:49.259
Befehl geschrieben. Immediate bedeutet
übrigens, dass etwas das kompiliert
00:07:49.259 --> 00:07:53.749
werden soll selbst ausgeführt wird. Das
braucht man für Kontrollstrukturen, die
00:07:53.749 --> 00:07:58.480
dann noch so Sprünge handhaben müssen
und ähnliches und ansonsten ist man im
00:07:58.480 --> 00:08:02.600
Ausführmodus, wird die Definition
ausgeführt. Nichts gefunden: Versucht man
00:08:02.600 --> 00:08:07.020
es als Zahl zu interpretieren und je
nachdem ob kompiliert werden soll oder
00:08:07.020 --> 00:08:11.509
nicht, wird auf den Stack gelegt oder es
wird etwas kompiliert, was die Zahl dann
00:08:11.509 --> 00:08:15.289
bei der Ausführung auf den Stack legen
wird. Wenn es auch keine gültige Zahl
00:08:15.289 --> 00:08:21.380
ist, ist es ein Fehler. Um dort
Konstantenfaltung einzfügen sind keine so
00:08:21.380 --> 00:08:25.319
großen Änderungen nötig. Wichtig ist
jetzt eigentlich nur, dass man die
00:08:25.319 --> 00:08:30.419
Konstanten nicht kompiliert, zumindest
nicht gleich, sondern erst einmal sammelt
00:08:30.419 --> 00:08:35.000
und dann wenn eine Operation kommt die bei
konstanten Eingaben auch konstante
00:08:35.000 --> 00:08:41.220
Ausgaben produziert, diese dann
auszuführen. Die Änderungen sind so,
00:08:41.220 --> 00:08:46.620
dass jetzt ganz am Anfang der aktuelle
Stackfüllstand gemerkt werden muss, denn
00:08:46.620 --> 00:08:50.750
man muss ja auch wissen, wie viele
Konstanten gerade zur Verfügung stehen.
00:08:50.750 --> 00:08:54.640
Soll es ausgeführt werden, wurde es
gefunden, dann brauchen wir keine
00:08:54.640 --> 00:08:58.330
Konstantenfaltung machen, dann schmeißen
wir den Pointer wieder weg, alles gut,
00:08:58.330 --> 00:09:03.990
vergessen wir. Sind wir im Kompiliermodus,
wird geprüft ob diese Definition mit
00:09:03.990 --> 00:09:08.540
konstanten Eingaben auch eine konstante
Ausgabe produzieren kann und wenn ja, sind
00:09:08.540 --> 00:09:13.740
genug dafür vorhanden. Eine Invertierung
einer Zahl braucht eine Konstante. Eine
00:09:13.740 --> 00:09:18.899
Addition braucht zwei Konstanten usw. das
muss geprüft werden. Wenn das gut geht
00:09:18.899 --> 00:09:22.960
kann sie ausgeführt werden. Sie lässt
dann die Ergebnisse dort liegen und
00:09:22.960 --> 00:09:26.280
dadurch, dass wir wusten wo der
Stackpointer vorher gewesen ist, wissen
00:09:26.280 --> 00:09:30.650
wir auch wie viele Konstanten danach noch
auf dem Stack liegen geblieben sind. Es
00:09:30.650 --> 00:09:37.610
kann also durchaus variabel viele
Ausgabekonstanten produzieren. Ist diese
00:09:37.610 --> 00:09:42.750
Definition jedoch nicht faltbar, dann
bleibt uns nichts anderes übrig, als
00:09:42.750 --> 00:09:46.470
alles was dort an Konstanten liegt
einzukompilieren und dann einen
00:09:46.470 --> 00:09:51.820
klassischen Call Befehl zu machen. Ja,
aber man kann den klassischen Callbefehl
00:09:51.820 --> 00:09:54.760
auch nochmal ein bisschen abwandeln. Man
kann kucken ob da eine sehr kurze
00:09:54.760 --> 00:09:59.480
Definition ist und dann Opcodes direkt
einfügen und bei Forth natürlich
00:09:59.480 --> 00:10:04.029
Imediate überprüfen was bedeutet, dass
diese Definition selber irgendwelche
00:10:04.029 --> 00:10:11.320
Spezialfälle umsetzen kann. Nicht
gefunden, Zahlen bleiben stets auf dem
00:10:11.320 --> 00:10:17.269
Stack liegen, damit sie halt später in
die Konstantenfaltung rein kommen können.
00:10:17.269 --> 00:10:21.000
Wichtig dabei ist zu wissen, dass dabei,
während die Zahlen gesammelt werden, ja
00:10:21.000 --> 00:10:26.380
schon ein Merker in den Stack gesetzt
wurde um den Füllstand zu bestimmen. Ist
00:10:26.380 --> 00:10:31.110
es nicht als Zahl zu interpretieren, ist
es ein Fehler. Das ist im Prinzip der
00:10:31.110 --> 00:10:34.960
Kerngedanke um Konstantenfaltung in Forth
zu implementieren. Das hier ist
00:10:34.960 --> 00:10:40.580
grundsätzlich auf jeder Architektur
möglich wo Forth läuft und ist auch
00:10:40.580 --> 00:10:45.710
relativ unabhängig davon wie das Forth
innen drin implementiert hat. Ich habe
00:10:45.710 --> 00:10:50.600
schon gesehen, dass jemand Matthias Troote
(?) von der MForth für AVR, angefangen hat
00:10:50.600 --> 00:10:54.119
das auch einzubauen und das noch
zusammen recognizern. Also es geht recht
00:10:54.119 --> 00:11:00.120
gut, es ist auch Standardkonform. Die
nächste Sache: Inlining. Klar macht der
00:11:00.120 --> 00:11:05.399
C-Kompiler auch. Kurze Definitionen die
nur ein paar Opcodes haben, können mit
00:11:05.399 --> 00:11:09.640
einigen Vorsichtsmaßregeln auch direkt
eingefügt werden, denn wozu sollte man
00:11:09.640 --> 00:11:14.810
einen Call wohin tun, wenn die Opcodes
kürzer sind als der Call selbst. Und hier
00:11:14.810 --> 00:11:18.580
das Beispiel von Plus. Man ruft nicht
die primitive vom Plus auf wenn man den
00:11:18.580 --> 00:11:24.940
Plus-Opcode direkt einfügen kann. Das
leuchtet eigentlich auch ein.
00:11:24.940 --> 00:11:28.430
Opcodierungen - ich nenne es mal so, ich
weiß nicht wie es sonst genannt werden
00:11:28.430 --> 00:11:34.550
soll – ist, wenn ein Opcode eine Konstante
direkt in sich aufnehmen kann. Dann ist es
00:11:34.550 --> 00:11:39.000
doch sinnvoller die Konstante direkt mit
zu opcodieren, als sie über den Stack zu
00:11:39.000 --> 00:11:42.760
legen und dann darüber zu verwenden. Man
spart halt ein paar Takte und ein bisschen
00:11:42.760 --> 00:11:48.969
Platz. Das hängt davon ab was für einen
Prozessor man hat. Beim MSP430 geht das
00:11:48.969 --> 00:11:53.469
immer wunderbar, bei einem Cortex
manchmal, der hat nur einige Opcodes die
00:11:53.469 --> 00:11:58.800
Konstanten können und wenn man einen
Stackprozessor hat, geht das gar nicht.
00:11:58.800 --> 00:12:03.029
Und der Regsiterallokator schließlich,
ist die Überlegung, dass man
00:12:03.029 --> 00:12:07.269
Zwischenergebnisse, die bei Forth
traditionell auf dem Stack liegen würden,
00:12:07.269 --> 00:12:11.220
versucht auf Register abzubilden. Denn
klar in der Stacksprache ist das ganz
00:12:11.220 --> 00:12:15.760
etwas anderes als einen Prozessor der
hauptsächlich mit Registern arbeitet.
00:12:15.760 --> 00:12:19.329
Beim ARM Cortex ist das ganz besonders
schlimm, denn er kann nicht direkt in den
00:12:19.329 --> 00:12:23.529
Speicher zugreifen um da irgend etwas zu
berechnen, sondern er muss auf jeden Fall
00:12:23.529 --> 00:12:28.260
immer aus dem Speicher in Register holen,
im Register etwas machen und in den
00:12:28.260 --> 00:12:32.760
Speicher zurück schreiben. Das ist
ziemlich aufwendig. Wenn man das abkürzen
00:12:32.760 --> 00:12:36.240
kann, die Zwischenergebnisse gleich im
Register hält, kann man viel kürzere
00:12:36.240 --> 00:12:40.550
Befehlssequenzen nutzen, die direkt
zwischen den Registern arbeiten.
00:12:40.550 --> 00:12:44.660
Wichtig dabei ist noch, dass das ganze
transpartent wird für den Programmierer,
00:12:44.660 --> 00:12:48.740
wenn man also etwas macht, wo die logische
Struktur des Stacks sichtbar wird oder
00:12:48.740 --> 00:12:53.329
sichtbar werden könnte, muss der Compiler
auf jeden Fall zurück fallen und alles in
00:12:53.329 --> 00:12:57.060
den richtigen Stack rein schreiben, so
dass man dann auch direkt im Stack
00:12:57.060 --> 00:13:01.120
Manipulation machen kann, wenn das denn
mal notwendig ist und das ist bei Forth
00:13:01.120 --> 00:13:06.150
ziemlich häufig, weil Forth Programmierer
gerne alle möglichen Tricks anwenden.
00:13:10.470 --> 00:13:15.800
Das wesentliche für den Registerallokator
ist, zu wissen wo welches Element gerade
00:13:15.800 --> 00:13:20.000
ist, man muss also während der
Kompilierung ein Stackmodell mit laufen
00:13:20.000 --> 00:13:24.930
lassen, worin vermerkt ist, wo diese Stack-
elemente eigentlich gerade sind. Sind sie
00:13:24.930 --> 00:13:29.490
noch auf dem Stack selbst, also im
Arbeitsspeicher? Sind sie gerade in einem
00:13:29.490 --> 00:13:35.010
Register drin? Wenn ja, in welchem? Oder,
wenn neue Zwischenergebnisse auftreten:
00:13:35.010 --> 00:13:38.750
Haben wir noch genug Register? Denn wenn
mehr Zwischenergebnisse da sind als
00:13:38.750 --> 00:13:41.930
Register zur Verfügung stehen, dann
müssen die Register wieder in den
00:13:41.930 --> 00:13:46.930
Arbeitsspeicher auf den Stack geschrieben
werden und das ist es was innen drin das
00:13:46.930 --> 00:13:54.499
besondere ausmacht. Man kann es sehr klein
implementieren, aber man muss daran
00:13:54.499 --> 00:13:58.520
denken, dass das sehr seltsam ist,
dass das im Microcontroller läuft,
00:13:58.520 --> 00:14:03.010
normalerweise gibt es bei Register-
allokatoren viele Algorithmen drum herum,
00:14:03.010 --> 00:14:06.240
die überlegen, wie man das
möglichst gut über möglichst weite
00:14:06.240 --> 00:14:10.559
Strecken im Programm machen kann. Ich habe
es sehr einfach gemacht. An den Stellen wo
00:14:10.559 --> 00:14:15.250
Kontrollstrukturen verzweigen hört man
einfach auf. Man schreibt dann alles in
00:14:15.250 --> 00:14:19.371
den Stack und fertig. Ist eine sehr simple
Implementation und globale Optimierung
00:14:19.371 --> 00:14:24.980
habe ich gar nicht drin. Aber es ist ein
Anfang. Das sind jetzt all die
00:14:24.980 --> 00:14:29.950
Optimierungen die angesprochen werden
sollen. Nun will ich ein paar Beispiele
00:14:29.950 --> 00:14:34.420
dafür zeigen. Erst einmal muss ich aber
noch sagen: Mercrisp-Ice ist nicht allein
00:14:34.420 --> 00:14:38.920
meine Arbeit sondern basiert auf vielen
vielen anderen schönen Sachen die auch
00:14:38.920 --> 00:14:43.720
vorgestellt worden sind. James Bowman hat
den J1 Prozessor entwickelt. Clifford
00:14:43.720 --> 00:14:48.509
Wolf, Cotton Seed und Mathias Lasser haben
die erste freie Toolchain für FPGAs
00:14:48.509 --> 00:14:55.570
entwickelt und darauf basiert das alles.
Da drin habe ich die Konstantenfaltung,
00:14:55.570 --> 00:15:00.930
automatisches Inline kurzer Definitionen
und Tail-Call-Optimierung. Hier ist jetzt
00:15:00.930 --> 00:15:05.220
mal ein kleines Beispiel. Das ist noch
aus der LEDcom Implementation, wie man
00:15:05.220 --> 00:15:08.750
über eine Leuchtdiode kommunizieren kann.
Für die die jetzt nicht bei der Assembly
00:15:08.750 --> 00:15:13.399
gesehen haben, es ist so, dass man eine
Leuchtdiode nicht nur zum Leuchten sondern
00:15:13.399 --> 00:15:17.190
auch als Fotodiode nutzen kann und wenn
man das schnell hintereinander abwechselt
00:15:17.190 --> 00:15:20.299
leuchtet und kucken wie hell es ist, hat
man eine serielle Schnittstelle über eine
00:15:20.299 --> 00:15:24.210
Leuchtdiode. Was natürlich auch dazu
führt, wenn man den Compiler auch noch im
00:15:24.210 --> 00:15:27.180
Chip hat, dann kann man über die Power On
Lampe seiner Kaffeemaschine neue
00:15:27.180 --> 00:15:30.460
Brühprogramme einspeichern und
Fehlermeldungen auslesen. Aber das ist
00:15:30.460 --> 00:15:32.479
jetzt noch etwas anderes,
das nur so nebenbei.
00:15:32.479 --> 00:15:35.589
Gelächter
Kucken wir uns das jetzt einmal genauer an.
00:15:35.589 --> 00:15:39.470
Als erstes werden Konstanten definiert
für Anode und Kathode, wo die gerade
00:15:39.470 --> 00:15:44.810
angeschlossen sind und dann eine
Definition, – "shine" soll sie heißen –
00:15:44.810 --> 00:15:48.340
wo die Anode und die Kathode beide als
Ausgang gesetzt werden und die Anode
00:15:48.340 --> 00:15:53.270
"high". Wenn man sich das jetzt einmal
disassembliert ansieht ist da schon
00:15:53.270 --> 00:15:59.689
einiges passiert. Als erstes "Anode,
Kathode or". Ist zu einer einzigen Konstante
00:15:59.689 --> 00:16:05.509
Hex F zusammen gefasst worden. Das
war die Konstantenfaltung. Dann als
00:16:05.509 --> 00:16:13.270
nächstes, ganz unten, das letzte wäre
ein Call um etwas zu speichern im io-Teil.
00:16:13.270 --> 00:16:16.780
Dort wird jetzt ein Jump und kein Call
eingefügt, das war die
00:16:16.780 --> 00:16:21.430
Tail-Call-Optimierung. Ist das
soweit noch ganz klar?
00:16:25.100 --> 00:16:28.840
Hier kann man noch einmal das Inlining sehen,
00:16:28.840 --> 00:16:32.480
denn an der Stelle hier,
Kathode AND, das "AND" wurde auch direkt
00:16:32.480 --> 00:16:37.610
eingefügt als Alu-Opcode und wurde nicht
als Call eingefügt und dann darum herum
00:16:37.610 --> 00:16:41.680
natürlich wieder die üblichen
Verdächtigen. Unten passiert Tail-Call
00:16:41.680 --> 00:16:45.130
und für die Konstantenfaltung habe ich
nochmal ein kleines Beispiel und zwar das
00:16:45.130 --> 00:16:50.110
was ich ganz am Anfang hatte, wie das
aussieht. Ganz einfach: Es wird
00:16:50.110 --> 00:16:53.850
ausgerechnet vom Compiler schon während
des kompilierens, die Konstante wird
00:16:53.850 --> 00:16:58.000
geschrieben. Der Stack-Prozessor kann
keine Konstante in Opcodes mit einbauen,
00:16:58.000 --> 00:17:03.440
also gibt es da keine weitere Optimierung
mehr. Dann kommt plus. Plus ist drin im
00:17:03.440 --> 00:17:07.628
Prozessor und der J1 hat noch die
Möglichkeit auch gleich den Rücksprung
00:17:07.628 --> 00:17:14.759
mit im Opcode zu haben. Fertig. Tail-Call
im Prinzip auch erledigt. So. Zum J1
00:17:14.759 --> 00:17:18.789
Prozessor kann man viel erzählen, ich
will nur kurz sagen, er ist sehr klein,
00:17:18.789 --> 00:17:22.529
sehr verständlich - das sind 200 Zeilen
Verilog, es lohnt sich wirklich sich das
00:17:22.529 --> 00:17:29.590
mal anzukucken. Schaut mal rein, wenn
ihr euch dafür interessiert. MSP430, das
00:17:29.590 --> 00:17:32.190
ist ein Prozessor, der sehr viele
verschiedene Adressierungsarten
00:17:32.190 --> 00:17:36.869
unterstützt und auch eigentlich recht gut
zu Forth passt. Mit Tail-Call gab es so
00:17:36.869 --> 00:17:40.269
ein paar Probleme, weil es einige Tricks
gibt, die mit den Rücksprungadressen
00:17:40.269 --> 00:17:44.489
etwas machen und dann knackst es. Also
habe ich keinen Tail-Call drin. Aber
00:17:44.489 --> 00:17:49.539
Konstantenfaltung, Inlining und
Opcodierung sind drin. Hier noch ein paar
00:17:49.539 --> 00:17:55.299
Beispiele. Hier kann man wieder sehen, es
werden Konstanten definiert und ganz am
00:17:55.299 --> 00:17:59.220
Ende sollen dann wieder Leuchtdioden
angesteuert werden, soll der Taster
00:17:59.220 --> 00:18:04.560
vorbereitet werden, hat man nur
Initialisierung für so ein Launchpad.
00:18:04.560 --> 00:18:09.820
Das sieht kompiliert so aus. Es tritt mehreres
in Aktion. Die Konstanten kommen wieder
00:18:09.820 --> 00:18:15.869
über die Konstantenfaltung und diese
Befehle werden über Inlining eingebaut
00:18:15.869 --> 00:18:20.299
und dadurch, dass sie direkt Parameter in
den Opcode übernehmen können, kriegen
00:18:20.299 --> 00:18:24.299
sie auch die Opcodierungen, so, dass das
was hinterher heraus kommt eigentlich das
00:18:24.299 --> 00:18:28.449
gleiche ist was ich auch in Assembler
schreiben würde. Man sieht es auch immer,
00:18:28.449 --> 00:18:33.260
die Zahlen immer nur ein Opcode, das
war es. Das letzte ist übrigens der
00:18:33.260 --> 00:18:38.530
Rücksprung, der sieht immer bisschen
komisch aus, aber das funktioniert.
00:18:38.530 --> 00:18:43.740
Mecrisp-Stellaris ist eine direkte
Portierung von Mecrisp auf einen ARM
00:18:43.740 --> 00:18:48.500
Cortex M4 gewesen. Stellaris-Launchpad war
die erste Plattform die unterstützt war.
00:18:48.500 --> 00:18:53.589
Der Name klingt gut, habe ich so gelassen.
Eigentlich identisch mit dem MSP430, wenn
00:18:53.589 --> 00:18:57.649
es um Optimierung geht. Aber ich habe
jetzt gerade noch (?) müssen noch /
00:18:57.649 --> 00:19:00.870
werden noch fertig geworden, einen
Registerallokator rein bekommen, den
00:19:00.870 --> 00:19:04.739
möchte ich noch kurz zeigen. Hier sieht
man ein Beispiel was schon ein bisschen
00:19:04.739 --> 00:19:09.139
schwieriger ist. Das oben ist der gray
Code, der gray Code ist so eine Sache,
00:19:09.139 --> 00:19:13.499
wenn man darin zählt, ändert sich immer
nur eine Bitstelle. Na gut, aber darum
00:19:13.499 --> 00:19:17.549
soll es jetzt nicht gehen, sondern darum,
dass man hier sieht, das keine
00:19:17.549 --> 00:19:24.230
Stackbewegungen mehr da sind. Das oberste
Stackelement ist im ARM in Register 6 enthalten
00:19:24.230 --> 00:19:28.229
und die Zwischenergebnisse, also duplicate
legt das oberste Element nochmal auf den
00:19:28.229 --> 00:19:34.019
Stack, dann kommt die Eins; man sieht
schon, der Schiebebefehl hat als
00:19:34.019 --> 00:19:38.570
Zielregister ein anderes Register, also
ein reines Zwischenergebnisregister und
00:19:38.570 --> 00:19:42.370
exklusiv-oder nimmt es von da und tut es
wieder auf das oberste Stackelement,
00:19:42.370 --> 00:19:48.280
so dass man gar kein Stackbewegung mehr
braucht und das Quadrat genauso. Das ist
00:19:48.280 --> 00:19:52.210
eben die Sache, dass man versucht
Zwischenergebnisse in Registern zu halten,
00:19:52.210 --> 00:19:58.530
soweit möglich. Das hier ist ein klein
bisschen aufwendigeres Beispiel. Hier ist
00:19:58.530 --> 00:20:02.539
es so, das Variablen geholt werden sollen,
zwei Stück, addiert und wieder zurück
00:20:02.539 --> 00:20:07.069
geschrieben. Im ARM Cortex kann man
übrigens einen Offset an jeden Ladebefehl
00:20:07.069 --> 00:20:12.070
daran fügen. Am Anfang wird also die
Adresse der Variablen geladen, dann wird
00:20:12.070 --> 00:20:15.729
die erste Variable geholt, dann die
zweite, beide werden addiert und zurück
00:20:15.729 --> 00:20:18.910
geschrieben. Wieder keine
Stackbewegungen nötig.
00:20:22.020 --> 00:20:27.040
Wer jetzt ein bisschen neugierig geworden
ist und sofort loslegen möchte:
00:20:27.040 --> 00:20:29.440
Alle Launchpads von Texas Instruments
00:20:29.440 --> 00:20:34.750
werden unterstützt, die ARM Cortex, viele
davon, von STM, Texas Instruments,
00:20:34.750 --> 00:20:42.049
Infineon neuerdings und Freescale und wer
andere Systeme benutzt, kann natürlich
00:20:42.049 --> 00:20:47.260
auch gerne Forth ausprobieren. Es gibt
Gforth für den PC, AmForth für die Atmel
00:20:47.260 --> 00:20:55.050
AVR-Reihe, für PIC gibt es FlashForth und
für den Z80 und einige andere CamelForth.
00:20:55.050 --> 00:20:59.789
Ganz ganz viele verschiedene. Es kommt
nämlich daher, das dadurch, dass Forth
00:20:59.789 --> 00:21:02.480
recht klein ist und recht leicht
implementiert werden kann, dass viele
00:21:02.480 --> 00:21:06.609
Leute zum kennen lernen der Sprache
einfach selber ihren eigenen Compiler
00:21:06.609 --> 00:21:10.899
implementieren. Das macht Spaß und ich
denke – auch wenn man mir jetzt dafür den
00:21:10.899 --> 00:21:15.899
Kopf abreißen wird, in einigen Kreisen –
man möge es tun. Denn dabei lernt man
00:21:15.899 --> 00:21:19.669
sehr viel über das Innere kennen. Andere
sagen natürlich man soll sich erst einmal
00:21:19.669 --> 00:21:22.789
mit der Philosophie der Sprache
auseinander setzen. Sei es drum, beide
00:21:22.789 --> 00:21:25.919
Seiten haben ihre guten Argumente. Ich
muss sage, ich habe direkt mit dem
00:21:25.919 --> 00:21:30.630
Schreiben meines ersten Compilers begonnen
und stehe nun ja. Ich habe noch einige
00:21:30.630 --> 00:21:35.309
Beispiele mitgebracht und ich habe
noch ein bisschen Zeit über. Das hier
00:21:35.309 --> 00:21:40.260
generiert Zufallszahlen mit dem Rauschen
des AD-Wandler der einen Temperatursensor
00:21:40.260 --> 00:21:44.690
trägt. Das ist einfach eine kleine
Schleife, die 16 mal durchläuft und es
00:21:44.690 --> 00:21:50.409
wird jeweils aus dem Analogkanal zehn im
MSP430 ein Wert gelesen, das unterste Bit
00:21:50.409 --> 00:21:58.612
wird maskiert, dann hinzu getan zu dem was
man schon hat und das nächste Bit. Das
00:21:58.612 --> 00:22:03.580
ist das wie es kompiliert worden ist. Als
erstes werden die Schleifenregister frei
00:22:03.580 --> 00:22:08.989
gemacht, dann wird eine Null auf den Stack
gelegt, wenn man es sich hier nochmal
00:22:08.989 --> 00:22:13.720
ankuckt, eine Null ganz am Anfang wurde da
schon hingelegt, also der Wert wo dann
00:22:13.720 --> 00:22:20.609
hinterher die Bits aus dem AD-Wandler rein
kommen. Dann, der Shiftbefehl wurde per
00:22:20.609 --> 00:22:27.640
Inlining eingefügt, dann kommt die
Konstante Zehn auf den Stack. Leider gibt
00:22:27.640 --> 00:22:32.539
es nur einen Push-Befehl im MSP430, also
hier die Kombination aus Stackpointer
00:22:32.539 --> 00:22:36.789
erniedrigen, etwas darauf legen, dann wird
analog klassisch ausgeführt mit einem
00:22:36.789 --> 00:22:41.900
Callbefehl und anschließend wieder
Inlining und Opcodierungen. Das Maskieren
00:22:41.900 --> 00:22:46.249
des unteren Bits ist nur noch ein Opcode,
Xor genauso und kann direkt eingefügt
00:22:46.249 --> 00:22:51.979
werden. Dann wird der Schleifenzähler
erhöht, verglichen und die Schleife
00:22:51.979 --> 00:22:56.610
springt zurück. Wenn die Schleife fertig
ist, Register zurück holen, Rücksprung.
00:22:56.610 --> 00:23:00.429
Hier hat man mal die ganzen Optimierungen
alle in einem gesehen, wie das in einem
00:23:00.429 --> 00:23:04.120
echten Beispiel aussieht, weil das davor
ja doch so ein bisschen gestellt gewesen ist
00:23:04.120 --> 00:23:09.090
um es schön zu zeigen. Das hier ist
ein etwas größeres Beispiel auf
00:23:09.090 --> 00:23:14.489
dem ARM Cortex. Die Bitexponentialfunktion
ist so etwas wie eine Exponentialfunktion,
00:23:14.489 --> 00:23:18.320
die aber auf Integer funktioniert. Und
hier kann man auch nochmal verschiedene
00:23:18.320 --> 00:23:22.189
Sachen sehen wie das im ARM Cortex
aussieht und was passiert wenn
00:23:22.189 --> 00:23:29.570
Kontrollsturkturen dazwischen kommen. Ganz
am Anfang wird verglichen ob der Wert eine
00:23:29.570 --> 00:23:34.499
bestimmte Größe erreicht hat. Dann,
dieses "push lr" kommt daher, dass im ARM
00:23:34.499 --> 00:23:39.090
Cortex so ein Link-Register existiert,
der dafür da ist, dass
00:23:39.090 --> 00:23:43.130
Unterprogrammeinsprünge die keine weitere
Ebene haben direkt im Register bleiben und
00:23:43.130 --> 00:23:46.779
nicht auf den Return-Stack gelegt werden.
Wenn aber Kontrollstrukturen kommen und
00:23:46.779 --> 00:23:50.571
noch nicht klar ist ob in einem der zwei
Zweige vielleicht doch noch ein
00:23:50.571 --> 00:23:54.889
Unterpgrogramm aufgerufen werden muss,
muss er jetzt gesichert werden. Dann zeigt
00:23:54.889 --> 00:23:59.069
der Sprung der zum "if" gehört, eine Zahl
wird herunter geworfen und eine Neue rein
00:23:59.069 --> 00:24:03.690
gelegt, was aber im Endeffekt nur ein
Ladebefehl ist, weil ja der Register Top
00:24:03.690 --> 00:24:08.081
of Stack ohnehin schon die ganze Zeit
bereit gelegen hat. Im else Zweig ist ein
00:24:08.081 --> 00:24:13.479
bisschen mehr zu tun. Das duplicate
brauchen wir nicht. Ein Registerallokator
00:24:13.479 --> 00:24:20.490
dahinter. Dann der Vergleich, wieder das
"if", hier bei "1 rshift" kann man wieder
00:24:20.490 --> 00:24:23.550
sehen, dass das alles in einen Opcode
zusammen gefügt worden ist, das ist
00:24:23.550 --> 00:24:32.379
wieder Kombinationen aus Konstantenfaltung
und Inlining. Dann, der else-Zweig, so,
00:24:32.379 --> 00:24:36.409
hier ist ein bisschen mehr zu tun. Man
kann jetzt auch sehen, dass mehrere
00:24:36.409 --> 00:24:42.940
Zwischenergebnisse im Register auftreten.
Also r3 und r2, beide mit dabei, die Werte
00:24:42.940 --> 00:24:46.219
werden jetzt nicht mehr auf den Stack
gelegt, sondern zwischen den Registern hin
00:24:46.219 --> 00:24:50.439
und her geschoben. Vielleicht wird das
jetzt ein bisschen unübersichtlich, aber
00:24:50.439 --> 00:24:54.619
ich denke, wenn man das direkt vergleicht,
ich habe immer dort wo Assembler steht
00:24:54.619 --> 00:24:57.829
auch den Forth Quelltext daneben
und das sind die Opcodes die jeweils
00:24:57.829 --> 00:25:04.200
für die Zeile generiert werden.
Was man hier noch sehen kann,
00:25:04.200 --> 00:25:08.950
dass man im ARM Cortex leider nicht
eine Konstante in den einzelnen Befehl mit
00:25:08.950 --> 00:25:14.850
einfügen kann. Deswegen wird es über ein
anderes Register geladen. Aber, andere
00:25:14.850 --> 00:25:18.809
Sachen – wie der Shiftbefehl – können
Konstanten direkt übernehmen. Das ist
00:25:18.809 --> 00:25:24.769
hier passiert und ganz am Ende muss
aufgeräumt werden. Bislang war das kein
00:25:24.769 --> 00:25:29.689
Problem, weil das oberste Element immer in
r6 geblieben ist. Jetzt aber wurden durch
00:25:29.689 --> 00:25:35.989
die Zwischenergebnisse und das hin und her
jonglieren, der Fall erreicht, dass das
00:25:35.989 --> 00:25:39.779
oberste Element auf dem Stack eben nicht
mehr in dem Register ist der normalerweise
00:25:39.779 --> 00:25:44.629
das oberste Element trägt. Deswegen der
vorletzte Befehl, der move-Befehl dient
00:25:44.629 --> 00:25:48.739
zum aufräumen. Der hat kein Äquivalent
in Forth, aber er dient dazu, das
00:25:48.739 --> 00:25:52.910
Stackmodell was gerade in einem Zustand
ist wie es sonst nicht sein sollte wieder
00:25:52.910 --> 00:25:56.069
auf den kanonischen Stack zurück zu
führen, damit an der Schnittstelle alles
00:25:56.069 --> 00:26:00.440
sauber übergeben werden kann. Wohl
gemerkt, globale Optimierungen gibt es
00:26:00.440 --> 00:26:04.469
noch nicht, wird es wohl auch erst einmal
nicht geben, aber man kann schon einmal
00:26:04.469 --> 00:26:08.519
sehen, dass man die gesamte Sache ohne
Stackbewegung geschafft hat, mal davon
00:26:08.519 --> 00:26:12.219
abgesehen, das der Returnstack einmal die
Adresse zum Rücksprung aufgenommen hat,
00:26:12.219 --> 00:26:17.219
was ich aber nicht vermeiden konnte, weil
dieser Compiler nicht voraus schauen kann.
00:26:17.219 --> 00:26:21.500
Er kann immer nur sehen, wo er gerade ist
und versuchen dafür zu generieren. Um das
00:26:21.500 --> 00:26:24.809
weglassen zu können, müsste man dann
vorausschauen können um zu sehen was
00:26:24.809 --> 00:26:30.169
in den Kontrollstrukturen
vielleicht doch noch passiert.
00:26:30.169 --> 00:26:33.169
Damit bin ich am Ende
angelangt, alle Beispiele gezeigt. Kann
00:26:33.169 --> 00:26:37.149
ich nur noch wünschen: Alles Gute zum
neuen Jahr! Wenn dann noch Fragen sind,
00:26:37.149 --> 00:26:40.179
kommt gleich nochmal zu mir, schreibt mir,
ich freue mich über viele E-Mails.
00:26:40.179 --> 00:26:41.849
Vielen Dank.
00:26:41.849 --> 00:26:43.159
Applaus
00:26:43.159 --> 00:26:46.921
Herald: Okay, alles klar,
vielen Dank Matthias.
00:26:46.921 --> 00:26:50.559
Abspannmusik
00:26:50.559 --> 00:26:57.000
subtitles created by c3subtitles.de
Join, and help us!