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,029
Herald: Okay, alles klar,
vielen Dank Matthias.

346
00:26:46,029 --> 00:26:56,961
*Abspannmusik*