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*