1
00:00:00,000 --> 00:00:09,705
32C3 Vorspannmusik
2
00:00:09,715 --> 00:00:14,550
Herald: Dann ist es mir jetzt eine ganz
besondere Freude Matthias Koch
3
00:00:14,550 --> 00:00:21,200
vorzustellen. Der wird über Compiler
Optimierung für Forth im Microcontroller
4
00:00:21,200 --> 00:00:25,140
sprechen. Bitte einen warmen
Applaus für Matthias.
5
00:00:25,140 --> 00:00:31,270
Applaus
6
00:00:31,270 --> 00:00:35,719
Matthias: Guten Tag, Hallo. Wie gesagt
Compileroptimierung für Forth im
7
00:00:35,719 --> 00:00:40,190
Microcontroller und ganz zur Eröffnung
habe ich eine Frage: Wer von euch kennt
8
00:00:40,190 --> 00:00:46,350
Forth eigentlich schon? Okay, so etwa die
Hälfte. Das bedeutet aber ich sollte
9
00:00:46,350 --> 00:00:50,480
besser noch einmal kurz erklären was
diese Sprache eigentlich ausmacht. Es ist
10
00:00:50,480 --> 00:00:56,059
eine Sprache die auf dem Modell eines
Stacks basiert. Vielleicht kennt ihr
11
00:00:56,059 --> 00:01:00,840
die umgekehrte polnische Notation wo es so
ist das erst die Parameter kommen und dann
12
00:01:00,840 --> 00:01:04,209
die Operatoren. Man legt also Werte auf
den Stack und von oben kommen die
13
00:01:04,209 --> 00:01:08,670
Operatoren, nehmen sich ewas und berechnen
ewas und legen es wieder darauf. Es gibt
14
00:01:08,670 --> 00:01:12,640
noch einen zweiten Stack, den Return-Stack
worüber die Rücksprungadressen
15
00:01:12,640 --> 00:01:17,200
gehandhabt werden. Das bedeutet man kann
nacheinander die verschiedenen Operatoren
16
00:01:17,200 --> 00:01:22,950
aufrufen und muss nicht wie bei C den
Stackframe hin und her kopieren. Der
17
00:01:22,950 --> 00:01:28,120
Compiler selbst ist sehr simpel aufgebaut.
Es basiert darauf, dass man den Eingabestrom
18
00:01:28,120 --> 00:01:34,470
was der Mensch tippt, in Wörter zerhackt,
also ein Space, Tabulator, Zeilenumbruch.
19
00:01:34,470 --> 00:01:38,050
Wenn ein Wort gefunden wird, wird es in
der Liste der bekannten Wörter gesucht
20
00:01:38,050 --> 00:01:42,710
entweder ausgeführt oder compiliert und
wenn es nicht gefunden werden kann wird es
21
00:01:42,710 --> 00:01:46,740
als Zahl interpretiert, auf den Stack
gelegt, oder es wird etwas kompiliert um
22
00:01:46,740 --> 00:01:49,950
diese Zahl dann später auf den Stack zu
legen. Das war eigentlich schon die
23
00:01:49,950 --> 00:01:54,820
Sprache. Das Besondere daran ist, dass
sie klein genug ist, dass sie in einem
24
00:01:54,820 --> 00:01:59,450
Mikrocontroller installiert werden kann.
Was dazu führt das man dann mit einem
25
00:01:59,450 --> 00:02:04,380
Terminal mit seinem Chip sprechen kann und
von innen heraus ausprobieren, ob der
26
00:02:04,380 --> 00:02:07,779
Hardwarecode funktioniert, weil man dann
nicht viele kleine Testprogramme schreiben
27
00:02:07,779 --> 00:02:11,800
muss, sondern ganz einfach von Hand an den
Leitungen wackeln kann und alle
28
00:02:11,800 --> 00:02:16,730
Definitionen die man geschrieben hat auch
sofort interaktiv ausprobieren kann. Das
29
00:02:16,730 --> 00:02:20,220
führt dann auch dazu, dass die
Definitionen natürlich gleich in der
30
00:02:20,220 --> 00:02:24,640
Hardware läuft und auch gleich mit
Echtzeit, so dass man die Fehlersuche
31
00:02:24,640 --> 00:02:31,784
stark vereinfachen kann. Das ist so ein
bisschen eine Einführung in Forth.
32
00:02:31,784 --> 00:02:34,640
Ich selbst habe diese Sprachen nicht
erfunden, die gibt es schon seit mehr als
33
00:02:34,640 --> 00:02:36,290
einem halben Jahrhundert.
34
00:02:36,290 --> 00:02:41,220
Aber ich habe Compiler geschrieben
für MSP430, ARM Cortex M0, M3
35
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
36
00:02:46,910 --> 00:02:50,720
Bowman gemacht habe, die auf einem
FPGA läuft. Aber dazu ein bisschen mehr
37
00:02:50,720 --> 00:02:55,200
später. Eigentlich ist das ungewöhnlich
sich selbst vorzustellen aber meine
38
00:02:55,200 --> 00:02:58,920
Freunde meinen das sollte man sagen. Ich
bin Diplomphysiker und habe Physik mit
39
00:02:58,920 --> 00:03:03,870
Nebenfach Gartenbau studiert, bin gerade in
meiner Doktorarbeit in der Laserspektroskopie
40
00:03:03,870 --> 00:03:08,030
habe gemischte Interessen durcheinander,
besonders Radionavigation
41
00:03:08,030 --> 00:03:12,400
und meine Lieblingssprachen
kann man hier sehen.
42
00:03:12,400 --> 00:03:17,010
Der Name mag vielleicht etwas ungewöhnlich
sein, aber die erste unterstützte
43
00:03:17,010 --> 00:03:22,550
Plattform war der MSP430 von MSP und
"écris" aus dem französischen kam der
44
00:03:22,550 --> 00:03:26,940
Name dann. Überschreibt den MSP430
weil es da innen drin ist und man schreibt
45
00:03:26,940 --> 00:03:32,600
direkt hinein. Unterstützt dann alle
MSP430-Launchpads, sehr viele ARM Cortex
46
00:03:32,600 --> 00:03:39,590
Architekturen und mit dem FPGA ein
bisschen mehr. Die klassischen
47
00:03:39,590 --> 00:03:44,120
Architekturen, also die auf denen Forth
normalerweise implementiert worden ist
48
00:03:44,120 --> 00:03:48,020
– so geschichtlich – waren eine virtuelle
Maschine. Wo eine Liste von Pointern
49
00:03:48,020 --> 00:03:52,850
drinen war, wo nacheinander diese Pointer
genommen worden sind und dann entweder wie
50
00:03:52,850 --> 00:03:58,560
eine Liste von Pointern zählten oder
aber eben ein Assemblerprimitive.
51
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
52
00:04:03,490 --> 00:04:06,770
wird sehr einfach dadurch und es lassen
sich auch einige ungewöhnliche Sachen
53
00:04:06,770 --> 00:04:12,989
dabei implementieren. Aber es frisst
viele viele Taktzyklen. Die ganz alten
54
00:04:12,989 --> 00:04:18,238
Systeme hatten sogar die Möglichkeit noch
einmal über eine Tabelle die ganzen
55
00:04:18,238 --> 00:04:22,550
verschiedenen Pointer umzuleiten, so dass
man Definitionen die schon liefen
56
00:04:22,550 --> 00:04:27,040
nachträglich noch ändern konnte, also
eine Definition ganz tief im System durch
57
00:04:27,040 --> 00:04:30,690
etwas neues austauschen. Die wird dann
sofort auch verwendet. Das ging mal.
58
00:04:30,690 --> 00:04:33,970
Ausserdem lässt sich Forth sehr leicht
dekompilieren, zumindest bei der
59
00:04:33,970 --> 00:04:39,250
klassischen Implementation, so das bei
einer Jupiter Ace. Man braucht ja keine
60
00:04:39,250 --> 00:04:43,749
Quelltexte, man hatte den Objektcode, man
konnte ihn desassemblieren zurück in den
61
00:04:43,749 --> 00:04:50,160
Quelltext, ändern und neu kompilieren
fertig. Die Optimierungen, die ich jetzt
62
00:04:50,160 --> 00:04:54,630
vorführen werde, zerstören diesen
interessanten Aspekt, weil da Maschinencode
63
00:04:54,630 --> 00:04:57,200
heraus kommt und weil da
auch Teile weg optimiert werden.
64
00:04:57,200 --> 00:05:00,340
Es gibt also nicht mehr so den eins zu eins
Zusammenhang zwischen dem was man
65
00:05:00,340 --> 00:05:04,580
geschrieben hat und dem was hinterher
tatsächlich im Prozessor ausgeführt wird.
66
00:05:04,580 --> 00:05:08,120
Anders herum jedoch, hatte Forth
lange auch mit dem Problem zu kämpfen,
67
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
68
00:05:13,090 --> 00:05:17,950
gerne heute vorstellen was für
Optimierungen man im Chip selbst
69
00:05:17,950 --> 00:05:22,940
durchführen kann, natürlich aus der
Compilertheorie heraus sind das alles alte
70
00:05:22,940 --> 00:05:28,320
Hüte. Aber die meisten Compiler brauchen
sehr viel Speicher, laufen auf einem PC wo
71
00:05:28,320 --> 00:05:31,980
es ja fast unbegrenzt davon gibt. Ich
möchte aber einmal herausfinden welche
72
00:05:31,980 --> 00:05:35,840
Optimierungen man in den Arbeitsspeichern
eines kleinen Microcontrollers
73
00:05:35,840 --> 00:05:42,260
implementieren kann. Dazu gehören
Tail-Call, Konstantenfaltung, Inlining,
74
00:05:42,260 --> 00:05:48,190
Opcodierung und die Registerallokation. In
welcher Architektur diese jeweils
75
00:05:48,190 --> 00:05:51,880
implementiert sind steht da mit bei.
Nun will ich die ganzen einzelnen
76
00:05:51,880 --> 00:05:57,030
Optimierungen einmal vorstellen. Tail-Call
ist relativ simpel. Wenn das letzte in
77
00:05:57,030 --> 00:06:01,310
einer Routine ein Call ist und danach
direkt ein Return kommt, dann kann man das
78
00:06:01,310 --> 00:06:04,919
auch durch einen Sprungbefehl ersetzen.
man braucht dann nicht den Umweg über den
79
00:06:04,919 --> 00:06:09,030
Stack zu nehmen. Das ist eigentlich so
weit klar, nichts besonderes.
80
00:06:09,030 --> 00:06:14,500
Konstantenfaltung bedeutet: Manchmal
möchte man als Mensch etwas so schreiben,
81
00:06:14,500 --> 00:06:19,970
dass man ein paar Konstanten nimmt, die
multipliziert, zusammen verodert; all das
82
00:06:19,970 --> 00:06:23,320
immer mit zu kompilieren wäre ja
eigentlich Zeitverschwendung. Es steht ja
83
00:06:23,320 --> 00:06:28,530
schon während der Kompilierung fest, was
das Ergebnis dieser Berechnung sein wird,
84
00:06:28,530 --> 00:06:32,041
der Compiler kann also durchaus diese
Rechnung schon während dem kompilieren
85
00:06:32,041 --> 00:06:36,080
durchführen, nur noch das Ergebnis
einkompilieren. Hier sieht man mal ein
86
00:06:36,080 --> 00:06:40,880
kleines Beispiel, also Sechs auf dem Stack
legen, Sieben auf den Stack legen, beide
87
00:06:40,880 --> 00:06:44,910
Werte vertauschen, miteinander
multiplizieren und das ganze dann
88
00:06:44,910 --> 00:06:50,710
aufsummieren. Eigentlich stehen die ersten
Teile schon fest, das reicht wenn man 42
89
00:06:50,710 --> 00:06:54,919
plus kompilieren würde. Das ist die
Konstantenfaltung. Das ist jetzt ein
90
00:06:54,919 --> 00:06:59,230
glasklarer Fall, wo man das direkt sieht,
aber manchmal gibt es auch aus anderen
91
00:06:59,230 --> 00:07:02,210
Optimierungen heraus noch die
Möglichkeit, dass Konstantenfaltungen
92
00:07:02,210 --> 00:07:08,930
möglich werden kann. Das ist dann nicht
mehr ganz so offensichtlich. Dazu, wie das
93
00:07:08,930 --> 00:07:12,270
implementiert wird, möchte ich erst
einmal kurz zeigen wie der klassische
94
00:07:12,270 --> 00:07:17,500
Forth Compiler implementiert worden ist.
Es war so, dass der Eingabestrom den der
95
00:07:17,500 --> 00:07:22,790
Benutzer eingetippt hat in einzelne
Wörter, in Tokens zerhackt worden ist,
96
00:07:22,790 --> 00:07:27,020
dann wurde geprüft ob es in der Liste der
bekannten Definitionen auftaucht, oder
97
00:07:27,020 --> 00:07:31,580
eben auch nicht. Ist das der Fall, ist die
Frage ob kompiliert werden soll oder
98
00:07:31,580 --> 00:07:35,040
nicht. Es gibt einen Ausführ- und
einen Kompiliermodus, der eine interaktive
99
00:07:35,050 --> 00:07:40,449
Sprache. Im Kompiliermodus und was nicht
immer geht das – auch eine Spezialität
100
00:07:40,449 --> 00:07:44,930
von Forth. Dann wird ein Aufruf in der
Definition einkompiliert, also ein Call
101
00:07:44,930 --> 00:07:49,259
Befehl geschrieben. Immediate bedeutet
übrigens, dass etwas das kompiliert
102
00:07:49,259 --> 00:07:53,749
werden soll selbst ausgeführt wird. Das
braucht man für Kontrollstrukturen, die
103
00:07:53,749 --> 00:07:58,480
dann noch so Sprünge handhaben müssen
und ähnliches und ansonsten ist man im
104
00:07:58,480 --> 00:08:02,600
Ausführmodus, wird die Definition
ausgeführt. Nichts gefunden: Versucht man
105
00:08:02,600 --> 00:08:07,020
es als Zahl zu interpretieren und je
nachdem ob kompiliert werden soll oder
106
00:08:07,020 --> 00:08:11,509
nicht, wird auf den Stack gelegt oder es
wird etwas kompiliert, was die Zahl dann
107
00:08:11,509 --> 00:08:15,289
bei der Ausführung auf den Stack legen
wird. Wenn es auch keine gültige Zahl
108
00:08:15,289 --> 00:08:21,380
ist, ist es ein Fehler. Um dort
Konstantenfaltung einzfügen sind keine so
109
00:08:21,380 --> 00:08:25,319
großen Änderungen nötig. Wichtig ist
jetzt eigentlich nur, dass man die
110
00:08:25,319 --> 00:08:30,419
Konstanten nicht kompiliert, zumindest
nicht gleich, sondern erst einmal sammelt
111
00:08:30,419 --> 00:08:35,000
und dann wenn eine Operation kommt die bei
konstanten Eingaben auch konstante
112
00:08:35,000 --> 00:08:41,220
Ausgaben produziert, diese dann
auszuführen. Die Änderungen sind so,
113
00:08:41,220 --> 00:08:46,620
dass jetzt ganz am Anfang der aktuelle
Stackfüllstand gemerkt werden muss, denn
114
00:08:46,620 --> 00:08:50,750
man muss ja auch wissen, wie viele
Konstanten gerade zur Verfügung stehen.
115
00:08:50,750 --> 00:08:54,640
Soll es ausgeführt werden, wurde es
gefunden, dann brauchen wir keine
116
00:08:54,640 --> 00:08:58,330
Konstantenfaltung machen, dann schmeißen
wir den Pointer wieder weg, alles gut,
117
00:08:58,330 --> 00:09:03,990
vergessen wir. Sind wir im Kompiliermodus,
wird geprüft ob diese Definition mit
118
00:09:03,990 --> 00:09:08,540
konstanten Eingaben auch eine konstante
Ausgabe produzieren kann und wenn ja, sind
119
00:09:08,540 --> 00:09:13,740
genug dafür vorhanden. Eine Invertierung
einer Zahl braucht eine Konstante. Eine
120
00:09:13,740 --> 00:09:18,899
Addition braucht zwei Konstanten usw. das
muss geprüft werden. Wenn das gut geht
121
00:09:18,899 --> 00:09:22,960
kann sie ausgeführt werden. Sie lässt
dann die Ergebnisse dort liegen und
122
00:09:22,960 --> 00:09:26,280
dadurch, dass wir wusten wo der
Stackpointer vorher gewesen ist, wissen
123
00:09:26,280 --> 00:09:30,650
wir auch wie viele Konstanten danach noch
auf dem Stack liegen geblieben sind. Es
124
00:09:30,650 --> 00:09:37,610
kann also durchaus variabel viele
Ausgabekonstanten produzieren. Ist diese
125
00:09:37,610 --> 00:09:42,750
Definition jedoch nicht faltbar, dann
bleibt uns nichts anderes übrig, als
126
00:09:42,750 --> 00:09:46,470
alles was dort an Konstanten liegt
einzukompilieren und dann einen
127
00:09:46,470 --> 00:09:51,820
klassischen Call Befehl zu machen. Ja,
aber man kann den klassischen Callbefehl
128
00:09:51,820 --> 00:09:54,760
auch nochmal ein bisschen abwandeln. Man
kann kucken ob da eine sehr kurze
129
00:09:54,760 --> 00:09:59,480
Definition ist und dann Opcodes direkt
einfügen und bei Forth natürlich
130
00:09:59,480 --> 00:10:04,029
Imediate überprüfen was bedeutet, dass
diese Definition selber irgendwelche
131
00:10:04,029 --> 00:10:11,320
Spezialfälle umsetzen kann. Nicht
gefunden, Zahlen bleiben stets auf dem
132
00:10:11,320 --> 00:10:17,269
Stack liegen, damit sie halt später in
die Konstantenfaltung rein kommen können.
133
00:10:17,269 --> 00:10:21,000
Wichtig dabei ist zu wissen, dass dabei,
während die Zahlen gesammelt werden, ja
134
00:10:21,000 --> 00:10:26,380
schon ein Merker in den Stack gesetzt
wurde um den Füllstand zu bestimmen. Ist
135
00:10:26,380 --> 00:10:31,110
es nicht als Zahl zu interpretieren, ist
es ein Fehler. Das ist im Prinzip der
136
00:10:31,110 --> 00:10:34,960
Kerngedanke um Konstantenfaltung in Forth
zu implementieren. Das hier ist
137
00:10:34,960 --> 00:10:40,580
grundsätzlich auf jeder Architektur
möglich wo Forth läuft und ist auch
138
00:10:40,580 --> 00:10:45,710
relativ unabhängig davon wie das Forth
innen drin implementiert hat. Ich habe
139
00:10:45,710 --> 00:10:50,600
schon gesehen, dass jemand Matthias Troote
(?) von der MForth für AVR, angefangen hat
140
00:10:50,600 --> 00:10:54,119
das auch einzubauen und das noch
zusammen recognizern. Also es geht recht
141
00:10:54,119 --> 00:11:00,120
gut, es ist auch Standardkonform. Die
nächste Sache: Inlining. Klar macht der
142
00:11:00,120 --> 00:11:05,399
C-Kompiler auch. Kurze Definitionen die
nur ein paar Opcodes haben, können mit
143
00:11:05,399 --> 00:11:09,640
einigen Vorsichtsmaßregeln auch direkt
eingefügt werden, denn wozu sollte man
144
00:11:09,640 --> 00:11:14,810
einen Call wohin tun, wenn die Opcodes
kürzer sind als der Call selbst. Und hier
145
00:11:14,810 --> 00:11:18,580
das Beispiel von Plus. Man ruft nicht
die primitive vom Plus auf wenn man den
146
00:11:18,580 --> 00:11:24,940
Plus-Opcode direkt einfügen kann. Das
leuchtet eigentlich auch ein.
147
00:11:24,940 --> 00:11:28,430
Opcodierungen - ich nenne es mal so, ich
weiß nicht wie es sonst genannt werden
148
00:11:28,430 --> 00:11:34,550
soll – ist, wenn ein Opcode eine Konstante
direkt in sich aufnehmen kann. Dann ist es
149
00:11:34,550 --> 00:11:39,000
doch sinnvoller die Konstante direkt mit
zu opcodieren, als sie über den Stack zu
150
00:11:39,000 --> 00:11:42,760
legen und dann darüber zu verwenden. Man
spart halt ein paar Takte und ein bisschen
151
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
152
00:11:48,969 --> 00:11:53,469
immer wunderbar, bei einem Cortex
manchmal, der hat nur einige Opcodes die
153
00:11:53,469 --> 00:11:58,800
Konstanten können und wenn man einen
Stackprozessor hat, geht das gar nicht.
154
00:11:58,800 --> 00:12:03,029
Und der Regsiterallokator schließlich,
ist die Überlegung, dass man
155
00:12:03,029 --> 00:12:07,269
Zwischenergebnisse, die bei Forth
traditionell auf dem Stack liegen würden,
156
00:12:07,269 --> 00:12:11,220
versucht auf Register abzubilden. Denn
klar in der Stacksprache ist das ganz
157
00:12:11,220 --> 00:12:15,760
etwas anderes als einen Prozessor der
hauptsächlich mit Registern arbeitet.
158
00:12:15,760 --> 00:12:19,329
Beim ARM Cortex ist das ganz besonders
schlimm, denn er kann nicht direkt in den
159
00:12:19,329 --> 00:12:23,529
Speicher zugreifen um da irgend etwas zu
berechnen, sondern er muss auf jeden Fall
160
00:12:23,529 --> 00:12:28,260
immer aus dem Speicher in Register holen,
im Register etwas machen und in den
161
00:12:28,260 --> 00:12:32,760
Speicher zurück schreiben. Das ist
ziemlich aufwendig. Wenn man das abkürzen
162
00:12:32,760 --> 00:12:36,240
kann, die Zwischenergebnisse gleich im
Register hält, kann man viel kürzere
163
00:12:36,240 --> 00:12:40,550
Befehlssequenzen nutzen, die direkt
zwischen den Registern arbeiten.
164
00:12:40,550 --> 00:12:44,660
Wichtig dabei ist noch, dass das ganze
transpartent wird für den Programmierer,
165
00:12:44,660 --> 00:12:48,740
wenn man also etwas macht, wo die logische
Struktur des Stacks sichtbar wird oder
166
00:12:48,740 --> 00:12:53,329
sichtbar werden könnte, muss der Compiler
auf jeden Fall zurück fallen und alles in
167
00:12:53,329 --> 00:12:57,060
den richtigen Stack rein schreiben, so
dass man dann auch direkt im Stack
168
00:12:57,060 --> 00:13:01,120
Manipulation machen kann, wenn das denn
mal notwendig ist und das ist bei Forth
169
00:13:01,120 --> 00:13:06,150
ziemlich häufig, weil Forth Programmierer
gerne alle möglichen Tricks anwenden.
170
00:13:10,470 --> 00:13:15,800
Das wesentliche für den Registerallokator
ist, zu wissen wo welches Element gerade
171
00:13:15,800 --> 00:13:20,000
ist, man muss also während der
Kompilierung ein Stackmodell mit laufen
172
00:13:20,000 --> 00:13:24,930
lassen, worin vermerkt ist, wo diese Stack-
elemente eigentlich gerade sind. Sind sie
173
00:13:24,930 --> 00:13:29,490
noch auf dem Stack selbst, also im
Arbeitsspeicher? Sind sie gerade in einem
174
00:13:29,490 --> 00:13:35,010
Register drin? Wenn ja, in welchem? Oder,
wenn neue Zwischenergebnisse auftreten:
175
00:13:35,010 --> 00:13:38,750
Haben wir noch genug Register? Denn wenn
mehr Zwischenergebnisse da sind als
176
00:13:38,750 --> 00:13:41,930
Register zur Verfügung stehen, dann
müssen die Register wieder in den
177
00:13:41,930 --> 00:13:46,930
Arbeitsspeicher auf den Stack geschrieben
werden und das ist es was innen drin das
178
00:13:46,930 --> 00:13:54,499
besondere ausmacht. Man kann es sehr klein
implementieren, aber man muss daran
179
00:13:54,499 --> 00:13:58,520
denken, dass das sehr seltsam ist,
dass das im Microcontroller läuft,
180
00:13:58,520 --> 00:14:03,010
normalerweise gibt es bei Register-
allokatoren viele Algorithmen drum herum,
181
00:14:03,010 --> 00:14:06,240
die überlegen, wie man das
möglichst gut über möglichst weite
182
00:14:06,240 --> 00:14:10,559
Strecken im Programm machen kann. Ich habe
es sehr einfach gemacht. An den Stellen wo
183
00:14:10,559 --> 00:14:15,250
Kontrollstrukturen verzweigen hört man
einfach auf. Man schreibt dann alles in
184
00:14:15,250 --> 00:14:19,371
den Stack und fertig. Ist eine sehr simple
Implementation und globale Optimierung
185
00:14:19,371 --> 00:14:24,980
habe ich gar nicht drin. Aber es ist ein
Anfang. Das sind jetzt all die
186
00:14:24,980 --> 00:14:29,950
Optimierungen die angesprochen werden
sollen. Nun will ich ein paar Beispiele
187
00:14:29,950 --> 00:14:34,420
dafür zeigen. Erst einmal muss ich aber
noch sagen: Mercrisp-Ice ist nicht allein
188
00:14:34,420 --> 00:14:38,920
meine Arbeit sondern basiert auf vielen
vielen anderen schönen Sachen die auch
189
00:14:38,920 --> 00:14:43,720
vorgestellt worden sind. James Bowman hat
den J1 Prozessor entwickelt. Clifford
190
00:14:43,720 --> 00:14:48,509
Wolf, Cotton Seed und Mathias Lasser haben
die erste freie Toolchain für FPGAs
191
00:14:48,509 --> 00:14:55,570
entwickelt und darauf basiert das alles.
Da drin habe ich die Konstantenfaltung,
192
00:14:55,570 --> 00:15:00,930
automatisches Inline kurzer Definitionen
und Tail-Call-Optimierung. Hier ist jetzt
193
00:15:00,930 --> 00:15:05,220
mal ein kleines Beispiel. Das ist noch
aus der LEDcom Implementation, wie man
194
00:15:05,220 --> 00:15:08,750
über eine Leuchtdiode kommunizieren kann.
Für die die jetzt nicht bei der Assembly
195
00:15:08,750 --> 00:15:13,399
gesehen haben, es ist so, dass man eine
Leuchtdiode nicht nur zum Leuchten sondern
196
00:15:13,399 --> 00:15:17,190
auch als Fotodiode nutzen kann und wenn
man das schnell hintereinander abwechselt
197
00:15:17,190 --> 00:15:20,299
leuchtet und kucken wie hell es ist, hat
man eine serielle Schnittstelle über eine
198
00:15:20,299 --> 00:15:24,210
Leuchtdiode. Was natürlich auch dazu
führt, wenn man den Compiler auch noch im
199
00:15:24,210 --> 00:15:27,180
Chip hat, dann kann man über die Power On
Lampe seiner Kaffeemaschine neue
200
00:15:27,180 --> 00:15:30,460
Brühprogramme einspeichern und
Fehlermeldungen auslesen. Aber das ist
201
00:15:30,460 --> 00:15:32,479
jetzt noch etwas anderes,
das nur so nebenbei.
202
00:15:32,479 --> 00:15:35,589
Gelächter
Kucken wir uns das jetzt einmal genauer an.
203
00:15:35,589 --> 00:15:39,470
Als erstes werden Konstanten definiert
für Anode und Kathode, wo die gerade
204
00:15:39,470 --> 00:15:44,810
angeschlossen sind und dann eine
Definition, – "shine" soll sie heißen –
205
00:15:44,810 --> 00:15:48,340
wo die Anode und die Kathode beide als
Ausgang gesetzt werden und die Anode
206
00:15:48,340 --> 00:15:53,270
"high". Wenn man sich das jetzt einmal
disassembliert ansieht ist da schon
207
00:15:53,270 --> 00:15:59,689
einiges passiert. Als erstes "Anode,
Kathode or". Ist zu einer einzigen Konstante
208
00:15:59,689 --> 00:16:05,509
Hex F zusammen gefasst worden. Das
war die Konstantenfaltung. Dann als
209
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.
210
00:16:13,270 --> 00:16:16,780
Dort wird jetzt ein Jump und kein Call
eingefügt, das war die
211
00:16:16,780 --> 00:16:21,430
Tail-Call-Optimierung. Ist das
soweit noch ganz klar?
212
00:16:25,100 --> 00:16:28,840
Hier kann man noch einmal das Inlining sehen,
213
00:16:28,840 --> 00:16:32,480
denn an der Stelle hier,
Kathode AND, das "AND" wurde auch direkt
214
00:16:32,480 --> 00:16:37,610
eingefügt als Alu-Opcode und wurde nicht
als Call eingefügt und dann darum herum
215
00:16:37,610 --> 00:16:41,680
natürlich wieder die üblichen
Verdächtigen. Unten passiert Tail-Call
216
00:16:41,680 --> 00:16:45,130
und für die Konstantenfaltung habe ich
nochmal ein kleines Beispiel und zwar das
217
00:16:45,130 --> 00:16:50,110
was ich ganz am Anfang hatte, wie das
aussieht. Ganz einfach: Es wird
218
00:16:50,110 --> 00:16:53,850
ausgerechnet vom Compiler schon während
des kompilierens, die Konstante wird
219
00:16:53,850 --> 00:16:58,000
geschrieben. Der Stack-Prozessor kann
keine Konstante in Opcodes mit einbauen,
220
00:16:58,000 --> 00:17:03,440
also gibt es da keine weitere Optimierung
mehr. Dann kommt plus. Plus ist drin im
221
00:17:03,440 --> 00:17:07,628
Prozessor und der J1 hat noch die
Möglichkeit auch gleich den Rücksprung
222
00:17:07,628 --> 00:17:14,759
mit im Opcode zu haben. Fertig. Tail-Call
im Prinzip auch erledigt. So. Zum J1
223
00:17:14,759 --> 00:17:18,789
Prozessor kann man viel erzählen, ich
will nur kurz sagen, er ist sehr klein,
224
00:17:18,789 --> 00:17:22,529
sehr verständlich - das sind 200 Zeilen
Verilog, es lohnt sich wirklich sich das
225
00:17:22,529 --> 00:17:29,590
mal anzukucken. Schaut mal rein, wenn
ihr euch dafür interessiert. MSP430, das
226
00:17:29,590 --> 00:17:32,190
ist ein Prozessor, der sehr viele
verschiedene Adressierungsarten
227
00:17:32,190 --> 00:17:36,869
unterstützt und auch eigentlich recht gut
zu Forth passt. Mit Tail-Call gab es so
228
00:17:36,869 --> 00:17:40,269
ein paar Probleme, weil es einige Tricks
gibt, die mit den Rücksprungadressen
229
00:17:40,269 --> 00:17:44,489
etwas machen und dann knackst es. Also
habe ich keinen Tail-Call drin. Aber
230
00:17:44,489 --> 00:17:49,539
Konstantenfaltung, Inlining und
Opcodierung sind drin. Hier noch ein paar
231
00:17:49,539 --> 00:17:55,299
Beispiele. Hier kann man wieder sehen, es
werden Konstanten definiert und ganz am
232
00:17:55,299 --> 00:17:59,220
Ende sollen dann wieder Leuchtdioden
angesteuert werden, soll der Taster
233
00:17:59,220 --> 00:18:04,560
vorbereitet werden, hat man nur
Initialisierung für so ein Launchpad.
234
00:18:04,560 --> 00:18:09,820
Das sieht kompiliert so aus. Es tritt mehreres
in Aktion. Die Konstanten kommen wieder
235
00:18:09,820 --> 00:18:15,869
über die Konstantenfaltung und diese
Befehle werden über Inlining eingebaut
236
00:18:15,869 --> 00:18:20,299
und dadurch, dass sie direkt Parameter in
den Opcode übernehmen können, kriegen
237
00:18:20,299 --> 00:18:24,299
sie auch die Opcodierungen, so, dass das
was hinterher heraus kommt eigentlich das
238
00:18:24,299 --> 00:18:28,449
gleiche ist was ich auch in Assembler
schreiben würde. Man sieht es auch immer,
239
00:18:28,449 --> 00:18:33,260
die Zahlen immer nur ein Opcode, das
war es. Das letzte ist übrigens der
240
00:18:33,260 --> 00:18:38,530
Rücksprung, der sieht immer bisschen
komisch aus, aber das funktioniert.
241
00:18:38,530 --> 00:18:43,740
Mecrisp-Stellaris ist eine direkte
Portierung von Mecrisp auf einen ARM
242
00:18:43,740 --> 00:18:48,500
Cortex M4 gewesen. Stellaris-Launchpad war
die erste Plattform die unterstützt war.
243
00:18:48,500 --> 00:18:53,589
Der Name klingt gut, habe ich so gelassen.
Eigentlich identisch mit dem MSP430, wenn
244
00:18:53,589 --> 00:18:57,649
es um Optimierung geht. Aber ich habe
jetzt gerade noch (?) müssen noch /
245
00:18:57,649 --> 00:19:00,870
werden noch fertig geworden, einen
Registerallokator rein bekommen, den
246
00:19:00,870 --> 00:19:04,739
möchte ich noch kurz zeigen. Hier sieht
man ein Beispiel was schon ein bisschen
247
00:19:04,739 --> 00:19:09,139
schwieriger ist. Das oben ist der gray
Code, der gray Code ist so eine Sache,
248
00:19:09,139 --> 00:19:13,499
wenn man darin zählt, ändert sich immer
nur eine Bitstelle. Na gut, aber darum
249
00:19:13,499 --> 00:19:17,549
soll es jetzt nicht gehen, sondern darum,
dass man hier sieht, das keine
250
00:19:17,549 --> 00:19:24,230
Stackbewegungen mehr da sind. Das oberste
Stackelement ist im ARM in Register 6 enthalten
251
00:19:24,230 --> 00:19:28,229
und die Zwischenergebnisse, also duplicate
legt das oberste Element nochmal auf den
252
00:19:28,229 --> 00:19:34,019
Stack, dann kommt die Eins; man sieht
schon, der Schiebebefehl hat als
253
00:19:34,019 --> 00:19:38,570
Zielregister ein anderes Register, also
ein reines Zwischenergebnisregister und
254
00:19:38,570 --> 00:19:42,370
exklusiv-oder nimmt es von da und tut es
wieder auf das oberste Stackelement,
255
00:19:42,370 --> 00:19:48,280
so dass man gar kein Stackbewegung mehr
braucht und das Quadrat genauso. Das ist
256
00:19:48,280 --> 00:19:52,210
eben die Sache, dass man versucht
Zwischenergebnisse in Registern zu halten,
257
00:19:52,210 --> 00:19:58,530
soweit möglich. Das hier ist ein klein
bisschen aufwendigeres Beispiel. Hier ist
258
00:19:58,530 --> 00:20:02,539
es so, das Variablen geholt werden sollen,
zwei Stück, addiert und wieder zurück
259
00:20:02,539 --> 00:20:07,069
geschrieben. Im ARM Cortex kann man
übrigens einen Offset an jeden Ladebefehl
260
00:20:07,069 --> 00:20:12,070
daran fügen. Am Anfang wird also die
Adresse der Variablen geladen, dann wird
261
00:20:12,070 --> 00:20:15,729
die erste Variable geholt, dann die
zweite, beide werden addiert und zurück
262
00:20:15,729 --> 00:20:18,910
geschrieben. Wieder keine
Stackbewegungen nötig.
263
00:20:22,020 --> 00:20:27,040
Wer jetzt ein bisschen neugierig geworden
ist und sofort loslegen möchte:
264
00:20:27,040 --> 00:20:29,440
Alle Launchpads von Texas Instruments
265
00:20:29,440 --> 00:20:34,750
werden unterstützt, die ARM Cortex, viele
davon, von STM, Texas Instruments,
266
00:20:34,750 --> 00:20:42,049
Infineon neuerdings und Freescale und wer
andere Systeme benutzt, kann natürlich
267
00:20:42,049 --> 00:20:47,260
auch gerne Forth ausprobieren. Es gibt
Gforth für den PC, AmForth für die Atmel
268
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.
269
00:20:55,050 --> 00:20:59,789
Ganz ganz viele verschiedene. Es kommt
nämlich daher, das dadurch, dass Forth
270
00:20:59,789 --> 00:21:02,480
recht klein ist und recht leicht
implementiert werden kann, dass viele
271
00:21:02,480 --> 00:21:06,609
Leute zum kennen lernen der Sprache
einfach selber ihren eigenen Compiler
272
00:21:06,609 --> 00:21:10,899
implementieren. Das macht Spaß und ich
denke – auch wenn man mir jetzt dafür den
273
00:21:10,899 --> 00:21:15,899
Kopf abreißen wird, in einigen Kreisen –
man möge es tun. Denn dabei lernt man
274
00:21:15,899 --> 00:21:19,669
sehr viel über das Innere kennen. Andere
sagen natürlich man soll sich erst einmal
275
00:21:19,669 --> 00:21:22,789
mit der Philosophie der Sprache
auseinander setzen. Sei es drum, beide
276
00:21:22,789 --> 00:21:25,919
Seiten haben ihre guten Argumente. Ich
muss sage, ich habe direkt mit dem
277
00:21:25,919 --> 00:21:30,630
Schreiben meines ersten Compilers begonnen
und stehe nun ja. Ich habe noch einige
278
00:21:30,630 --> 00:21:35,309
Beispiele mitgebracht und ich habe
noch ein bisschen Zeit über. Das hier
279
00:21:35,309 --> 00:21:40,260
generiert Zufallszahlen mit dem Rauschen
des AD-Wandler der einen Temperatursensor
280
00:21:40,260 --> 00:21:44,690
trägt. Das ist einfach eine kleine
Schleife, die 16 mal durchläuft und es
281
00:21:44,690 --> 00:21:50,409
wird jeweils aus dem Analogkanal zehn im
MSP430 ein Wert gelesen, das unterste Bit
282
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
283
00:21:58,612 --> 00:22:03,580
ist das wie es kompiliert worden ist. Als
erstes werden die Schleifenregister frei
284
00:22:03,580 --> 00:22:08,989
gemacht, dann wird eine Null auf den Stack
gelegt, wenn man es sich hier nochmal
285
00:22:08,989 --> 00:22:13,720
ankuckt, eine Null ganz am Anfang wurde da
schon hingelegt, also der Wert wo dann
286
00:22:13,720 --> 00:22:20,609
hinterher die Bits aus dem AD-Wandler rein
kommen. Dann, der Shiftbefehl wurde per
287
00:22:20,609 --> 00:22:27,640
Inlining eingefügt, dann kommt die
Konstante Zehn auf den Stack. Leider gibt
288
00:22:27,640 --> 00:22:32,539
es nur einen Push-Befehl im MSP430, also
hier die Kombination aus Stackpointer
289
00:22:32,539 --> 00:22:36,789
erniedrigen, etwas darauf legen, dann wird
analog klassisch ausgeführt mit einem
290
00:22:36,789 --> 00:22:41,900
Callbefehl und anschließend wieder
Inlining und Opcodierungen. Das Maskieren
291
00:22:41,900 --> 00:22:46,249
des unteren Bits ist nur noch ein Opcode,
Xor genauso und kann direkt eingefügt
292
00:22:46,249 --> 00:22:51,979
werden. Dann wird der Schleifenzähler
erhöht, verglichen und die Schleife
293
00:22:51,979 --> 00:22:56,610
springt zurück. Wenn die Schleife fertig
ist, Register zurück holen, Rücksprung.
294
00:22:56,610 --> 00:23:00,429
Hier hat man mal die ganzen Optimierungen
alle in einem gesehen, wie das in einem
295
00:23:00,429 --> 00:23:04,120
echten Beispiel aussieht, weil das davor
ja doch so ein bisschen gestellt gewesen ist
296
00:23:04,120 --> 00:23:09,090
um es schön zu zeigen. Das hier ist
ein etwas größeres Beispiel auf
297
00:23:09,090 --> 00:23:14,489
dem ARM Cortex. Die Bitexponentialfunktion
ist so etwas wie eine Exponentialfunktion,
298
00:23:14,489 --> 00:23:18,320
die aber auf Integer funktioniert. Und
hier kann man auch nochmal verschiedene
299
00:23:18,320 --> 00:23:22,189
Sachen sehen wie das im ARM Cortex
aussieht und was passiert wenn
300
00:23:22,189 --> 00:23:29,570
Kontrollsturkturen dazwischen kommen. Ganz
am Anfang wird verglichen ob der Wert eine
301
00:23:29,570 --> 00:23:34,499
bestimmte Größe erreicht hat. Dann,
dieses "push lr" kommt daher, dass im ARM
302
00:23:34,499 --> 00:23:39,090
Cortex so ein Link-Register existiert,
der dafür da ist, dass
303
00:23:39,090 --> 00:23:43,130
Unterprogrammeinsprünge die keine weitere
Ebene haben direkt im Register bleiben und
304
00:23:43,130 --> 00:23:46,779
nicht auf den Return-Stack gelegt werden.
Wenn aber Kontrollstrukturen kommen und
305
00:23:46,779 --> 00:23:50,571
noch nicht klar ist ob in einem der zwei
Zweige vielleicht doch noch ein
306
00:23:50,571 --> 00:23:54,889
Unterpgrogramm aufgerufen werden muss,
muss er jetzt gesichert werden. Dann zeigt
307
00:23:54,889 --> 00:23:59,069
der Sprung der zum "if" gehört, eine Zahl
wird herunter geworfen und eine Neue rein
308
00:23:59,069 --> 00:24:03,690
gelegt, was aber im Endeffekt nur ein
Ladebefehl ist, weil ja der Register Top
309
00:24:03,690 --> 00:24:08,081
of Stack ohnehin schon die ganze Zeit
bereit gelegen hat. Im else Zweig ist ein
310
00:24:08,081 --> 00:24:13,479
bisschen mehr zu tun. Das duplicate
brauchen wir nicht. Ein Registerallokator
311
00:24:13,479 --> 00:24:20,490
dahinter. Dann der Vergleich, wieder das
"if", hier bei "1 rshift" kann man wieder
312
00:24:20,490 --> 00:24:23,550
sehen, dass das alles in einen Opcode
zusammen gefügt worden ist, das ist
313
00:24:23,550 --> 00:24:32,379
wieder Kombinationen aus Konstantenfaltung
und Inlining. Dann, der else-Zweig, so,
314
00:24:32,379 --> 00:24:36,409
hier ist ein bisschen mehr zu tun. Man
kann jetzt auch sehen, dass mehrere
315
00:24:36,409 --> 00:24:42,940
Zwischenergebnisse im Register auftreten.
Also r3 und r2, beide mit dabei, die Werte
316
00:24:42,940 --> 00:24:46,219
werden jetzt nicht mehr auf den Stack
gelegt, sondern zwischen den Registern hin
317
00:24:46,219 --> 00:24:50,439
und her geschoben. Vielleicht wird das
jetzt ein bisschen unübersichtlich, aber
318
00:24:50,439 --> 00:24:54,619
ich denke, wenn man das direkt vergleicht,
ich habe immer dort wo Assembler steht
319
00:24:54,619 --> 00:24:57,829
auch den Forth Quelltext daneben
und das sind die Opcodes die jeweils
320
00:24:57,829 --> 00:25:04,200
für die Zeile generiert werden.
Was man hier noch sehen kann,
321
00:25:04,200 --> 00:25:08,950
dass man im ARM Cortex leider nicht
eine Konstante in den einzelnen Befehl mit
322
00:25:08,950 --> 00:25:14,850
einfügen kann. Deswegen wird es über ein
anderes Register geladen. Aber, andere
323
00:25:14,850 --> 00:25:18,809
Sachen – wie der Shiftbefehl – können
Konstanten direkt übernehmen. Das ist
324
00:25:18,809 --> 00:25:24,769
hier passiert und ganz am Ende muss
aufgeräumt werden. Bislang war das kein
325
00:25:24,769 --> 00:25:29,689
Problem, weil das oberste Element immer in
r6 geblieben ist. Jetzt aber wurden durch
326
00:25:29,689 --> 00:25:35,989
die Zwischenergebnisse und das hin und her
jonglieren, der Fall erreicht, dass das
327
00:25:35,989 --> 00:25:39,779
oberste Element auf dem Stack eben nicht
mehr in dem Register ist der normalerweise
328
00:25:39,779 --> 00:25:44,629
das oberste Element trägt. Deswegen der
vorletzte Befehl, der move-Befehl dient
329
00:25:44,629 --> 00:25:48,739
zum aufräumen. Der hat kein Äquivalent
in Forth, aber er dient dazu, das
330
00:25:48,739 --> 00:25:52,910
Stackmodell was gerade in einem Zustand
ist wie es sonst nicht sein sollte wieder
331
00:25:52,910 --> 00:25:56,069
auf den kanonischen Stack zurück zu
führen, damit an der Schnittstelle alles
332
00:25:56,069 --> 00:26:00,440
sauber übergeben werden kann. Wohl
gemerkt, globale Optimierungen gibt es
333
00:26:00,440 --> 00:26:04,469
noch nicht, wird es wohl auch erst einmal
nicht geben, aber man kann schon einmal
334
00:26:04,469 --> 00:26:08,519
sehen, dass man die gesamte Sache ohne
Stackbewegung geschafft hat, mal davon
335
00:26:08,519 --> 00:26:12,219
abgesehen, das der Returnstack einmal die
Adresse zum Rücksprung aufgenommen hat,
336
00:26:12,219 --> 00:26:17,219
was ich aber nicht vermeiden konnte, weil
dieser Compiler nicht voraus schauen kann.
337
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
338
00:26:21,500 --> 00:26:24,809
weglassen zu können, müsste man dann
vorausschauen können um zu sehen was
339
00:26:24,809 --> 00:26:30,169
in den Kontrollstrukturen
vielleicht doch noch passiert.
340
00:26:30,169 --> 00:26:33,169
Damit bin ich am Ende
angelangt, alle Beispiele gezeigt. Kann
341
00:26:33,169 --> 00:26:37,149
ich nur noch wünschen: Alles Gute zum
neuen Jahr! Wenn dann noch Fragen sind,
342
00:26:37,149 --> 00:26:40,179
kommt gleich nochmal zu mir, schreibt mir,
ich freue mich über viele E-Mails.
343
00:26:40,179 --> 00:26:41,849
Vielen Dank.
344
00:26:41,849 --> 00:26:43,159
Applaus
345
00:26:43,159 --> 00:26:46,921
Herald: Okay, alles klar,
vielen Dank Matthias.
346
00:26:46,921 --> 00:26:50,559
Abspannmusik
347
00:26:50,559 --> 00:26:57,000
subtitles created by c3subtitles.de
Join, and help us!