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