Home | Artikel | VCFe Forth Interna

VCFe Vortrag vom 2011.04.30 - Forth Interna - Compiler und Interpreter aus der Sicht der CPU


Inhalt

Einführung

In diesem Vortrag wende ich mich nun erstmals der Software zu, welche auf einem Rechner läuft. Schliesslich ist ein Rechner ohne Software so ziemlich wertlos. Dies ist insgesammt ein sehr grosses Gebiet, weit grösser als alles was mit der Hardware des Rechners zu tun hat. Schon einmal die ganzen Programmiersprachen, und dann erst recht die ganzen Betriebssysteme, und dann die ganzen Applikationen oben drauf.

Dieses Jahr wird am VCFe einiges mit Forth gemacht. Also war es naheliegend, dass ich gleich Forth als Beispiel dafür nehme, zum daran sowohl das compilieren in einer einfachen Programmiersprache, wie auch das interpretieren in einem einfachen Kommandointerpreter aufzuzeigen. Also zeigen was eigentlich dahinter steckt, bis Forth auf einem Rechner läuft (oder überhaupt eine beliebige Hochsprache). Wer kein Forth kann, kann dies im standard Einführungstext Starting Forth nachlesen, oder im Text mit dem Forth Forth 1970 vorgestellt wurde.

Dieser Vortrag ist der vierte Teil zu drei früheren Vorträgen, der erste 2006.05.01 - Rechnen mit Bauklötzchen - Rechnergrundlagen und deren Implementationen und der zweite 2008.04.26 - 8008 8080/8085 und Z80/U880 - Maschinencode und Assembler und der dritte 2010.05.01 - Kommunikation - Schnittstellen für Datenübertragung von CPU zu CPU. Darin wurden bisher im ersten die Bits und ihre Implementation in Hardware als Gatter und daraus zusammengebaut Speicher und Prozessor gezeigt, sowie im zweiten die ganzen Prozessordetails wie Register und Rechnen und Befehle und Programmierung in Maschinencode und Assembler, sowie im dritten ein Teil der Daten Ein-/Ausgaben (der für diesen Vortrag allerdings nicht relevant ist).

Ausgehend von diesen bisherigen Prozessor und Maschinencode und Assembler Kenntnissen werden nun hier die Innereien von einem Forth Compiler und dem Kommandozeilen Interpreter gezeigt. Damit wird auch anerhand dieses einfachen Softwaresystemes die Lücke überbrückt, zwischen einerseits den nun bekannten Prozessor Mechanismen und anderseits dem schon lange bekannten Rechner benutzen mit einer Hochsprache und einer Kommandozeile.

Das ganze wird für mehrere Prozessortypen gemacht werden, zuerst mit dem bereits eingeführten 8080 aufgebaut, und dann mit einigen anderen, zum vergleichen wie sehr ihre verschiedenen Befehlssätze das Compilieren vereinfachen oder erschweren können, bzw die Geschwindigkeit des compilierten Programmes beschleunigen oder ausbremsen können.

Daneben wurde schon bisher in einem weiteren Vortrag 2007.04.28 - Basic Interpreter - am Beispiel von Commodore 64 und Dragon 32 ein weiteres Software System eingeführt, das den Leser vielleicht interessieren könnte, als Vergleich zu Forth.

Hochsprachen

Prozessoren können nur Maschinencode Befehle ausführen, und nichts anders. Auch Assembler Befehle sind nur symbolische Namen dafür. Sie sind daher auch rein durch Substitution umwandelbar.

Hochsprachen ihre Befehle sind anderseits komplett unabhängig vom Maschinencode, und erst recht dem Maschinencode eines spezifischen Prozessors. Sie sind eine reine symbolische Beschreibung der erwünschten Rechenoperationen. Programmieren wird damit in zwei Hälften aufgeteilt, was man will (die Rechnung), und wie man das dem spezifischen Prozessor entlockt (die Codegenerierung), von denen letztere automatisch gemacht wird. Dabei muss die resultierende Lücke von Hochsprache zu Maschinensprache überbrückt werden.

Dazu müssen die ersteren ihre Anweisungen in Folgen von letzteren ihren Befehlen zerlegt werden. Der Compiler ist die Brücke dazu, der muss diese Aufgabe erledigen. Dies gescheiht in zwei Schritten:

Bei Forth ist dies sehr stark vereinfacht. Weil ersteres grossteils vom Programmierer fertig gemacht angeliefert wird, und damit nur sehr simples Parsing nötig ist (nur Worte und Leerzeichen unterscheiden) und fast gar kein Lexing mehr (nur Zahlen und Operationen unterscheiden). Daher wird hier auch vor allem der zweite Teil des Compilers behandelt, den Code generieren, weil das auch zeigt wie eine Hochsprache mit einem Prozessor umgeht.

Forth

Die eigentlichen Operationen sind relativ einfach zu machen. Ein Forth + bedeutet eine Addition, und das ist im Intel Assembler ADD und im 8080 Maschinencode die Operation 000. Ebenso ist Forth - eine Subtraktion, in Assembler SUB und Maschinencode Operation 010. Das selbige gilt auch für Forth AND/OR/XOR die Und/Oder/ExOder bedeuten, was in Assembler ANA/ORA/XRA sind welche in Maschinencode Operationen 100/110/101 ergibt. Das ist so einfach, weil die Rechneneinheit und ihre Operationen genau dafür entwickelt wurdem. Das ist bei fast allen Prozessoren der Fall.

Leicht komplizierter wird es aber, weil der 8080 nur ein 8bit Prozessor ist, Forth aber von mindestens 16bit Zahlen ausgeht. Diese kann man aber in zwei 8bit Schritten rechnen, mit dem genau dafür vorgesehenen Carry Flag (neuntes Bit der unteren 8bit Operation abspeichern) und den Operationen mit Carry (das neunte Bit als &Uml;bertrag ins erste Bit der oberen 8bit einbauen, und somit ins neunte Bit der ganzen Rechnung). Also ist bei Addition und Subtraktion der erste/untere 8bit Teil mit ADD (000) bzw SUB (010) zu rechnen, und dann der zweite/obere 8bit Teil mit ADC (001) bzw SBB (011). Das selbige gilt auch wieder für Und/Oder/ExOder, nur ohne Carry, also beide 8bit Teile mit den selbigen Operationen. Daher gibt es diese auch nicht in 2 separaten ohne/mit Carry Versionen im Prozessor. Auch das ist bei fast allen 8bit Prozessoren der Fall.

Die Problematik ist mehr die Daten zu verwalten, wo wann welche sind und wie man die richtigen Daten an den richtigen Befehl gibt. Dazu braucht es einen von Befehl zu Befehl weitergegebenen Datenbestand, der gemäss einer Übergabekonventionen angeordnet sein muss. Hierin unterscheiden sich dann auch alle verschiedenen Typen Prozessoren stark von einander, und damit auch die generierten Befehlsfolgen.

Der 8080 hat wie seine 8bit Recheneinheit auch nur einen 8bit Akkumulator, der für beide Teile der 16bit Rechnung nacheinander wiederverwertet werden muss. Also müssen die beiden Teile für permanentere Abspeicherung anderstwo hin. Der 8080 offeriert einem dafür seine 6 anderen Register im Prozessor, für das am öftesten benutzte, und ansonsten nur noch seinen Hauptspeicher, und den wiederum mit einer Auswahl an Zugriffsmethoden, die je ihre Limiten und Zeitaufwand haben. Das ist ein typisches Problem für alle 8bit Prozessoren. Wie weit sie damit umgehen können, und wie aufwendig das wird, beeinflusst sehr stark den Compileraufwand und die Laufzeit für Hochsprachen. (Aber auch 16bit Prozessoren haben das Problem in kleinerer Ausführung. Der Akkumulator reicht zwar für eine ganze 16bit Forth Zahl, aber Forth braucht mehrere Zahlen aufs mal, und dann ist es wieder eine Frage von was in welchen Registern und wo/wie im Speicher angeordnet wird.)

Forth erwartet einen Stack für seine Daten. Jedes Wort erwartet seine Operanden dort und liefert sein Resultat dorthin. Das ist zentral in Forth. Die Laufzeit und damit Effizienz von Forth hängt massiv davon ab, wie man diesen Stack anordnet, wieviel Verwaltungsaufwand an Prozessor verbraucht wird zum Daten von diesem lesen und auf diesen schreiben. Diesen Aufwand und Verlust zu reduzieren ist eine Sache von Optimierungen, einerseits beim Entwerfen der Übergabekonventionen so das sie gut zum verwendeten Prozessor passen, und anderseits beim Code generieren diesen teilweise weglassen können, aber nur dort wo das sicher ist.

Dabei gibt es verschiedenste Sprachelemente, für die man Code generieren muss. Beispiele davon sind:

Zu Anfang werden, mit nur Datenstack, folgende Forth Befehle angeschaut:

Arithmetik: + - AND (und analog OR und XOR)
Stack: DUP DROP SWAP
Speicher: ! @
Zahlwert: 23 (und alle anderen Zahlwerte analog)

und später, mit auch Returnstack, dann noch folgende dazu:

Returnstack: >R R> OVER ROT

bevor dann noch später die ganzen Programmstrukturen an die Reihe kommen, inklusive : (colon) und ; (semicolon), sowie VARIABLE und CONSTANT.

Hinweis zur Aussprache: ! und @ werden als "store" (= speichern) und "fetch" (= holen) ausgesprochen, nicht als "Ausrufezeichen" und "at"/"Affenschwanz". Ebenso werden >R und R> als "to-R" (= zu R) und "R-from" (= R von) ausgesprochen, und nicht als "gröser-R" und "R-grösser", zumal sie Daten transferieren und nicht vergleichen.

Naiver Stack

Zuerst fangen wir an mit einer sehr naiven (und langsamen) Implementation, zum einmal grundlegendes Vorgehen zu zeigen, ohne Ablenkungen. Aber auch diese nutzt bereits prozessorspezifische Eigenheiten aus zum schneller sein, indem sie den Prozessorstack für die verschachtelten Unterprogram als Datenstack verwendet (bzw missbraucht). (Diese Implementation wird auch desswegen später versagen, ist also eine falsche Implementation. Aber sie ist einfacher zu verstehen als erstes Beispiel, und zeigt ein interessantes Detail auf bezüglich Features ausnutzen. Und sie wird später dann überraschend doch teilweise nutzbar werden.)

Der Prozessorstack ist für rekursive CALL/RET Paare gedacht, die jeweils den 16bit Programmzählerinhalt (die Adresse des nächsten Befehls) als 2 8bit Werte abspeichern vor dem Unterprogrammsprung (im CALL) bzw wieder lesen und dorthin springen beim Unterprogramrücksprung (im RET). Der Speicherblock dazu wird mit dem SP Register adressiert, der automatisch nebenbei verändert wird. CALL macht dabei Speicher[--SP] = PC und PC = Adresse, RET macht dann PC = Speicher[SP++]. Dazu gibt es aber auch noch die PUSH/POP Befehle, zum beliebige Daten von Registerpaaren auf dem Prozessorstack abzuspeichern und wiederzuholen, auch mit der Register SP Automatik, die hier ausnutzt wird.

Der naive Code mit dem Prozessorstack als Datenstack wäre dann:

+
POP D; POP H
DAD D
PUSH H
(Wegen dem DAD Spezialbefehl 16bit Addition ausnutzen mit Registerpaar HL als einzigen für den ersten/stack-tiefsten Operanden, und daher dann DE als zweiten/stack-obersten)
-
POP D; POP H
MOV A,L; SUB E; MOV L,A
MOV A,H; SBB D; MOV H,A
PUSH H
(Ist weitaus langsamer, 6 statt 1 Befehle zum rechnen, weil DAD der einzige ist der 16bit ausnutzt. Der Compilerbauer ist der Brückenbauer, muss den Prozessor und die Hochsprache kennen)
AND (und analog OR und XOR)
Ist wie bei -, nur die SUB/SBB durch 2 mal ANA ersetzen
DUP
POP H
PUSH H; PUSH H
DROP
INX SP; INX SP
(Das geschieht ohne den Speicher zu Lesen. Ein POP H mit Speicher lesen wäre der Code kürzer aber die Ausführung langsamer. Wieder muss man den Prozessor gut kennen)
SWAP
POP D; POP H
PUSH D; PUSH H
!
POP H; POP D
MOV M,E; INX H
MOV M,D; (kein INX H)
(HL ist die Adresse zum darin speichern vom obersten Stack Element, weil das MOV M, ausnutzen kann. DE ist das was gespeichert werden soll vom zweiten Stack Element. Nur ein INX weil keine weitere Adresse benötigt wird)
@
POP H
MOV E,M; INX H
MOV D,M
PUSH D
(HL ist wieder die Adresse zum davon lesen, und DE bekommt die gelesenen Daten, zum auf den Stack legen)
23 (und alle anderen Zahlwerte analog)
LXI H,23
PUSH H

TOS Cache Stack

Obiges war desshalb naiv (und langsam), weil die gewählte Stack Anordnung als Übergabekonvention viele unnötige PUSH und danach wider POP Befehle erzeugt werden. Diese sind zwar alles kurze 1Byte Befehle, aber langsam wegen drei Speicherzugriffen (daher waren die beiden 1Byte und 1Speicherzugriff INX SP Befehle auch schneller in DROP).

Hinweis zu Zeit und Geschwindigkeits Angaben: Ich gebe alle diese in Speicherzugriffen an, und nicht in Taktzyklen. Der Grund dafür ist die Elimination von prozessorabhängigen Taktzyklen zu Speicherzugriffen Umrechnungen, und damit bessere Vergleichbarkeit. Die Taktzyklen und Taktfrequenz sagen sehr wenig über Geschwindigkeit aus, genausowenig wie motortypabhängige Drehzahlen etwas über Fahrzeuggeschwindigkeit vergleichen aussagen (z.B. 10'000U/min 125cc vs 3'000U/min 2l). Anderseits sagen Speicherzugriffe einiges mehr aus, da Speicher bei allen Prozessoren etwa gleich schnell sind. Dann muss man nur noch die Effizienz von Anteil Nutzdatenzugriffe zu Gesammtzugriffe berücksichtigen, was den Hauptunterschied von Prozessoren ausmacht, zusammengesetzt aus Speicherzugriffen pro Befehl und Befehlen pro Wort.

Es ist daher besser, diese PUSH/POP (gross-)teils einzusparen, was unnötige Codezugriffe und Datenzugriffe einspart. Das kann man, indem man das oberste Forth Datenstack Element (Top Of Stack, TOS) permanent in einem Registerpaar behaltet. Das nennt man einen TOS Cache. Wir nehmen hierzu das HL Registerpaar, weil dies den DAD benutzen kann.

Der TOS Cache Code mit dem Prozessorstack als Datenstack wäre dann:

+
POP D
DAD D
(Hier fliegen 2 von 4 Befehlen, 2 von 4 Bytes und 6 von 10 Zugriffen. Und DAD HL=HL+DE ist zwar für Forth Op1=Op2+Op1, aber das geht hier weil die Addition kommutativ ist. Wenn es für Subtraktion ein DSB gäbe, müsste man dies langsamer als HL=DE-HL machen, mit XCHG; POP H; DSB D)
-
POP D
MOV A,E; SUB L; MOV L,A
MOV A,D; SBB H; MOV H,A
(Hier fliegen 2 von 9 Befehlen, 2 von 9 Bytes und 6 von 15 Zugriffen. Und weil mit der MOV/SUB Registerreihenfolgewahl bereits L=E-L und H=D-H passiert ist kein XCHG nötig)
AND (und analog OR und XOR)
Ist auch wie bei -, nur die SUB/SBB durch 2 mal ANA ersetzen, und ist erst noch kommutativ
DUP
PUSH H
(Hier fliegen 2 von 3 Befehlen, 2 von 3 Bytes und 6 von 9 Zugriffen)
DROP
POP H
(Hier wird Code gespart, aber mit mehr Zugriffen langsamer, ohne den 2 mal INX SP Trick. Hier muss man jetzt aber nach HL lesen, da die Daten im TOS Cache nachgeladen werden müssen, durch mit dem zweiten Stackelement überschreiben)
SWAP
POP D; XCHG; PUSH D, "herrein/schalten/hinraus"
oder alternativ:
POP D; PUSH H; XCHG, "im Dreieck kopieren"
oder gleich ganz kurz:
XTHL
(Hier nutzen wir wieder einen sehr spezialisierten Befehl aus, der HL und das oberste Stackelement austauscht. Solche Gelegenheiten erkennt man nur wenn man den Prozessor sehr gut kennt)
!
POP D
MOV M,E; INX H
MOV M,D
POP H
(Spart hier wieder nichts, weil wir den TOS Cache nachladen müssen. Hier ist jetzt HL die Adresse, weil TOS, und DE wird für die Daten benutzt)
@
MOV E,M; INX H
MOV D,M
XCHG
(Hier fliegen 2 von 5 Befehlen (und 1 neuer kommt), 2 von 5 Bytes (plus 1 neuer) und 6 von 11 Zugriffen (plus 1 neuer). Es hat gar keine Stackoperationen mehr, nur die Adresse in HL wird durch die Daten ersetzt. Der Umweg mit DE und XCHG ist nötig, weil wir 2 Bytes vom Speicher holen)
23 (und alle anderen Zahlwerte analog)
PUSH H
LXI H,23
(Hier wird also nichts gespart, nur die Reihenfolge wird anderst, zuerst den TOS Cache sichern, dann überschreiben. Man beachte noch, dass dies eigentlich ein DUP ist, und dann die obere Kopie überschreiben)

Zwei Stacks

Real verlangt Forth aber nach 2 Stacks, je einen für Daten und Returnadressen (so wie es die 8080 für CALL/RET Adressen ja auch vorgesehen hat). Eine reale Forth Implementation muss daher den Prozessorstack für CALL/RET benutzen.

Der Datenstack (bzw genauer der TOS) ist eigentlich Forth sein 16bit Akkumulator, einfach ein mehrfacher, mit n*16bit Grösse, mit den anderen Registern "hinter"/"unter" dem Akkumulator angeordnet. (Daher ist auch der TOS Cache in HL so passend, da dieser beim 8080 eine Art 16bit Hilfsakkumulator ist, vorgesehen zum 16bit Adressenrechnungen mache, wesshalb auch der DAD Befehl existiert.)

Die beiden Forth Befehle >R und R> entsprechen dabei den 8080 PUSH und POP, zum Daten (oder Adressen) vom/zum Datenstack zum/vom Returnstack verschieben, statt von/zu den 4 8080 Registerpaaren (BC,DE,HL,SP) zum/vom Prozessorstack verschieben.

Der Datenstack kann daher nicht mehr ihn und SP und PUSH/POP Befehle benutzen. Der Rest des Datenstacks (ohne TOS) muss daher als Adresse eines der Registerpaare BC oder DE benutzen. Diese können aber kein automatisches verändern. Also muss man diese mit INX und DEX bearbeiten, und das wie den Prozessor Returnstack Speicher[--SP]= nun mit DEX; PUSH schreiben und wie =Speicher[SP++] nun mit POP; INX lesen. Diese können auch keine 16bit aufs mal schreiben oder lesen, also braucht man jeweils 2 mal DEX; STAX oder LDAX; INX.

Das Registerpaar DE kann im XCHG Befehl benutzt werden, und das ist nützlich zum Daten mit HL austauschen. Also ist BC weniger wertvoll, also nimmt man am besten den für die Datenstackadresse. Damit wird geschrieben mit 2 mal DEX B; STAX B und gelesen mit 2 mal LDAX B; INX B. Das braucht insgesammt jeweils 4 statt 1 Befehle, 4 statt 1 Byte Code, und 6 statt 3 Speicherzugriffe.

Der TOS Cache Code ohne dem Prozessorstack als Datenstack wäre dann:

Bisheriges:
(nur umgebaut auf BC als Datenstack)
+
LDAX B; INX B; MOV E,A
LDAX B; INX B; MOV D,A
DAD D
(Wieder haben wir DAD, nur die Daten vom Stack holen wurde einiges aufwendiger, zumal sie auch noch von A nach E und D kopiert werden müssen. Identisch viele Datenzugriffe (2), aber weil weit mehr Befehle auch weit mehr Codezugriffe (7 statt 2). Von Naiv 4C+6D=10 zu TOS Cache 2C+2D=4 zu BC Stack 7C=2D=9)
-
LDAX B; INX B; SUB L; MOV L,A
LDAX B; INX B; SBB H; MOV H,A
(Und wieder ist, weil mit Registerwahl direkt L=A-L und H=A-H, ist kein E oder D nötig, und kein XCHG. Die beiden SUB/SBB sind nun vermischt mit den beiden LDAX weil es nur einen Akkumulator gibt, und beide in DE speichern und wieder nach A holen langsamer wäre, wegen mehr MOV Befehlen)
AND (und analog OR und XOR)
Ist wieder wie -, nur SUB/SBB durch 2 mal ANA ersetzen, und ist wieder auch kommutativ
DUP
MOV A,H; DEX B; STAX B
MOV A,L; DEX B; STAX B
DROP
LDAX B; INX B; MOV L,A
LDAX B; INX B; MOV H,A
SWAP
LDAX B; INX B; MOV E,A
LDAX B; (kein INX B); MOV D,A
MOV A,H; (kein DEX B); STAX B
MOV A,L; DEX B; STAX B
XCHG
(Hier verlieren wir den XTHL Spezialbefehl, daher geht es zurück zur POP D; PUSH H; XCHG Methode. Es is aber nur ein teilweiser POP D; PUSH H Ersatz nötig, das letzte INX und das erste DEX kann man sich sparen!)
!
LDAX B; INX B; MOV M,A; INX H
LDAX B; INX B; MOV M,A
LDAX B; INX B; MOV L,A
LDAX B; INX B; MOV H,A
(Man bemerke, alle LDAX B mit INX B, weil das Datenstack lesen ist, aber das zweite MOV M,A ohne, weil das nur die TOS Variablenadresse ist, die danach vom dritten Stackelement überschrieben wird)
@
MOV E,M; INX H
MOV D,M
XCHG
23 (und alle anderen Zahlwerte analog)
MOV A,H; DEX B; STAX B
MOV A,L; DEX B; STAX B
LXI H,23
Neues:
(mit BC Datenstack und SP Returnstack)
>R
PUSH H
LDAX B; INX B; MOV L,A
LDAX B; INX B; MOV H,A
(Gerade hier sieht man, wie TOS auf Returnstack mit PUSH viel schneller ist als das das zweite Stackelement in den TOS holen
R>
MOV A,H; DEX B; STAX B
MOV A,L; DEX B; STAX B
POP H
OVER
Kann man in Forth als >R DUP R> SWAP definieren, was für diese seltener benutzten und mit 3 Stackelementen arbeitend ohnehin langsameren Befehlen zum Teil ausreicht.
Oder man kann in Assembler die Sequenzen zusammenlegen, und dann diese durch Befehle weglassen optimieren:
*** ab hier >R
PUSH H
LDAX B; INX B; MOV L,A
LDAX B; (kein INX B); MOV H,A
*** ab hier DUP
(kein MOV A,H); (kein DEX B); (kein STAX B)
(kein MOV A,L); DEX B; (kein STAX B)
(Nach beiden LDAX ist das Element immer noch auf dem Stack, also kann man die zweimal MOV/STAX kürzen. Und wieder INX/DEX kürzen, das gibt einen kostenlosen integrierten DUP!)
*** ab hier R>
(kein MOV A,H); (kein DEX B); (kein STAX B)
(kein MOV A,L); (kein DEX B); (kein STAX B)
(statt POP H) POP D
(In HL sind bereits die Daten die am Schluss dort sein sollen. Also nicht wegspeichern, statt dessen die Daten von Returnstack direkt zum Rest-Datenstack kopieren, via dem Registerpaar DE)
*** ab hier SWAP
(kein LDAX B); (kein INX B); (kein MOV E,A)
(kein LDAX B); (kein MOV D,A)
(statt MOV A,H) MOV A,D; (und wieder da) DEX B; STAX B
(statt MOV A,L) MOV A,E; DEX B; STAX B
(kein XCHG)
(Und weil Daten schon in HL auch nicht vom Datenstack zu DE holen, und dann statt HL eben die in DE abspeichern. Insgesammt spart man mit den Optimierungen 17 von 31 Befehlen (und 1 neuer wieder da), 17-1 von 31 Bytes und 23-1 von 45 Zugriffen, also etwa 50%!)
(Und man kann noch mehr sparen, wenn man statt dem Returnstack mit PUSH H/POP D das Registerpaar DE mit XCHG/nichts benutzt, nochmals 1 Befehl 1 Byte und 5 Speicherzugriffe weg!)
ROT
Kann man in Forth als >R SWAP R> SWAP definieren. Und wie oben Assembler Sequenzen zusammenlegen und optimieren

Das ist einiges mehr an Code, nur weil STAX/LDAX B nur 8bit sind und kein INX/DEX B eingebaut haben, und die Daten in A statt DE landen. Das multipliziert alle Stackzugriffe zu 4 mal mehr Befehle, und ergibt so 2 mal mehr Laufzeit (die Code Speicherzugriffe gehen 4 mal rauf, die Datenspeicherzugriffe bleiben gleich). Auch die Rechenzeit bleibt gleich, also kostet das ganze so um 50% mehr Zeit!

Compilerbauer wollen daher auch Register die alle alles können, auch alle potentielle Stackpointer sein. Das nennt man dann einen orthogonalen Befehlssatz. Nicht-orthogonale Befehlssätze nerven massiv. Die 8080 Erweiterungen geben ein Paradebeispiel davon ab, egal ob DAD ohne DSB und nur in Registerpaar HL, oder PUSH/POP nur mit Registerpaar SP. Und die orthogonalere 8008 Basis alleine ist nicht leistungsfähig genug, und war auch nicht sehr orthoginal, mit nur Register A als Ziel der Arithmetik und Logik, und nur HL für Adressen.

Auffällig ist auch der Effekt von Spezialbefehlen, schnell wenn sie genau treffen und man sie nutzen kann, nutzlose Siliziumverschwendung wenn man sie nicht (mehr) nutzen kann. Gerade wenn der Compiler sie nicht nutzen kann, wird auch kein einziges damit compiliertes Program sie nutzen, sie werden vollständig nutzlos. Das ist auch das Hauptargument der Reduced Instruction Set Computer (RISC) Fraktion, dass Compiler diese oft nicht nutzen, und damit auch alle compilierten Programme, was heute fast alle Programme ist, und man sie daher weglassen sollte.

Dem halten die Complex Instruction Set Computer (CISC) Leute entgegen, dass sie doch von teils Programmen nutzbar sind, vor allem in kurzen zeitkritischen Assembler Routinen, zur Optimierung, und daher bleiben sollten. Und gerade die OVER Optimierung (und ROT ist Vergleichbar) zeigt was man mit einmaliger Optimierung im Compiler herausholen kann, wonach alle damit compilierten Programme etwas schneller werden, ohne weiteren Einsatz derer Programmierer.

Subroutine Threading

Wenn man für jeden einzelne Forth Wort immer wieder diese z.T. langen Befehlsfolgen wiederholt, wird gerade auch bei BC benutzen ein massive Menge an Code entstehen, mit viel Speicherverbrauch. Das kann man realistisch nur verwenden auf Prozessoren mit 2 PUSH/POP-baren Registerpaaren, oder gar Allzweckregister (General Purpose, GP), jedenfalls nur mit automatischem verändern. Oder man verwendet es wenn man viel Speicher opfern kann, was C Compiler genau machen, aber Forth Leute nicht mögen.

Alternative ist, diese "Elementaroperationsfolgen" alle als kleine Unterprogramme anzulegen, sogenannte Primitives in der Forth Terminologie. Diese sind entweder als Teil einer Runtime Library (RTL) vorhanden, die in jedes Programm angehägt werden muss, oder als DLL vorliegend die geladen wird, bzw sind bei Forth im Dictionary darin, und damit bereits geladen und beim Compilieren bereit zum gleich linken. Deren Aufruf ist dann nur noch jeweils ein 3-Byte CALL Befehl. Am Schluss geht es dann zurück mit einem zusätzlichen RET.

Die compiliertem Programme sind dann nur noch viele CALLs, als eine Aufrufliste, sogenannte Secondaries in der Forth Terminologie. Am Schluss steht wieder ein RET, oder wenn nur CALLs erwünscht sind ein CALL Exit (wobei diese "nur CALLs" Variante aber ohnehin von CALL Literal mit seinem Zahlwert danach ad absurdum geführt wird, also keinen grossen Sinn macht). Besonders optimal macht dies cmForth, welches wenn der letzte Befehl ein CALL war, dieses durch ein JMP ersetzt, statt ein RET dahinter zu compilieren, was Code und Returnstack Platz und Speicherzugriffe spart, ein Verfahren das als tail call Optimierung bekannt ist.

Damit ist der Compiler einfacher (er muss nur noch Aufruflisten erzeugen) und portabler (er muss nur den Befehlscode von CALL kennen, sowie vielleicht noch den von RET, wenn kein CALL Exit benutzt wird, und vielleicht noch den von JMP, wenn tail call optimiert wird). Damit wird auch decompilieren möglich, weil man von den CALL Befehlen ihren Adressen wieder zu den Namen der compilierten Routinen zurückfinden kann.

Eine Ausnahme gilt für Zahlenwerte: Die jeweilige Zahl, die von mal zu mal variert, kann nicht ins Primitive eingebaut werden, ohne eine massive Menge an Primitives zu generieren. Hier braucht es also eine generische CALL-bare Routine, die den Zahlenwert hinter dem CALL Befehl im aufrufenden Program stehend erwartet, wobei diese Routine den Wert aus dem Program auf den Datenstack kopiert, und dann deren Ausführung als Code verhindert (indem es sie überspingt).

Diesen Ansatz nennt man in der Forth Welt zumeist subroutine threading, im Vergleich zu den anderen später beschriebenen threading Techniken. Er ist auch alternativ als subroutine compiling bekannt, im Vergleich zur bisherigen direct compiling Technik, die soviel Platz brauchte.

Der subroutine threading Code wäre dann (nur teilweise, zum den Resten nicht wiederholen):

Einmalig, die Primitives:
(Dies wird in der Dictionary gespeichert)
+
Add:
LDAX B; INX B; MOV E,A
LDAX B; INX B; MOV D,A
DAD D
RET
-
Sub:
LDAX B; INX B; SUB L; MOV L,A
LDAX B; INX B; SBB H; MOV H,A
RET
AND (und analog OR und XOR)
Ist wieder wie -, nur die SUB/SBB durch 2 mal ANA ersetzen, und ist wieder auch kommutativ
DUP
Dup:
MOV A,H; DEX B; STAX B
MOV A,L; DEX B; STAX B
RET
Alle DROP SWAP ! @ sowie OVER ROT
Sind identisch gemacht wie oben bei Zwei Stacks, nur mit Labels (Drop: Swap: Store: Fetch: Over: Rot:) davor und RET dahinter addiert
Zahlwerte (egal für welchen Wert)
Literal:
(Der Name Literal ist schlicht englisch für Zahlwert)
MOV A,H; DEX B; STAX B
MOV A,L; DEX B; STAX B
(Das ist noch der normale PUSH, wie bei DUP, dann überschreiben wir die im HL verbliebene TOS Kopie)
POP H
(Der eigentliche Zahlwert ist nirgendswo hier, weil er im aufrufenden Program ist. Oben auf dem Returnstack ist aber die Adresse unseres Zahlenwertes weil der CALL Literal ja letztlich PUSH PC; JMP Literal gemacht hat, also kann man diese Adresse mit POP in HL holen)
MOV E,M; INX H
MOV D,M; INX H
(Via dem den Zahlenwert temporär in DE holen)
PUSH H
(Der neue nach-Zahlenwert PC Wert muss nun, mit der +2 (wegen den geholten Daten überspringen!), wieder auf den Returnstack zurück, daher oben auch beide INX H)
XCHG
(Jetzt die Daten von DE nach HL, auf das TOS. Daher muss auch ein PUSH H; RET benutzt werden, statt PCHL. Hier kollidieren der HL Gebrauch als TOS wegen DAD und das HL als einziges Register für PCHL)
RET
(Solche Techniken sind recht haarig, aber normale Welt für Compilerschreiber)
>R
Push:
(Hier ist ein Problem, dass die CALL Push/Pop ihre Returnadressen im Weg sind, und Push diese zudecken bzw Pop diese entfernen würde. In beiden Fällen wäre der RET am Schluss ein Absturz)
XTHL
PUSH H
(Damit wird das TOS von HL unter die >R Returnadresse gelegt, durch zuerst mit XTHL anstelle der Returnadresse austauschen/hinlegen, und dann diese wieder darüber legen)
LDAX B; INX B; MOV L,A
LDAX B; INX B; MOV H,A
RET
R>
Pop:
MOV A,H; DEX B; STAX B
MOV A,L; DEX B; STAX B
POP H
XTHL
(Damit wird das TOS unter der R> Returnadresse hervorgeholt zu HL, durch zuerst dieses aufdecken, und dann beide austauschen)
RET
EXIT (sofern überhaupt vorhanden, nicht einfach RET benutzt)
Exit:
(Hier wird nur die eigene Rücksprungsadresse beseitigt, und dann mit dem RET die vom Secondary benutzt, und so zu dessen Aufrufer zurückgekehrt)
INX SP; INX SP
(Damit wird ein R> gemacht, ohne es in HL und somit auf den Datenstack zu befördern, also mit einem integrierten DROP, das ganze zusammen nennt man auch ein RDROP, daher ist es auch der selbige 2 mal INX SP Code wie beim Datenstack DROP im naiven Stack ohne TOS Cache)
RET

Wiederholt, in den Secondaries:
(Nur dies wird für jedes Wort wieder compiliert, was erheblich kompakter wird, der Grund für das ganze)
+
CALL Add
(Das addiert insgesammt zum BC Stack seinen 9 Speicherzugriffen noch weitere CALL Add 5 und RET 3, gibt damit 17)
Alle - AND DUP DROP SWAP ! @ sowie >R R> OVER ROT
Sind indentisch als CALL Sub And Dup Drop Swap Store Fetch sowie Push Pop Over Rot
23 (und alle anderen Zahlwerte analog)
CALL Literal
.DW 23
(Der Zahlenwert ist hier, nach dem CALL Literal Befehl eingefügt, der eine Spezialfall)
EXIT
CALL Exit
(oder gleich RET verwenden)

Subroutine Threading kostet aber auch einiges an CALL/RET Verwaltungsaufwand (2 Befehle, 8 Speicherzugriffe), was etwa 50% addiert. Es ist also kompakter aber langsamer. Solche Kompromisse muss man als Compilerbauer oft abwägen. Ist der Speicher wegen Program zu gross zu Ende gibt es einen Compilerabbruch ohne Program, oder zur Laufzeit einen Programmabbruch, oder gar Absturz, aber sicher kein Resultat. Anderseits ist länger Laufen wegen subroutine threading nur warten auf ein Resultat. Zweiteres ist weitaus weniger schlecht. Daher ziehen Forth Leute den Threading Ansatz vor, gerade auch von den Kleinspeicher Tagen her.

Beides, direct und subroutine compiling, sind aber auch mischbar, wie dies auch in cmForth gemacht wird. Daher kann man bis 3Byte immer (oder agressiver auch für 4..5..6Byte) direct compiling machen, und dann darüber zu subroutine compiling übergehen. Das ergibt schnell wo es nichts (oder wenig) Platz kostet, und kompakt wo die Aufrufkosten prozentual geringer werden.

Es ist aber auch bekannt, dass Programe oft 80% ihrer Laufzeit in nur 20% des Codes verbringen, in sogenannten hot spots. Daher kann man auch generelles direct compilieren für kleine häufig genutze zeitkritische Routinen benutzen, und subroutine compilen für den grossen Resten. Sowas nennt man dann inline Optimierung.

Im Extremfall reicht aber auch das nicht, und man fällt dann auf Assembler Optimierung zurück, bei dem man die zeitkritischen Routinen komplett in Assembler schreibt, und voll optimieren kann (wie oben bei OVER demonstriert), und dabei dann auch voll die CISC Spezialbefehle ausnutzen kann. Den Ansatz nennt man auch gemischtsprachliche Programmierung. Dazu haben viele Forth Systeme einen eigenen speziellen Assembler integriert, der so aufgebaut ist, dass er diese Routinen nebenbei zu weiteren Primitives werden lässt.

Direct Threading

Mit subroutine threading ist jedes dritte Byte in den Secondaries ein CALL Befehl sein Befehlscode (und die beiden anderen die 16bit Adresse der aufgerufenen Routine). Diese Befehlscodes einsparen erlaubt eine weitere Platzreduktion von 3-Byte auf 2-Byte, auf immerhin 1/3 kleiner, also -33%, weil man dann in den Secondaries nur noch die Adressen der Routinen speichert. Also nur eine Adressliste ohne CALLs statt einer Aufrufliste mit CALLs. Am Schluss geht es dann immer zurück mit der Adresse von Exit. Diesen Ansatz nennt man direct threading, im Vergleich zum obigen subroutine threading. Damit ist der Compiler noch einfacher (er muss nur noch Adresslisten erzeugen) und noch portabler (er muss keine Befehlscodes des verwendeten Prozessors mehr kennen, nur noch Adressen).

Diese Adressliste ist damit aber nicht mehr via dem im Prozessor eingebauten PC und Befehlsdecoder Mechanismus ausführbarer Code. Man muss daher diese Adressen explizit selber ausführen, was auf diese interpretieren hinausläuft. Das Interpretieren der Adressen braucht eine Nachbildung des Prozessors seines Befehlsausführungs Mechanismuses. Diese wird der innere Interpreter genannt ("innerer" zum ihm vom "äusseren" Kommandointerpreter zu unterscheiden). Das Forth System hat damit dann eine gemischt compilierte (die Adresslisten erzeugen) und interpretierte (die Adresslisten ausführen) Implementation.

Es sind dazu einerseits ein Registerpaar als eigenen "Programmzähler" nötig, den Interpreter Pointer (IP), und anderseits ein paar Routinen, die diesen bearbeiten:

Routine Next
Benutzen des IP zum einlesen von Adressen und Sprung zur Routine, sowie IP++ rechnen, analog zum Programzähler. Dieser ist daher auch bekannt als der Adressinterpreter. Am Ende aller Primitives steht neu JMP Next statt RET. Alternativ kann man etwas Platz opfern zum schneller werden, indem man am Ende jedes Primitives eine Kopie von Next hinstellt
Routine Docol, eigener "CALL"
(In manchen Forths auch Docolon oder Enter oder Nest genannt.) Den IP des aufrufenden Secondaries auf den Returnstack abspeichern und dann neu laden mit dem Anfang des aufgerufenen Secondaries, gefolgt von JMP Next. Am Anfang eines jeden Secondaries steht dafür ein CALL Docol, zum dieses aufrufen und die Adresse der darauf folgenden Adressliste für den neuen IP mitgeben (und auch einen Teil der -33% Einsparung wieder auffressen). Dieser Block mit dem einzigen CALL, und damit dem einzigen vom Prozessor abhängigen Code, wird code field genannt, der Rest (die Adressliste) wird parameter field genannt. (Die Primitives verändern den IP nicht, da sie ja wie gehabt den PC benutzen, da sie ja weiterhin aus normalem Code bestehen, und rufen daher auch kein Docol auf.)
Routine Exit, eigener "RET"
(In manchen Forths auch ;S oder Semis oder Unnest genannt.) Den IP vom Returnstack her zurücksetzen, für weiter mit dem aufrufenden Secondary weiterfahren. Die Adresse von Exit steht am Ende jedes Secondaries seiner Adressliste, weil diese alle aus anderen Secondaries aufgerufen werden. Exit ist selber ein normales Primitive, und macht damit auch am Schluss ein JMP Next (Die Primitives rufen auch keine Secondaries auf, verändern damit IP nicht, und rufen daher auch kein Exit auf.)

Der IP braucht damit ein weiteres Registerpaar. Wir haben aber keines mehr frei im 8080, mit BC als Datenstackadresse, DE für Temporäres (inklusive dem zweiten Stackelement) und HL als TOS. Also muss man hier den TOS Cache im HL aufgeben, wieder wie beim naiven Code arbeiten, was noch langsamer wird, oder ihn anderstwo hinlegen, falls man noch einen Platz dafür findet.

Nach dem JMP Next beinhaltet Next wiederum am Schluss einen PCHL, weil dies weitaus schneller ist als PUSH H; RET (es spart 5 Speicherzugriffe pro Next, und Next ist sehr häufig, es dominiert mehr als alles andere die Forth Geschwindigkeit). HL ist dabei nötig für den PCHL Sprungbefehl (Bei einem Z80/U880 geht dies auch mit den IX und IY Registern, die sind aber langsamer). Also ist HL nur noch temporär nutzbar, und damit weder als IP noch als TOS (womit uns DAD auch noch verloren geht). Also Temporär in HL anstelle von DE machen, und damit wird DE als IP benutzbar (und ist dazu wegen XCHG besser als BC). Für einen TOS Cache bleibt also definitiv kein Platz.

Mit dem inneren Interpreter brauchen aber auch keinerlei CALL/RET mehr dafür, nur noch JMP/PCHL. SP wird somit wieder frei, und damit der Prozessorstack wieder für einen schnellen Datenstack nutzbar mit PUSH/POP! Stattdessen benutzen wir BC für unseren (seltener benutzten) Returnstack. Mit PUSH/POP kann man in den meisten Primitives einen Teil vom erhöhten Zeitverbrauch wieder einsparen, dafür wird es einmal pro Secondary Anfang/Ende im Docol/Exit mit BC langsamer. (Bei einem Z80/U880 kann man anstelle von BC auch IX oder IY nehmen, die zwar nochmals leicht langsamer sind, aber BC dann als TOS benutzbar machen, in allen Primitives, was das wieder locker aufholen sollte.)

Der direct threading Code wäre dann (nur teilweise, zum den Resten nicht wiederholen):

Routine Next (eigentlich JMP Speicher[DE++] machen)
Next:
LDAX D; INX D; MOV A,L
LDAX D; INX D; MOV A,H
PCHL
(Das addiert weitere 9 Speicherzugriffe, mit dem aufrufenden JMP Next sogar 12, aber diese ersetzen die subroutine threading CALL/RET ihre 8)
Routine Docol (CALL, eigentlich Speicher[--BC]=DE und DE=neu)
Docol:
MOV D,A; DEX B; STAX B
MOV E,A; DEX B; STAX B
POP D
(Vom CALL Docol unten her ist der neue DE IP Wert auf dem Prozessorstack gelandet, was unser Datenstack ist, nicht Returnstack, aber der POP entfernt ihn problemlos, er ist nur temporär dort)
JMP Next
(Eine alternative Technik ist möglich, weil der neue IP Wert, wenn auch nur minus 3, vom PCHL her noch in HL steckt. Statt CALL Docol kann man nur ein JMP Docol machen (spart 2 Speicherzugriffe), und statt POP D ein XCHG; INX D; INX D; INX D (das ist zwar 3 Befehle und 3 Bytes mehr aber nur 1 Speicherzugriff mehr, das spart insgesammt 1 Speicherzugriff))
Am Anfang jedes Secondary
CALL Docol (bzw JMP Docol)
(Dann gefolgt von einer Adressliste:)
.DW Adresse1
.DW Adresse2
.DW ...
Routine Exit (Return, eigentlich DE=Speicher[BC++] machen
Exit:
LDAX B; INX B; MOV A,E
LDAX B; INX B; MOV A,D
JMP Next
Am Ende jedes Secondary
.DW Exit
Der Rest, die eigentlichen Primitives
Der Code ist ähnlich wie oben bei naiv mit Prozessorstack, aber analog zu Subroutine Threading, jeweils einmal Primitive mit Label und danach aber JMP Next statt RET.
Wiederholt, in den Secondaries:
(Nur dies wird für jedes Wort wieder compiliert, was erheblich kompakter wird, der Grund für das ganze)
+
.DW Add
Alle - AND DUP DROP SWAP ! @ sowie >R R> OVER ROT
Sind indentisch als .DW Sub And Dup Drop Swap Store Fetch sowie Push Pop Over Rot
Zahlwerte (egal für welchen Wert)
Literal:
MOV A,H; DEX B; STAX B
MOV A,L; DEX B; STAX B
(Das ist wieder der normale PUSH auf den Datenstack)
XCHG
(Der eigentliche Zahlwert ist nirgendswo hier, weil er im aufrufenden Secondary ist. Nach Next zeigt der IP (= DE) aber bereits auf den Zahlwert, also kann man jetzt den Zahlenwert via HL in DE holen)
MOV E,M; INX H
MOV D,M; INX H
XCHG
(Der neue nach-Zahlenwert IP Wert muss nun, mit der +2 (wegen den geholten Daten überspringen), wieder ins IP (= DE) zurück, daher auch beide INX H. Damit sind auch die Daten von DE ins HL, und damit auch ins TOS)
JMP Next
23 (und alle anderen Zahlwerte analog)
.DW Literal
.DW 23
(Der Zahlenwert ist hier, nach dem CALL Literal Befehl)

Das wäre bei einem Add nun 9+12=21 statt 9+8=17, also nochmals 25% mehr, was für 2 statt 3 Bytes akzeptabel ist, bei -33% weniger.

Eine riesiges Problem haben wir aber: Dort in der naiven Implementation hatten wir mit HL und DE zwei temporäre Registerpaare, jetzt haben wir nur einen einzelnen mit HL. Hier gehen uns schlicht die Register aus. Der Ansatz mit dieser Registeraufteilung wird damit zu Makulaur, und damit unser ganzer Code der ihn benutzt, und wir fangen wieder von vorne an :-(. Auch das ist ein Teil des Compiler schreibens, ein sehr frustrierender!

Die Arithmetik kann man mit HL und A in 2 Teilen machen, statt mit HL und DE in einem, nur ist dann nichts mehr mit PUSH/POP, die immer 2 Bytes holen. Also ist auch nichts mehr mit SP als Datenstack, das nur 2 Bytes mit PUSH/POP/XTHL kann. Also wieder zurück zu Returnstack mit SP und Datenstack mit BC, und damit den Zeitverbrauch Einsparer verlieren. Wir sind damit wieder bei dem Subroutine Threading Code als Basis, aber auch noch ohne TOS. Hier ist nur noch eine Kostprobe davon, wie gross und langsam das inzwischen wird:

+
Add:
LDAX B; INX B; MOV L,A
LDAX B; INX B; MOV H,A
LDAX B; INX B; ADD L; MOV L,A
LDAX B; (kein INX B); ADC H; (kein MOV H,A)
(kein MOV A,H); (kein DEX B); STAX B
MOV A,L; DEX B; STAX B
JMP Next

Das alles ergibt weiteren Verwaltungsaufwand und Code dafür, und braucht auch weitere Zeit. Insgesammt 22Add+3JMP+9Next=34, also nochmals doppelt im Vergleich zu den 9+8=17. Es wird also wieder einiges langsamer zum diese 1/3 an Platz sparen. Also nochmals kompakter aber nochmals langsamer. Damit ist diese ein weiterer möglicher Kompromiss von Speicherverbrauch und Wartezeit. Es gibt aber auch Prozessoren, wo direct threading schneller ist als subroutine threading. Einer davon ist der weiter unten beschriebene 6809.

Bei einem 8080 ist direct threading ein so schlechter Kompromiss, dass ich lieber den Speicher für subroutine threading opfere, und daher hier gar nicht weiteren Code produziere. Bei Z80/U880 mit Returnstack in IX oder IY, und Datenstack in SP, und TOS Cache in BC, und HL als ein temporär ist der Kompromiss dagegen durchaus akzeptabler. Das wird auch im CamelForth so gemacht, das für den Z80 direct threading benutzt. Anderseits wird auch dort beim 8051 davon abgesehen, und subroutine threading benutzt.

Leider ist direct threading (und alle folgenden threading Arten) auch nicht mehr mit direct compiling und/oder subroutine compiling/threading mischbar. Und damit kann man es auch nicht einmal für kompakt compilierbare Worte schneller machen. Also keine inline Optimierung. Das ist eine fundamentale Limite. Man kann aber immer noch hot spots beschleunigen, aber auch nicht inline, sondern nur indem man diese ihre Routinen komplett in Assembler optimiert, mit diesen Routinen dann als Primitives.

Indirect Threading

Eine alternative Form davon ist indirect threading. Es spart auch beim CALL Docol im code field am Anfang jedes Secondaries noch den Befehlscode ein, indem auch dort nur die Adresse von Docol steht. Das ist eine sehr geringe Einsparung. Wenn man die im "offiziellen" optimalen Forth Programmierstil empfohlenen durchschnittlich 10 Worte pro Secondary annimmt, dann ist er nur noch 1/10 zusätzlich zu obigem, also noch -3% Platz, nachdem das ganze code field bei 10 Worte pro Secondary schon +10% addierte.

Mit nur der Adresse von Docol im code field sind die Secondaries auch nicht mehr mit PCHL anspringbar. Vielmehr muss Next das nun ebenfalls dereferenzieren, zum Docol selber finden, und dann erst dieses anspringen, also auch den CALL Docol (bzw den JMP Docol) selber ausführen. Das ist dann damit doppelt indirekt, und weiter langsamer. Dafür fehlt aber auch die Ausführungszeit vom CALL (bzw JMP) Befehl ganz. Wegen ihrem Fehlen ist auch die neue IP Adresse nicht mehr auf dem Prozessorstack zu finden, also wird diese zumeist als Zwischenstufe in ein weiteres Registerpaar namens W (= working) gelegt, wo Docol es dann hernehmen kann.

Dazu kommt aber auch, dass die Primitives nun nicht mehr direkt ausgeführt werden, weil Next eine Adresse erwartet und keinen Code, weswegen diese zusätzlich zu ihrem Code ihre eigene Adresse vor sich haben müssen, die auf den Code gleich danach zeigt, was diese leicht grösser macht (und die geringe Platzersparnis reduziert), und ebenfalls leicht langsamer macht.

Der indirect threading Code wäre dann (zu Vergleichszwecken kompatibel zu obigem gescheiterten Ansatz, und nur teilweise, zum den Resten nicht wiederholen):

Routine Next (eigentlich W=Speicher[DE++] und JMP Speicher[W] machen)
Next:
LDAX D; INX D; MOV A,L
LDAX D; INX D; MOV A,H
PUSH H
(Mangels Register wird der Prozessorstack als langsames W Register missbraucht, und das ausgerechnet in Next, das ohnehin zeitkritisch ist, *brrr*). (Eine Z80/U880 könnte das im verbleibenden von IX oder IY zwischenspeichern.))
MOV A,M; INX H
MOV H,M; (kein INX H)
MOV L,A
PCHL
(Das erste Byte in A zwischenspeichern, damit HL noch erhalten bleibt zum das zweite Byte holen. Das kommt direkt in H, weil nichts mehr frei, dann A zu L. Das passt gerade noch, ist aber unfreundlich, *brrr* die Zweite. Und hier verliert man das Temp (und W) in HL, wesshalb es oben auf dem Prozessorstack abgelegt werden musste)
Routine Docol (CALL, eigentlich Speicher[--BC]=DE und DE=W machen)
Docol:
MOV D,A; DEX B; STAX B
MOV E,A; DEX B; STAX B
POP D
(Hier kommt das W zurück, nachdem die Adresse von Docol im HL durch das PCHL verwertet worden ist)
INX D; INX D
(Es fehlt nun aber die Wirkung der beiden INX in Next, dem gemachten und dem ausgelassenen, also muss man dies hier nachholen. Es ist diesmal der neue IP Wert minus 2, also muss auch noch wie bei der JMP Docol Variante korrigieren, diesmal nur 2 weil nur die Docol Adresse dort war, statt 3 wegen JMP Docol)
JMP Next
Routine Exit (Return, eigentlich DE=Speicher[BC++] machen
Ist genau gleich wie bei direkt threading, weil es auch dort bereits durch die parameter field Adressliste aufgerufen wurde
Der Rest, die eigentlichen Primitives
Die sind sowieso identisch wie bei direkt threading, auch durch die Adressliste im parametier field aufgerufen, mit dem selbigen Registermangel, und damit auch ohne TOS Cache und ohne Prozessorstack als Datenstack

Dies ergibt einen weiteren möglichen Kompromiss von Speicherverbrauch und Wartezeit. Der ist beim 8080 noch schlechter, weil Registerknappheit mit W noch schlimmer wird. Wesshalb man sich ernsthaft fragt, wesshalb jemand das so machen würde. Es gibt aber tatsächlich Prozessoren wo indirect threading schneller ist als direct threading. Einer davon ist der Pentium. Dort wurden gegenüber dem 486 erstmals 2 separate Code und Daten Caches eingeführt. Zuerst den CALL/JMP als Code lesen, und gleich danach die Adressliste als Daten, verwirrt die beiden Caches ihre Zuständigkeit. Einfach regelmässig ein Secondary aufrufen, was man dauernd macht, resultiert damit bereits in wiederholtem Code/Daten Cache hin und herschalten, und die wiederholte Verwirrung bremst den Prozessor aus. Er wird langsamer als wenn er gar keinen Cache hätte, also 386er Geschwindigkeit!

Historisch hat FIG Forth immer indirect threading benutzt, egal auf welchem Prozessor, zum den Speicherinhalt der Secondaries einheitlich halten (code field und parameter field), ohne vom Prozessor abhängigen CALL/JMP Befehlscode (oder gar variable Länge davon) im code field, und damit den Compiler identisch (und einfacher) halten (nur Adresse ins code field schreiben). Ausserdem war alles im Secondary (parameter field und code field) als Adressen halten etwas eleganter, ebenso dass Secondaries und Primitives alle mit einer code field Adresse (CFA) anfangen (und damit identisch formatiert machen). So wurde indirect threading zum Standard, sogar in dem Masse, dass viele Leute Forth mit indirekt threading gleichsetzen, weil sie nichts anderes kennen, obwohl auch einiges anderes geht.

Aktuelles heutiges Forth ist aber öfter mit direct threading, weil das fast immer schneller ist, oder gar mit subroutine threading, sogar mit inline Optimierungen, bis hin zu direct compiling, oder gar dort Fall zu Fall Optimierungen der Übergabekonvention (so wie wir es in OVER von Hand gemacht haben).

Token Threading

Noch nicht langsam genug? Da gibt es als ultimative Speichersparvariante noch das token threading. Dabei wird die Menge Worte auf 256 begrenzt, und dann in den Secondaries nur jeweils 1 Byte Tabellenindex gespeichert, eben den Token. Das spart nochmals -50% Platz gegenüber direct und indirect threading, oder gar -67% gegenüber subroutine threading. Das ist noch langsamer, wegen man die bei jedem Wort im Next die Tabelle dereferenzieren muss, was noch mehr Zeit kostet. Das ist also nur für minimalsten Platz relevant. Ich werde hier daher jegliche token threading Implementation weglassen, weil die nicht mehr wirklich relevant sind.

Ich erwähne diese hier auch nur, weil teils speziell für Forth entwickelte Prozessoren dieses verwenden (mit Hardware Tabelle und Dereferenzierung zum schnell sein), darunter die MuP20/P20 MuP21/P21 F21 i21 ganz am Schluss. Aber auch manche BIOS ROMs (das OpenFirmware der neueren Sun Sparc sowie der PPC Macintoshes) verwenden einen token threading Forthabkömling, für den Code in Einsteckkarten ROMs, weil dieses sowohl von der CPU (SPARC oder PPC) wie auch von Adressen des ROMs und des Motherboards unabhängig ist.

(Token threading kann unter manchen Umständen sogar recht schnell sein. Der SoftVGA Bildzeilenzeicher ist, wie im SoftVGA Kapitel vom Softe Hardware Vortrag beschrieben, ein kleiners token threading System, mit dem Bildinhalt im Videospeicher aus Tokens bestehend, das alle 12 Speicherzugriffe einen Streifen von 4 Pixel zeichnet, mit 4 Takte für die 4 OUT Befehle und dazwischen 4*2=8 Takte zum den Next Entthreader laufen lassen zum den nächsten 4 Pixel Streifen ermitteln. Das geht aber auch nur, weil der AVR sehr effektiv im Tokens entthreaden ist, und weil die für 2^4=16 Muster nötigen Primitives (je 10Wort/20Byte) in 256Wort/512Byte passten, was nur 8bit Tabellenrechnung für die Adressen brauchte. Mit anderem als einen AVR wäre das ganze Projekt niemals möglich gewesen. Und ohne meine Forth Interna Kenntnisse wäre ich nie auf diesen Token Ansatz gekommen!)

Compilier

Damit wissen wir nun, was an Code oder Aufrufen oder Adressen im Speicher drin ist, und wie es ausgeführt wird. Nun wenden wir uns der Frage zu, wie es dorthin kommt, also wie der Compilier den Code generiert. Genauer der Frage, was passiert, wenn jemand:

: QUADRAT DUP * ;<Enter>
2 QUADRAT .<Enter>

eingibt, bis Forth nach der ersten Zeile OK und nach der zweiten 4 OK ausgibt.

Dazu wird der Forth Interpreter für beide Zeilen benutzt, welcher am Schluss vom verarbeiten die beiden OK ausgibt, sowie für die erste Zeile der Forth Compiler vom Interpreter aus gestartet, sowie für die zweite Zeile die Ziffer 2 und unser neues Wort QUADRAT und das bestehende Wort . (als "print" ausgesprochen), wobei letzteres die errechneten 4 ausgibt. Hier schauen wir zuerst mal den Forth Compiler an. Das Wort : (als "colon" ausgesprochen) ist das eigentliche Forth Compiler Programm, das jetzt vom Interpreter aufgerufen wird. Es ist selber ein Secondary, wurde also in Forth geschrieben.

Alle Forth Worte, bestehende wie : und neue wie QUADRAT, egal ob Primitive oder Secondary oder sonstwas, können nur vom Interpreter ausgeführt werden, wenn ihr Name im Dictionary vorhanden ist. Also ruft :, wie jedes Wort das Worte erzeugt, als erstes ein weiteres Secondary namens CREATE auf, das dann aus der Eingabezeile die Zeichen QUADRAT (bis zum ersten Leerzeichen) liest, und einen gleichnamigen Dictionary Eintrag für das neue Wort erstellt, seinen dictionary header. Auf was dabei genau passiert (vor allem die gebildeten Dictionary Datenstrukturen) gehe ich hier nicht weiter ein. Dies hat nichts mit Code generieren zu tun, und ist je nach Forth Variante auch sehr verschieden. (Ebenso geh ich auch nicht auf Forth seine Datenein-/-ausgabe ein, weder Tastatur/Bildschirm noch Disk.)

CREATE addiert danach auch noch ein minimales code field, das die Routine Docreate aufruft, das nichts anderes macht, als bei Aufruf des neuen Wortes die Adresse nach dem dictionary header (und dem code field) auf den Datenstack legen (also die Adresse des parameter field (PFA)), und dann das Wort beenden. Das ist einerseits damit das neue Wort wenigstens etwas sinnvolleres macht als einen Absturz. Anderseits erlaubt das dem Benutzer direkt CREATE zu benutzen, zum Namen für eigene Datenstrukturen anzulegen. Diese sind dann im jeweiligen parameter field untergebracht, wozu dann Platz für sie im Dictionary zu reservieren ist (mit dem ALLOT Befehl), und danach auf dieses Wort seinem parameter field zuzugreifen ist (via dem PFA das es auf dem Datenstack ablegt). Genauer ist das code field bei direct compiled ein wenig Code der dies macht, bei subroutine threading und direct threading ein CALL Docreate, und bei indirect threading die Adresse von Docreate, was nicht wirklich überrascht.

Das code field ist bei Datenstrukturen immer nötig, aber bei Secondaries je nach System überflüssig, und wird daher teils von : überschrieben. Nach CREATE wird bei direct compiled und subroutine threading den Aufruf komplett beseitigt, bei direct threading und indirect threading dagegen dessen Adresse mit Docol überschrieben. Daher heisst dies auch Docol, so wie CREATE sein Docreate benutzt, benutzt : sein Docol.

Dann wird zum eigentlichen compilieren der von Benutzer gegebenen Worte DUP * ; übergegangen, die Routinen dazu zu ermitteln und eintragen, sei das als Code oder Aufrufe oder Adressen. Dazu wird der Befehl ] benutzt. Er hat diesen eigenartigen Namen, weil man mit [ (als "left bracket" ausgesprochen) den Compiler unterbrechen kann, dann etwas berechnen (z.B. zur Compilezeit eine Konstante erzeugen statt als fertige Konstante im Source eingeben oder zur Laufzeit immer wieder neu berechnen), und dann mit ] (als "right bracket" ausgesprochen) weiter compilieren kann.

Je nach Forth System kann compilieren von ] auf 2 Arten gemacht werden:

Egal welches, werden nun wieder aus der Eingabezeile die Zeichen DUP eingelesen (wieder bis zum Leerzeichen). Dieses Wort wird im Dictionary gesucht, mit ' (als "tick" ausgesprochen), und dessen code field Adresse auf den Datenstack gelegt. Auf was dabei genau passiert (vor allem die Dictionary Datenstrukturen absuchen) gehe ich hier ebenfalls nicht weiter ein. Dies hat auch nichts mit Code generieren zu tun.

Dann wird es im neu entstehenden Secondary, am nächsten freien Platz (der HERE genannt wird), durch das Wort , (als "comma" ausgesprochen) eincompiliert, das ein ! macht gefolgt von HERE verschieben. Bei direct compiled wird der Code der dies macht hineinkopiert (wofür das Primitive die Codelänge und den Code beinhalten muss), und bei subroutine threading ein CALL und die Adresse hingeschrieben, und bei direct und indirect threading nur die Adresse hingeschrieben.

Das wird alles endlos wiederholt, und damit nach dem dup auch für das * und ;. Ausnahmen davon gibt es nur zwei:

Das Wort ; (als "semicolon" ausgesprochen) ist immediate. Es compiliert zuerst bei direct compiled ein RET, und bei subroutine threading ein RET oder CALL Exit, und bei direct und indirect threading die Adresse von Exit (deren eigenes "RET"). (Die Exit Alternativnamen ;S und Semis kommen von ; (semicolon) her, das sein ;S oder Semis benutzt). Dann bricht ; aus der Compilerschleife aus, bzw bricht sie ab, durch [ benutzen. (Das [ ist übrigens auch ein immediate Wort, weil es ja auch direkt zum compilieren kurz unterbrechen aufrufbar ist.)

Je nach Forth System kann compilieren beenden von [ wieder auf 2 Arten gemacht werden:

Programmstrukturen

Programme die nur eine gerade Serie von Befehlen ausführen sind langweilig, selbst wenn sie beliebig oft verschachtelt andere (Unter-)Programme aufrufen können. Erst Verzweigungen, und damit auch abbrechbare Schleifen, machen Programme wirklich interessant.

Die Verzweigungen und Schleifen werden dabei aus Sprungbefehlen zusammengesetzt, teils unbedingte, aber zumeist bedingte. Das ist auch bei Forth so. In direct compiled kommen dazu stets normale Prozessor Sprungbefehle zum Einsatz, und bei subroutine threading ist unbedingter Sprung ein normaler JMP Befehl oder ein CALL Branch (wie auch am Schluss RET oder CALL Exit sein kann) aber bedingt ist stets ein Call Zbranch (wie auch für Zahlwerte stets Call Literal ist), und bei direct und indirect threading kommen wieder Adressen von eigenen IP verändernden Branch und Zbranch Routinen zum Einsatz:

Routine Branch, eigener "unbedingter Sprung" (In manchen Forths auch Else genannt)
Den PC oder IP neu laden mit der Fortsetzung des Secondaries. (Das ist wegen unbedingt sein keine Verzweigung, und damit ein Jump und kein Branch. Der Name ist hier schlecht gewählt. Das kommt vermutlich von Forth seinem entstehen auf der IBM 1130, und IBM ihrem Gebrauch von Branch für alle Spünge)
Routine Branch, in subroutine threading, Primitive (sofern überhaupt vorhanden, nicht einfach JMP benutzt)
Branch:
(Dies ist analog zu Literal, nur mit Daten vom Program in den PC statt auf den Datenstack)
XCHG
(Zuerst das TOS in DE in Sicherheit bringen)
POP H
(Dann wie bei Literal die Rücksprungdresse vom CALL Branch holen, die auf die Branch Adresse zeigt)
MOV A,M; INX H
MOV H,M; (kein INX H)
MOV L,A
(Das zweite INX H entfällt, weil wir ohnehin springen, und daher die Adresse des Codes danach nicht mehr interessiert. H laden geht daher direkt, L muss via A weil HL noch benutzt wird, und DE mit TOS besetzt ist)
PUSH H
(Dann abspeichern für das RET)
XCHG
(Und das TOS von DE wiederherstellen, wieder PUSH H; RET weil TOS und PCHL Kollision)
RET
Routine Branch, in subroutine threading, Aufruf mit Adresse 42
CALL Branch
.DW 42
Routine Branch, in (in)direct threading, Primitive
Branch:
(Dies ist analog zu Literal, nur mit Daten vom Secondary in den IP (= DE) statt auf den Datenstack)
XCHG
(Zuerst das TOS in DE in Sicherheit bringen, und dabei kommt auch bereits das bestehende IP (= DE) ins HL)
MOV A,M; INX H
MOV H,M; (kein INX H)
MOV L,A
(Neues IP laden, nicht in DE, weil temporär TOS dort ist)
XCHG
(Beide IP und TOS zurück, wenigstens keine POP und PUSH/RET Orgie hier, da IP statt PC bearbeiten)
JMP Next
Routine Branch, in (in)direct threading, Aufruf mit Adresse 42
.DW Branch
.DW 42

Routine Zbranch, eigener "bedingter Sprung" (In manchen Forths auch ZeroBranch oder 0Branch oder ?Branch oder If genannt)
Falls die Zahl auf dem TOS gleich 0 ist (den Wert für "False", alles ausser 0 ist "True"), dann wie oben den PC oder IP neu laden, sonst den PC oder IP in Ruhe lassen und geradeaus weiter. Auf jeden Fall wird die Zahl im TOS vom Datenstack entfernt
Routine Zbranch, in subroutine threading, Primitive
Zbranch:
(Dies ist analog zu Branch, aber nur Sprung wenn TOS=0. Das TOS wird verbraucht, also nicht in DE in Sicherheit bringen)
MOV L,A; ORA H
(Bei beiden TOS Bytes = 0 ist nun A = 0 und Zero Flag = 1)
POP H
(immer holen wie gehabt)
JNZ Zb-Nojmp
  ("if", Sprung wie in Branch gehabt)
  MOV A,M; INX H
  MOD H,M; (kein INX H)
  MOV L,A
  JMP Zb-Done
Zb-Nojmp:
  ("else", kein Sprung, nur Adresse übergeh)
  INX H; INX H
Zb-Done:
PUSH H
(Abspeichern wie gehabt)
LDAX B; INX B; MOV L,A
LDAX B; INX B; MOV H,A
(TOS nachladen, wie bei DROP)
RET
Routine Zbranch, in subroutine threading, Aufruf mit Adresse 42
CALL Zbranch
.DW 42
Routine Zbranch, in (in)direct threading, Primitive
Zbranch:
(Dies ist analog zu Branch, aber nur Sprung wenn TOS=0. Das TOS wird verbraucht, also nicht in DE in Sicherheit bringen)
MOV L,A; ORA H
(Bei beiden TOS Bytes = 0 ist nun A = 0 und Zero Flag = 1)
JNZ Zb-Nojmp
  ("if", Sprung wie in Branch gehabt)
  XCHG
  MOV E,M; INX H
  MOV D,M; (kein INX H)
(Neues IP laden, direkt in DE, weil kein TOS dort ist)
Zb-Nojmp:
  ("else", kein Sprung, nur Adresse übergeh)
  INX D; INX D
Zb-Done:
LDAX B; INX B; MOV L,A
LDAX B; INX B; MOV H,A
(TOS nachladen, wie bei DROP)
JMP Next
Routine Zbranch, in (in)direct threading, Aufruf mit Adresse 42
.DW Zbranch
.DW 42

Zum diese nutzen muss eine Hochsprache spezielle Anweisungen beinhalten, zum die Verzweigungen und Sprünge definieren, mit der Ausnahme von unstrukturierten GOTO/IF..GOTO/GOSUB/RETURN Sprachen wie Basic, die direkt den Sprungbefehlen entsprechen (einfach mit Zeilennummern statt Labels). Dazu verwenden die meisten Sprachen verschiedenste strukturierte Konstrukte, die in Sprungbefehle umgesetzt werden müssen. In Forth sind diese speziellen Konstrukte auch nur Worte wie alles andere. Sie sind ebenfalls alle immediate Worte, die den Compiler erweitern und selber dann spezielle Sachen eincompilieren, wie das bei ; schon der Fall war, diesmal spezielel Sachen aus obigen beiden Sprungbefehlen zusammengesetzt. Weil diese compilieren sind sie auch nicht in Kommandozeilen erlaubt, es kann keine interaktiv ausgeführte Verzweigungen oder Schlefen geben. Es sind dies folgende Worte:

Verzweigung Bedingung IF .. THEN
Das IF compiliert als erstes ein Zbranch, welches bei Bedingung = 0 (= false) den .. Teil überspringen wird bis zu nach dem THEN. Mangels besserem Wissen wird dies als "offenen" Sprung (= die Adresse darin ist 0) compiliert. Als zweites speichert es die Adresse dieser offenen Adresse ab, bei manchen Forths auf dem Datenstack, bei anderen in einem speziellen Speicherbereich. Das THEN (= ENDIF in anderen Sprachen, das ist schlecht benannt in Forth) nimmt die aktuelle Adresse nach dem .. Teil und flickt dies an der von IF gespeicherten Adresse ein, womit der "false" Sprung nun genau richtig überspringt
Verzweigung Bedingung IF .. ELSE .. THEN
Das fakultative ELSE Teil macht nun beides. Als erstes wie IF etwas compilieren, aber ein unbedingtes Branch, welches "offen" ist, und nach dem "true" Teil ausführen immer den "false" Teil überspringen soll. Dann wird wie bei THEN dem IF sein Zbranch mit der Adresse für den "false" Sprung nachgeflickt. Und zuletzt wird dem ELSE sein neues "offenes" Branch seine Adresse gespeichert, damit THEN dieses dann flickt, unwissend dass es ersetzt wurde
Schleifen BEGIN .. AGAIN (endlos) und BEGIN .. Bedingung UNTIL (endlich)
Das BEGIN tut gar kein Code compilieren, es tut nur die aktuell Adresse abspeichern. Die AGAIN oder UNTIL compilieren dann einen Branch (endlos) bzw Zbranch (springt bei "false" und bricht damit bei "true" ab) und nehmen dann die von BEGIN abgespeicherte Adresse dafür
Schleife BEGIN Bedingung WHILE .. REPEAT
Hier haben wir Schleife und Verzweigung kombiniert. Nachdem BEGIN schon seine Adresse gespeichert hat, compiliert das WHILE wie IF einen Zbranch, und speichert eine zweite Adresse davon ab. Am Schluss kommt dann REPEAT, das einerseits einen Branch zu BEGIN seiner Adresse compiliert (wie AGAIN dies macht), und anderseits dem WHILE sein Zbranch flickt, zu nach dem Branch springen (wie THEN dies macht)
Schleifen Ende Anfang DO .. LOOP (mit +1) und Ende Anfang DO .. Schritt +LOOP (mit +/-beliebig)
Das DO compiliert als erstes Code der die beiden Ende und Anfang Werte auf den Returnstack(!) transferiert, damit sie aus dem Weg sind, und das mit Anfang zuoberst, damit es als Schleifenzähler mit dem I Befehl geholt werden kann. Als zweites speichert es wie BEGIN die aktuelle Adresse danach ab. Das LOOP compiliert Code der das obere Returnstackelement nimmt und 1 dazu addiert (der Anfang wird damit zum Schleifenzähler) und es mit dem zweiten (Ende) Wert vergleicht, und bei ungleich zur DO Adresse springt (wie ein UNTIL), bzw bei gleich nicht springt und danach die beiden Werte vom Returnstack entfernt. Ein +LOOP unterscheidet sich von LOOP nur darin, dass es anstelle von 1 das oberste Datenstack Element benutzt
Schleife Anzahl FOR .. NEXT (mit -1)
Obiges Ende Anfang DO .. LOOP ist eines der kompliziertesten Mechanismen im ganzen Forth, weil Charles Moore es von Fortran her kopiert hat. Später nervte ihn das, und er ersetzte es im vereinfachten cmForth durch etwas einfacheres. Das FOR compiliert als erstes Code der nur einen Wert zum Returnstack kopiert (>R), und speichert die Adresse ab. Das NEXT compiliert dann Code der 1 subtrahiert und springt solange nicht 0, bzw bei gleich 0 den Wert vom Returnstack entfernt, wie es Zbranch mit dem Datenstack macht
Keine BEGIN Schleifen
Auch die ganzen BEGIN Varianten sind dem Charles Moore inzwischen auch zu kompiziert. Sein neuestes MachineForth bzw colorForth kennt gar keine solchen Schleifenkonstrukte mehr! Schleifen macht man, indem man ab Schleifenanfang ein neues Wort definiert, das dann als letztes Wort sich selbst (= rekursiv) aufruft, wobei die seit cmForth schon vorhandene tail call Optimierung damit zu tail recursion wird, dessen JMP Befehl dann zum Branch einer BEGIN .. AGAIN Endloschleife wird. Ohne tail call Optimierung geht diese Technik nicht, weil sonst der Returnstack überschwemmt wird. Dieser Ansatz kommt von Lisp, das traditionell gar keine Schleifenkonstrukte kannte (und Charles Moore schon in den 1950ern kannte). Abgebrochen wird eine Schleife mit IF EXIT THEN, wobei EXIT das Wort abbricht, zurück zum Aufrufer. Ein Schleifenabbruch am Ende ergibt ein BEGIN .. UNTIL Verhalten, am Anfang ergibt BEGIN .. WHILE .. REPEAT, es geht aber auch mit zwischendrin oder gar mit mehreren Orten. Oder man verwendet IF Wort-rekursiv EXIT THEN, zum ein UNTIL bauen, mit nach der Schleife im Wort weitergehen. Da eine Schleife so immer direkt am Anfang ihres Wortes anfängt, muss allfällige Initialisierung in dem Wort passieren das dieses Schleifenwort aufruft. Das ist ein geringes Opfer für die Eliminierung von Konstrukten
Reduzierte Verzweigung Bedingung IF .. EXIT THEN ..
Aber auch die Verzweigungen wurden vereinfacht, das ELSE ist weg. Statt dessen wird am Ende des IF Teiles das Wort direkt mit EXIT verlassen, ohne je ein ELSE und dessen Branch gemacht zu haben. Da so eine Verzweigung immer direkt am Ende ihres Wortes endent, muss allfälliger gemeinsame Code nach der Verzweigung auch in Wort passieren das dieses Verzweigungswort aufruft. Auch das ist ein geringes Opfer für die Reduktion von Konstrukten

Die Grundregel ist also: Der erste im Source liefert/speichert seine Adresse, der zweite benutzt diese Adresse, wobei derjenige der springt (der Anfang bei Verzweigungen und der Schluss bei Schleifen) die Sprungbefehle compiliert.

Variablen und Konstanten

Variablen und Konstanten brauchen auch Namen und Platz in Dictionary, und sie müssen ebenfalls bei der Ausführung "angesprungen" werden können.

Ersteres ist einfach. VARIABLE und CONSTANT (und auch USER) machen wie : zuerst ein CREATE zum einen Dictionary Header generieren, wie gehabt mit dem Namen den CREATE aus der Eingabezeile liest. CREATE liefert auch wieder einen code field mit Docreate darin, für die Ausführung. Während : dies mit Docol überschreibt (oder gar entfernt), gehen VARIABLE und CONSTANT und USER hier ihre eigenen Wege:

Interpreter

Damit wissen wir nun, was für Code im Speicher ist, und wie er dorthin gekommen ist. Nun wenden wir uns der Frage zu, wie ausgewählt wird, was für Code ausgeführt werden soll. Genauer die Frage, was passiert, wenn jemand unser zuvor benutztes:

: QUADRAT DUP * ;<Enter>
2 QUADRAT .<Enter>

eingibt, damit Forth die : und 2 und QUADRAT und . ausführt, und danach seine beiden OK ausgibt.

Dazu wird der Forth Interpreter nach dem Aufstarten des Systmes automatisch gestartet. Dieser beinhaltet eine mit BEGIN .. AGAIN gemachte Endlosschleife, welche die Interpreterschleife genannt wird. Diese ist auch ein Wort, genauer ein Secondary, also auch in Forth geschrieben. Das Wort heisst übrigens QUIT. Wieder ein seltsamer Name wie bei ], weil man es hier auch mit dem Befehl QUIT aufrufen kann, zum ein Program beenden, indem man einfach wieder den Interpreter aufruft! Dieser wird am Anfang (und nach jeder Eingabezeile bearbeiten und dann das OK ausgeben) immer auch den Returnstack löschen zum aufräumen. Und er wird selber nie beendet (und der Returnstack ist nun ohnehin leer) und somit nie zum mit QUIT beendeten Program zurückkehren. Und wegen Neustart gitb es kein OK, weil das Schleifenende umgangen wird.

Zum ein Program wegen einem Fehler abbrechen wird ABORT" Meldung " benutzt, das die Fehlermeldung ausgibt, auch den Datenstack leert, und dann mit QUIT wie oben weitermacht. Der Systemstart selber macht zuerst COLD, das den Speicherinhalt aufbaut (bzw bei manuellem Aufruf zuräcksetzt), und dann ABORT" aufruft, das wiederum QUIT aufruft. Somit ist die ganze Arbeit auch manuell auslösbar, in immer drastischeren Portionen

In der QUIT Endlosschleife wird nach dem Returnstack löschen zum eigentlichen interpretieren der von Benutzer gegebenen Worte übergegangen, bestehende wie : und neue wie QUADRAT. Alle eincompilierbaren Befehle sind dabei auch direkt manuell ausführbar, was Forth erst sein interaktives Verhalten gibt. Alle Forth Worte, egal ob Primitive oder Secondary oder Variable oder Konstante, können vom Interpreter ausgeführt werden, wenn ihr Name (und code field und parameter field) im Dictionary vorhanden ist.

Was geschieht wenn die obige Rechnung mit DUP *<Enter> direkt eingegeben wird, statt in QUADRAT compiliert? Als erstes wird mit ACCEPT die Eingabe geholt bis zur <Enter> Taste, Dann wird die Eingabezeile mit INTERPRET ausgewertet.

Im INTERPRET selber werden wieder, wie im ], nun aus der Eingabezeile die Zeichen DUP eingelesen (wieder bis zum Leerzeichen). Wieder wird dieses Wort im Dictionary gesucht, mit ' (tick), und dessen code field Adresse auf den Datenstack gelegt. Was anderst gemacht wird, ist dass es nicht mit , (comma) ins Dictionary compiliert wird, zum später ausführen, sondern direkt mit EXECUTE ausgeführt wird. Das ist dem Forth sein Gegenstück zum PCHL beim 8080, das im primitivsten Fall nur ein R> macht, und dann sich beendet! Damit wird bei direct compiled und subroutine threading sein abschliessendes RET, und bei direct und indirect threading sein abschliessendes Exit plus dessen Next benutzt, welche dann zum derart "untergeschobenen" auszuführenden Wort "zurückkehren", und es so ausführen. Erst das ausgeführte Wort wird mit seinem RET oder Exit dem EXECUTE seinen eigentlichen Rücksprung machen, wieder ins INTERPRET zurück.

Es wird dabei also nichts in das Dictionary compiliert, auch nicht temporär. Daher sind auch im Interpreter keine speziellen compilierenden Immediate Worte ausführbar, weil kein Compiler aktiv ist. Daher sind auch Kommandozeilen mit Verzweigungen oder Schleifen darin unmöglich.

Das wird alles wiederholt bis zum <Enter>, und damit auch für das *. Ausnahme davon gibt es diesmal nur einen:

Es gibt kein ; Gegenstück am Ende der Eingabe. Das INTERPRET beendet sich nach dem <Enter> erreichen, und das QUIT druckt dann sein OK aus. Die Endlosschleife in QUIT wird nie verlassen, also wird für die nächste Runde der Returnstack wieder gelöscht, und eine weitere Eingabezeile geholt und ausgewertet, endlos.

Andere Prozessoren

Bisher habe ich in dieser Serie immer konsistent den 8080 benutzt, sowie genereller die Intel Welt gebracht, mit dem 8008 und seinen Nachfolgern 8080/8085, sowie dem erweiterten Zilog Z80/U880. Dies einerseits weil die Reihe 8008/8080/8085/Z80 sehr traditionell ist, anderseits weil viele Z80/U880 Systeme (und deren Benutzer) am VCFe sind, sowie weil in diesen sehr viele Details darin sind zum erklären, und nicht zuletzt auch weil ich mit dem Z80 angefangen habe.

Das Thema diesmal ist aber eigentlich nicht Forth, sondern Prozessoren vergleichen, mit Forth als Messlatte. Also will ich auch hier Forth Implementationen auf verscheidenen Prozessoren vergleichen, zum dabei zeigen, wie verschiedene Prozessoren ihre Features und Befehlssätze andere Compiler brauchen, bzw wie Prozessorfeatures (und auch fehlende davon) den Compilerschreiber beeinflussen.

Jetzt wo alles mit dem hier bestens bekannten 8080 vorgezeigt ist, zeige ich wie es bei anderen geht. Als Beispiele nehme ich:

Für jeden Prozessor gibt es zuerst eine Kurzeinführung, fokusiert auf die für Forth relevanten Eigenschaften, und dann 1 oder 2 Implementationen, vor allem mit Hinweisen was für Methoden bei welchem gut oder schlecht laufen und wieso.

Atmel AVR

Der AVR ist bereits vom Softe Hardware Vortrag her bekannt. Er wird daher hier nur kurz hier zusammengefasst. Der AVR ist ein 8bit Prozessor, mit fast gar keinen 16bit Befehlen (nur 16bit Register-Register Kopie, sowie für 4 Registerpaare +/- 6bit Konstante). Er hat 32 8bit Register, sehr viele, womit man viele Daten im Prozessor behalten kann. Er hat dabei keinen Akkumulator, statt dessen benutzen alle arithmethischen Befehle 2 beliebige Register als Operanden (statt A und Register oder HL und Register), mit dem Ergebnis in einem beliebigen Register (dem ersten der beiden Operanden). Das nennt man einen Zweiadressrechner. Das ist viel flexibler und spart einiges an Herumschieberei.

Die Register haben aber abgestufete Funktionalität. Register/Register Arithmetik können alle 32, Register/Konstante Arithmetik können nur 16 davon, die geringe Menge an 16bit Registerpaar Arithmetik können nur 8 davon (als 4 Paare), Speicher adressieren können nur 6 davon (als 3 Adressen), Speicher indiziert adressieren können nur 4 davon (als 2 Addresen+6bitOffset), den Programspeicher adressieren können nur 2 davon (als 1 Programadresse). Das ergibt bei der Registerwahl für die Übergabekonvention eine "gerade noch genug gut für die Aufgabe" Methodik.

Ein Vorteil ist, dass es mit den 3 Registerpaaren X,Y,Z, sowie dem SP für vier Adressen Platz hat. Dazu kommt, dass alle davon mit automatischem +1 nach Lesezugriff und -1 vor Schreibzugriff arbeiten können, wie es Stacks brauchen, also kein Problem ist mit den 2 Stacks schnell machen. Mit dem vielen Platz erlaubt es auch problemlos einen TOS Cache zu haben, und daneben ohne Herumschiebereien viele temporäre Daten.

Leicht aufwendiger ist, dass Speicherzugriffe nur separat von der Arithmetik möglich sind, also mit 2 Befehlen und mehr Ausführungszeit, was ein weiterer Grund für einen TOS Cache ergibt, zum die Datenstack Speicherzugriffe reduzieren. Auch gibt es fast nur 8bit Befehle, und damit fast immer 2 Befehle pro Operation (bzw 2+2=4 Befehle bei Speicherzugriff+Arithmetik), also gibt es relativ lange Routinen. Ein direct compiled braucht hier daher recht viel Platz, mangels 16bit Befehlen und mangels kombinierten Speicherzugriffen und Arithmetik, es ist also davon abzuraten.

Alle Befehle ausser 4 sind nur 1Wort/2Byte gross. Lediglich die langen CALL/JMP mit weiter als +/-2kWort/4kByte Distanz, sowie LDS/STS mit konstanter Adresse sind alle 2Wort/4Byte. Als Folge von diesem ist subroutine threading auch zumeist mit den kurzen RCALL/RJMP in nur 1Wort/2Byte machbar, und damit gleich kompakt wie direct oder indirect threading, aber schneller, und ist damit zu empfehlen. Allerdings kosten die RCALL/CALL + RET auch 3/4 + 4 Speicherzugriffe an Zeit, oft mehr als die Rechnung (die etwa 4..10 Speichergriffe Zeit brauchen). Also etwa 2 mal Zeit für etwa 1/4 mal Platz, das ist akzeptabel, zumal man für schnellstmöglich auch Primitives schrieben kann.

Folglich wird SP den Returnstack abgeben und einer von X,Y,Z den Datenstack. Das indizierte adressieren kann Zugriffe auf Stackelemente unterhalb der beiden oberen beschleunigen, also Y oder Z dafür nehmen. Programmspeicher Zugriff (auch lesend) ist heikel, also nicht das Z dafür blockieren, also Y als Datenstack nehmen. Der TOS Cache sollte Speicher lesen können, z.B. in @, also X dafür nehmen. Temp passt am besten in Z, das alles kann. Falls mehr gebraucht wird ist R24:R25 (das vierte 16bit Paar) die erste Anlaufstelle.

Der AVR subroutine threading Code wäre dann:

Einmalig, die Primitives:
(Dies wird in der Dictionary gespeichert)
+
Add:
LD ZL,Y+: LD ZH,Y+
ADD XL,ZL; ADC XH,ZH
(Kein DAD-artiges 16bit. Immer 2 Register, XL und YH als erster Operand und Ziel der Rechnung, ZL und ZH sind zweiter Operand)
RET
-
Sub:
LD ZL,Y+: LD ZH,Y+
SUB ZL,XL; SBC ZH,XH
MOVW XH:XL,ZH:ZL
(beide SUB/SBC nach dem laden, weil keine Limite mit nur ein A Register, ZH:ZL entsprechen direkt DE holen, und dort rechnen. In ZH:ZL rechnen und danach MOVW (einer der wenigen 16bit Befehle), weil die Subtraktion nicht kummutativ ist)
RET
AND (und analog OR und XOR)
Ist wie +, nur die ADD/ADC durch 2 mal AND ersetzen, und ist wieder auch kommutativ
DUP
Dup:
ST -Y,XH; ST -Y,XL
RET
DROP
Drop:
LD XL,Y+: LD XH,Y+
RET
SWAP
Swap:
LD ZL,Y+: LD ZH,Y+
ST -Y,XH; ST -Y,XL
MOVW XH:XL,ZH:ZL
RET
!
Store:
LD ZL,Y+: LD ZH,Y+
ST X+,ZL; ST X,ZH
LD XL,Y+: LD XH,Y+
RET
@
Fetch:
LD ZL,X+; LD ZH,X
MOVW XH:XL,ZH:ZL
RET
Zahlwerte (egal für welchen Wert)
Literal:
ST -Y,XH; ST -Y,XL
(Das ist noch der normale PUSH, wie bei DUP)
(Oben auf dem Returnstack ist die Adresse unseres Zahlenwertes, also können wir jetzt die Adresse und den Zahlenwert holen)
POP ZH; POP ZL
(Keine 16bit PUSH/POP Befehle, also in 2 Hälften, und dazu noch beim AVR verkehrt, den High Teil zuletzt/zuoberst auf dem Prozessorstack gelegt, dann erst zuerst/darunter Low)
LD XL,Z+; LD XH,Z+
IJMP
(Weil LD direkt ins XH:XL TOS Cache ging, und das nicht das ZH:ZL Temp ist, kann man mit IJMP (das kann nur ZH:ZL benutzen) direkt PCHL-mässig springen, statt mit PUSH; PUSH; RET>)
>R
Push:
POP ZH; POP ZL
PUSH XL; PUSH XH
(Auch die Daten auf den Returnstack "verkehrt" hinlegen, damit sie als Adressen nutzbar bleiben, z.B. zum EXECUTE mit einem >R implementieren)
LD XL,Y+: LD XH,Y+
(Damit wird die Returnadresse gesichert in ZH:ZL, dann TOS abgespeichert und neu geladen, und zum Schluss die Returnadresse direkt angesprungen, statt PUSH ZL; PUSH ZH; RET)
IJMP
R>
Pop:
POP ZH; POP ZL
ST -Y,XH; ST -Y,XL
POP XH; POP XL
IJMP
OVER
Kann man in Forth als >R DUP R> SWAP definieren, was für diese seltener benutzten und mit 3 Stackelementen arbeitend ohnehin langsameren Befehlen zum Teil ausreicht.
Oder man kann in Assembler die Sequenzen zusammenlegen (ohne die POP ZH; POP ZL; IJMP weil alles in einem), und dann diese durch weiter Befehle weglassen optimieren:
Over:
*** ab hier >R (statt PUSH Daten im Prozessor behaltend)
MOVW ZH:ZL,XH:XL
LD XL,Y+: LD XH,Y+
*** ab hier DUP (SBIW entspricht 2 mal DEX B)
SBIW YH:YL,2
*** ab hier R> (TOS bereits da, und kein POP nötig)
*** ab hier SWAP (laden entfät, nur speichern)
ST -Y,ZH; ST -Y,ZL
RET
Oder man nutzt das indizierte Adressieren des Speichers aus:
Over:
ST -Y,XH; ST -Y,XL
(Das ist der DUP, ohne ein >R davor)
LD XL,Y+2: LD XH,Y+3
(Und dann das darunterliegende (= dritte) Element holen und das erste damit überschreiben, daher ist auch kein >R oder R> nötig)
RET
ROT
Kann man in Forth als >R SWAP R> SWAP definieren. Und wie oben Assembler Sequenzen zusammenlegen und optimieren
EXIT (sofern vorhanden, nicht einfach RET)
Exit:
POP ZH; POP ZL
(Der AVR hat kein Gegenstück zu INX SP)
RET
Routine Branch, (sofern vorhanden, nicht einfach JMP oder gar RJMP)
Branch:
(Dies ist analog zu Literal, nur mit Daten vom Program in den PC statt auf den Datenstack)
POP ZH; POP ZL
(Wie bei Literal die Rücksprungdresse vom CALL Branch holen, die auf die Branch Adresse zeigt)
LD R24,Z+; LD R25,Z+; MOVW R25:R24,ZH:ZL
(Ein LD ,Z+ kann nicht direkt in ZH:ZL lesen, also R25:R24 Umweg)
IJMP
(Und direkt mit JMP Z springen, statt PUSH; PUSH; RET. Das ist genug Aufwand, dass man auf alles CALLs verzichten will und Branch mit JMP oder RJMPmachen. Dann wird auch EXIT zu RET, und man ist auch offen für tail call Optimierung)
Routine Zbranch
Zbranch:
(Dies ist analog zu Branch, aber nur Sprung wenn TOS=0)
POP ZH; POP ZL
OR XH,XL
(Bei beiden TOS Bytes = 0 ist nun XH = 0 und Zero Flag = 1)
BRNZ Zb-Nojmp
  ("if", Sprung wie in Branch gehabt)
  LD R24,Z+; LD R25,Z+; MOVW R25:R24,ZH:ZL
JMP Zb-Done
Zb-Nojmp:
  ("else", kein Sprung, nur Adresse übergeh)
  ADIW ZH:ZL,2
Zb-Done:
LD XL,Y+: LD XH,Y+
(TOS nachladen, wie bei DROP)
IJMP

Wiederholt, in den Secodaries:
(Dies wird für jedes Wort wieder compiliert)
+
(R)CALL Add
(Das ergibt 6 Speicherzugriffe eigentliche Addition, sowie weitere CALL Add 3 und RET 4, gibt damit 13, im Gegensatz zum 8080 seinen 9+8=17)
Alle - AND DUP DROP SWAP ! @ sowie >R R> OVER ROT
Sind indentisch (R)CALL Sub And Dup Drop Swap Store Fetch sowie Push Pop Over Rot
23 (und alle anderen Zahlwerte analog)
(R)CALL Literal
.DW 23
EXIT
(R)CALL Exit
(oder gleich RET verwenden)
Routine Branch, Aufruf mit Adresse 42
(R)CALL Branch
.DW 42
(oder gleich JMP 42 verwenden)
Routine Zbranch, Aufruf mit Adresse 42
(R)CALL Zbranch
.DW 42

Bisher alles ein recht geradeaus benutzbarer Rechner, wenn auch leicht umständlich. Es gibt hier aber ein sehr grosses Problem: Der AVR hat eine Harward Architektur, wie viele andere Mikrocontroller es auch haben (z.B. die 8048/8051 und die Z8 und die PIC, nicht aber die von Neumann Architektur 6805/6811/6812 oder die MSP430 oder die ARM). Auf den ersten Blick ist das sogar von Vorteil: Es ist einfacher und billiger. Es kann mit 2 separaten Speichern den nächsten Code holen während der letzte Befehl am rechnen ist, was schneller ist. Dabei gibt es erst noch 16bit Befehl aufs mal, weil der Befehlsspeicher 16bit breit sein kann, weil unabhängig vom 8bit Datenspeicher, und damit hat es 16bit + 8bit an Durchsatz. Dementsprechend sind etwa 80% aller Befehle nur 1 Speicherzugriff lang. Auch die für 2 mal 8bit rechnen nötigen 2 Befehle bremsen dabei nicht, weil während den 2 mal 8bit rechnen auch 2 geholt werden können, sie brauchen also nur mehr Platz, nicht mehr Zeit. Daher benutzen auch so viele Mikrocontroller eine Harward Architektur, weil billig und schnell.

Nur wirft das ganze bei Forth ein riesiges Problem auf: Der Programspeicher ist ausschliesslich Flash, und kein SRAM. SRAM (und etwas EEPROM) hat es nur im Datenspeicher, aber Programcode kann nicht vom Datenspeicher aufgeführt werden. Daten (aber nur Konstanten) können vom Programspeicher gelesen werden, das geht aber auch nur mit einem anderen Befehl als vom Datenspeicher lesen (LPM statt LD), mit separaten Adressen (beide Speicher haben eine eigene Adresse 0, die verschieden ist), und sind dort auch nicht veränderbar (also keine Variablen).

Das macht das Forth Dictionary auf allen harward Architekturen schwierig zu implementieren, und das ist neben den beiden Stacks die zentrale Datenstruktur! Der Code muss ins Flash, die Dictionary Header damit auch, CONSTANT seine Konstanten können es auch. Aber VARIABLE seine Variablen müssen ins SRAM, und müssen daher alle wie bei USER implementiert werden. Das gilt aber diesmal für alle Variablen, auch für Variablenarrays, darf aber wiederum nicht für Konstantentabellen gelten. CREATE, bzw sein Docreate, wird damit nicht mehr für Variablen oder Variablenarrays benutzbar.

Noch schwieriger wird es aber wenn der Benutzer neuen Code compilieren will (oder Variablen oder Konstanten anlegen will). Wohin damit? Man kann bei Harward nicht in den Programspeicher schreiben, und damit auch nicht ins Flash, und SRAM scheidet spätestens bei Code aus, also wird : nicht mehr implementierbar. Das ist auch der Grund, warum alle universellen Rechner wie PCs von Neuman sind, trotz mehr Aufwand und langsamer, weil man compilierten Code von Disk Files in den Speicher laden und ausführen will, was auch das selbige Problem hätte. Jetzt steht noch mehr Flickerei an als bei USER:

Motorola 6809

Nach den ganzen obigen AVR Harward Problemen, kommt nun der 6809 an die Reihe. Dieser ist schlicht der Forth Traumprozessor, denn er hat genau die richtigen Register und die fast optimalen Befehle dafür.

Bisher habe ich in dieser Serie die Intel Welt gebracht. Parallel dazu gab es in den 1970ern noch eine zweite grosse Welt, die Motorola 6800/6802 und 6809, sowie den davon abstammenden MOS Technology 6502. Für mich war der 6809 der zweite Prozessor (nach der Z80), vor der 6502/6510 als dritten, den 8080/8085 als vierten, dem 8051 als fünften und dem 68000 als sechsten, und 15 Jahre danach den AVR als siebten (die 8086/8088/286/386+) habe ich nie in Assembler programmiert). Diese Motorola Welt werde ich hier jetzt etwas nachholen.

Die 6800/6802 sind zeitlich (ab 1974) und umfangsmässig (8bit mit vollen 16bit Adressen) deren Parallelen zu den 8080/8085, beide in NMOS (statt dem PMOS der 8008), und sogar mit dem gleichen Schritt von 12V (aber die 6800 mit eingebautem Spannungswandler so dass nur 5V gebraucht werden) zu echter 5V Technologie dazwischen, mit ansonsten wenigen Änderungen. Ein 8008 Gegenstück hat es hier keines, Intel war damals alleine. Die 6502 ist wie die Z80 das Werk einer Gruppe von mit der Entwicklung unzufriedener Mitarbeiter die weggingen und eine eigene Firma gründeten, auch in 1976. Die 6809 ist parallel zu den 8086/8088, ein gemischter 8bit/16bit Prozessor, und wie diese zum Vorgäger nur Assembler Sourcekompatibel, nicht aber Befehlscodekompatibel, wenn auch weit näher liegend (nur mehr Register und Befehle, kein Wechsel zu Zweiadressrechner). Leider fehlt dem 6809 die Adresserweiterung der 8086/8088 auf 20bit zum sich von reinen 8bit Prozessoren distanzieren, und er hat den erfolgreichen 68000 als grossen 16bit/32bit Bruder, statt dem gescheiterten 80432 32bit, wesshalb er nie wirklich gross verbreitet wurde, ausser in Steuerungen. Dafür ist der 6809 einer der komfortabelsten 8bit/16bit Prozessoren überhaupt. (Apple wollte anfangs den 6809 für den Macintosh, nahm aber den 68000 wegen dessen 24bit Adressen)

Auch bei den Mikrocontrollern lief es parallel, aber leicht anderst. Intel hat dort auf der Basis seiner 4bit Harward Architektur 4004 den 8bit 8048 gemacht, und später den 8051, beide auch Harward, und mit ihrer berüchtigten 256Byte SRAM Limite (wenigstens hat die AVR das nicht). Motorola dagegen hat, mangels 4004 oder 8008 Gegenstück, seine von Neuman 6802 genommen und die 6805 und 6808 gemacht, und später auf 6809 Basis die 6811 und 6812, alle von Neumann, mit 64k Speicherplatz, wobei der 6811 eine reduzierte 6809 CPU ist (ohne U Register) und 6812 die nach Reklamationen nachgeschobene Vollausgabe (mit U Register). Damit sind diese auch optimal für Forth geeignet.

Die 6809 ist also eine 8bit CPU, mit einigen 16bit Befehlen. Sie hat an Registern 2 8bit Akkumulatoren (A und B), mit allen Befehlen in 8bit. Diese können zu einem 16bit Akkumulator D zusammengesetzt werden, mit 16bit Addition (wie DAD) und Subtraktion, und das ohne 8bit in A und 16bit in HL zu verstreuen, ohne Kopiererei. In Forth ist D damit ein idealer TOS Cache. (Die 6800/6802 haben A und B, aber keine Nutzung als D.)

Die 6809 hat 2 Stackpointer (S und U), von denen S für Unterprogramme benutzt wird, und U rein für Daten mit PUSH/POP ist. Logisch macht man Forth mit S als Returnstack und U als Datenstack. (Die 6800/6802 haben nur S. Die 6811 ebenfalls. Gerade die Forth Leute haben sich da sehr über den vermissten zweiten Stack beschwert, und somit die 6812 erwirkt.)

Die Register BC und DE und HL fehlen hier, dafür kann die ganze Arithmetik direkt mit Daten vom Speicher ablaufen, ohne zuerst in Register zu laden, und das erst noch mit vollen 16bit Adressen (und 3Byte Befehlen), oder mit kurzen 8bit Adressen (und 2Byte Befehlen) die oben mit den 8bit vom Hilfsregister DP (= Direct Page) erweitert werden (das gibt 256 Blöcke zu je 256Bytes). DP+8bit ist in Forth ideal für die USER Variablen. (Die 6800/6802 haben das auch, aber statt DP fest 0, also nur 1 Block von 256 Bytes, an Adressen 0..255, was dann die Zero Page genannt wird.)

Indirekte Adressen (wie für Speicher[HL]) wären damit aber sehr langsam, mit 1Byte Befehl plus 1Byte Adresse plus 2Byte indirekte Adresse lesen plus 1Byte Datentransfer (= 5 Speicherzugriffe). Also hat es noch 2 reine 16bit Adressregister (X und Y). Diese beiden (und auch S und U) können alle 4 als indirekte Adressregister arbeiten, mit vielen Varianten (das R bedeutet X oder Y oder S oder U):

Das alle das können sie erst noch kombiniert mit Arithmetik machen, und das erst noch zusammen mit D in 16bit!. Das spart enorm Code und Speicherzugriffe dafür. Ebenso können alle 4 mit dem Ergebnis einer beliebigen Adressregister+Offset Rechnung geladen werden, sehr orthogonal. (Die 6800/6802 haben nur X, und indirekte Adressierung geht nur mit X (nicht mit S), und keine automatische Ver&aum;nderung (nur INX/DEX Befehle), und nur indiziert (X+8bitOffset). X kann Addition (nur +B mit ABX oder +1 mit INX) aber keine Subtraktion (ausser -1 mit DEX).)

Leider gilt wegen Befehlscode Mangels (nur 256 Codes in 8bit Befehlen) die Orthogonalität nur im Assembler. Im Maschinencode sind aber manche identisch aussehende Befehle um ein 1Byte und 1Speicherzugriff grösser bzw langsamer. Y laden/speichern ist daher langsamer als X, ebenso S laden/speichern langsamer als U, aber Y und S als Adressen benutzen (und dabei verändern) ist wieder gleich schnell wie X und U. Das beeinflusst die Registerwahl. Ein weiteres Zeitproblem ist, dass die 6809 (und auch die 6800/6802) bei 16bit Daten/Adressen zuerst die oberen 8bit bewegt und rechnet, und dann erst die unteren 8bit, was nach den unteren 8bit bewegen und rechnen noch einen dritten Speicherzugriff an Zeit für eine interne "Korrekturrunde" braucht für die bereits berechneten oberen 8bit korrigieren. Das ist als Totzyklus bekannt.

Daher nimmt man also für Forth Register D als TOS Cache, S als Returnstack, U als Datenstack, X als IP (falls man direct oder indirect threading macht), Y als W (falls man indirect macht), DP als USER Basis. Es hat genau für alles die passenden Register, trotz dass mit A+B+X+Y+U+S+DP+PC=13Bytes nur unwesentlich mehr als mit dem 8080 seinen A+BC+DE+HL+SP+PC=11Bytes an Registern vorhanden sind. Daher ist die 6809 auch der Forth Traumprozessor.

Der 6809 direct compiled Code mit TOS Cache wäre dann:

+
ADDD ,U++
(Ja, das ist alles, ein Befehl, weil 16bit mit D (= TOS) als Ziel, und ,U (= Datenstack im Speicher addressiert mit U ohne indiziert), und ++ (= autmatisch U + 2 danach). Das alles passt in 2Byte, und damit identisch gross wie eine 2Byte Adresse, und mit ganzen 4 Speicherzugriffen, kürzer als einem CALL seine 3Bytes und 5 Zugriffe. Das im Gegensatz zum 8080 direct compiling 9 bzw subroutine threading 9+8=17 sowie AVR subroutine threading 6+7=13 Zugriffen. Es ergibt 2 bzw 4 sowie 3 mal schneller. Datenzugriffe sind in allen vieren identische 2, Codezugriffe sind hier aber 2 und andere 7 bzw 7+8=15 sowie 4+7=11. Das ist der Prozessorunterschied Effizienz in Anteil Nutzdatenzugriffe zu Gesammtzugriffe)
-
SUBD ,U++
(16bit Subtraktion auch, 2Byte)
AND (und analog OR und XOR)
ANDA ,U+; ANDB ,U+
(Das weicht jetzt ab, weil AND nur in 8bit existiert. Braucht aber auch nur 2+2=4Bytes, leicht mehr als ein CALL)
DUP
PSHU D
(Ein PUSH heisst hier PSH, ein POP heist PUL, beide mit jeweils S oder U dahinter, je nach welchem Stack sie benutzen. Ein LDD ,U++ geht hier auch, nur ist es langsamer, trotz gleichviel Speicherzugriffe, weil ,U++ gegenüber ,U 3 Totzyklen an Zeit zum intern U++ rechnen braucht, währed PSH/PUL dafür nur 2 Totzyklen brauchen)
DROP
PULU D
SWAP
LDX ,U; STD ,U; TFR X,D
(Es hat hier kein XTHL Gegenstück (und nur ein langsames XCHG), also muss man "im Dreieck kopieren", das braucht 3 Befehle, 2+2+2=6Bytes)
!
TFR D,X; PULU D; STD ,X; PULU D
(D ist TOS, kann aber nicht Adressregister, daher hier 4 Befehle, mit 2+2+2+2=8 Bytes, hier lohnt am ehesten ein Unterprogramm)
@
TFR D,X; LDD ,X
23 (und alle anderen Zahlwerte analog)
PSHU D; LDD #23
(2 Befehle, 2+3=5 Bytes, CALL mit Zahlwert ist auch 5, und so sind die ganzen PC von/zu Stack Sachen weg)
>R
PSHS D; PULU D
R>
PSHU D; PULS D
OVER
PSHU D; LDD 2,U
(Hier wieder wie beim zweiten AVR, mit Indiziert (das 2,U))
ROT
Kann man in Forth als >R SWAP R> SWAP definieren
EXIT
RET
(1 Befehl mit 1 Byte, ist absolut kompaktestes)
Routine Branch
JMP 42
(1 Befehl mit 3 Bytes. Wobei man bei +/-128Bytes mit BRA 42 nur 2 Bytes braucht)
Routine Zbranch
ADDD #0
(Bei TOS = 0 ist D nun immer noch 0 und Zero Flag = 1)
PULU D
(TOS nachladen, wie bei DROP)
LBEQ 42
(Bei "EQ" (= Equal = Zero Flag ist 1, Ergebnis Addition mit 0 ist gleich 0 gewesen) springen, mit LBEQ Langdistanz beliebig, oder mit BEQ Kurzdistanz +/-128Bytes. Das gibt 3 Befehle mit 3+2+2oder4=7oder9 Bytes)

Wie an sieht kann direct compiled auf dem 6809 sehr kompakt sein. Die + - DUP DROP sind nur 2Bytes, und die AND @ >R R> OVER sind passable 4Bytes. Der 23 Zahlwert kommt in 5 Bytes. Und EXIT Branch passen sogar in kurzen 1 bzw 2oder3 Bytes. Nur die SWAP 6Bytes und ! 8Bytes, sowie Zbranch 7oder9Bytes schlagen oben hinaus. Damit wird jegliches threading unnötig, und direct compiled ergibt ein sehr schnelles Forth.

Will man sogar noch mehr, kann man auch Zahlwert gefolgt von Operation zusammenziehen. Aus 23 + wird damit statt PSHU D; LDD #23; ADDD ,U++ dann ein direktes ADDD #23, mit 3Byte statt 2+3+2=7Bytes Code, und neben 4 Speicherzugriffe Code auch noch 2+2=4 Speicherzugriffe Datenstack einsparend. So etwas nennt man bei einem Compiler der es automatisch macht eine peephole Optimierung. Gerade orthogonale Befehlssätze (alles mit 16bit, alles mit Stack oder Konstante) und einfache Befehlsfolgen (nur einen Befehl zum ersetzen/umbauen), wie beim 6809 der Fall, machen diese Technik erheblich einfacher, und damit direct compiling noch attraktiver.

Dagegen bringt subroutine threading fast gar nichts, ein CALL (der hier JSR heisst) braucht immer 3 Bytes (bzw bei 23 Branch Zbranch mit dem Zahlwert oder der Adresse sogar 5 Bytes), statt obigen 2..8 Bytes, also wenig Einsparung und teils sogar mehr Verbrauch. Anderseits ist ein JSR auch 5 Speicherzugriffe und der RET (der hier RTS heisst) will nochmals 3. Das sind 8 Zugriffe auf die obigen 4..14 drauf, etwa +100% Zeit für etwa -25% Code. Also wird man das nur machen, wenn man gnadenlos Platz sparen muss. Dann wird man aber gleich ein direct oder indirect threading nehmen, weil das nur 2/3 vom Platz von subroutine threading braucht. Also nimmt man JSR nur in einem "zumeist direct" System, zum die übelsten Fälle kürzen, wie bei SWAP ! Zbranch.

Ein direct threading spart doch etwas mehr Platz, etwa um 60%, kann sich also lohnen. Das zumal es auf dem 6809 auch nicht gerade langsam ist, und sogar schneller als subroutine threading ist. Siehe dazu den Gebrauch davon in der 6809 Ausgabe von CamelForth. Dies ist so, weil IP (in Register X) und PC parallel existieren, und damit bei Primitives in direct threading kein IP abspeichern und wieder laden ist, im Gegensatz zu subroutine threading mit PC abspeichern und wieder laden. Das erspart pro Primitive 2+2=4 Speicherzugriffe. Das ist eigentlich ein Spezialfall von leafcall Optimierung. Das kompensiert für den Next Aufwand, der hier auch sehr gering ist (nur 1 2Byte Befehl JMP ,X++, und daher auch ohne JMP Next an jedes Primitive angehängt wird), zumal den JSR Befehlscode vom Secondary lesen auch noch wegfällt. Insgesammt ist beim Schritt von einem Primitive "1" zum nächsten Primitive "2" bei subroutine threading das RTS von "1" und das JST "2" vom Secondary nötig, was (1+2)+(3+2)=8 Speicherzugriffe ausmacht, während bei direct threading das Next nur (2+2)=4 Speicherzugriffe braucht. Damit ist direct threading nur 50% langsamer als direct compiled, im Gegensatz zu den 100% langsamer des subroutine threading! Und alle drei sind schnell.

Der 6809 direct threading Code wäre dann (nur teilweise, zum den Resten nicht wiederholen):

Routine Next (eigentlich JMP Speicher[X++] machen)
Next:
JMP ,X++
(Weil ,X++ 3 Totzyklen hat, gibt es noch eine ganz ausgefuchste Forth Variante, mit S als IP und X als Returnstack, mit Next sein JMP ,S++ durch RTS ersetzt, welches damit die Secondaries als "Codestacks" anschaut, die nach und nach "abgebaut" werden)
Routine Docol (CALL, eigentlich Speicher[--S]=X und X=neu)
Docol:
PULS Y
(Die Adresse vom JSR Docol zurückholen, der JMP Trick ist hier unmöglich, weil kein HL vom PCHL her herumliegt)
PSHS X; TFR Y,X; [Next Kopie statt JMP Next]
Am Anfang jedes Secondary
JSR Docol
(Dann gefolgt von einer Adressliste:)
.DW Adresse1
.DW Adresse2
.DW ...
Routine Exit (Return, eigentlich X=Speicher[S++] machen
Exit:
PULS X; [Next Kopie statt JMP Next]
Am Ende jedes Secondary
.DW Exit
Der Rest, die eigentlichen Primitives, als Beispiel +
Add:
ADDD ,U++; [Next Kopie statt JMP Next]

Auch indirect threading ist immer noch recht schnell. Next ist dabei bloss 2 Befehle (LDY ,X++; JMP ,Y++), und damit immer noch ohne JMP Next machbar. Secondaries haben aber keinen JSR Docol Befehlscode mehr am Anfang zum holen, und Docol selber kann sein PULS Y einsparen. Dafür ist Next doch etwas länger und alle Primitives haben ihre eigene Adresse am Anfang zum holen. Es ist also langsamer, aber nicht wirklich viel.

Man sieht hier schön, dass 8080 und AVR mit subroutine optimal laufen, der 6809 damit aber absolut gar nicht, dafür aber mit direct compiled, wo 8080 und AVR gross werden, oder mit direct threading wo 8080 und AVR mehr oder weniger absaufen. So stark unterscheiden sich einzelne Prozessoren und ihre Befehlssätze wenn es um Code generieren geht.

DEC PDP-11

Nach der 6809 nehme ich hier nun die PDP-11 an die Reihe, die noch leicht optimaler ist. Sie kann alles in 16bit Rechnen (und zumeist auch in 8bit). Sie kann 16bit in einem Speicherzugriff transferieren (= nochmals doppelt so schnell, selbst bei gleicher Effizienz). Sie kann wie die 6809 kombinierte Speicher und Arithmetik in einem Befehl, und ist damit gleich effizient. Dazu ist sie noch dank 16bit Wort Befehlscodes wie der AVR ein Zweiadressrechner. Und damit ohne die 6809 Unterscheidung von einerseits Akkumulator D und anderseits Adressregister X,Y,U,S sowie S und Y langsamer. Wie beim AVR sind fast alle Befehle nur 1Wort/2Byte. Lediglich alle JSR (der CALL heisst auch hier so) und die JMP mit weiter als +/-256Wort/512Byte Distanz sind 2Wort/4Byte, ebenso sind alle Befehle mit 1 oder 2(!) konstanter/n Adresse(n) oder Index Offset(s) darin 2Wort/4Byte bzw sogar 3Wort/6Byte, ebenso sind alle Befehle mit einer Datenkonstante 2Wort/4Byte (bzw Datenkonstante und Adresse oder Index Offset 3Wort/6Byte).

Die PDP-11 ist also eine 16bit CPU, mit einigen (aber nicht allen) Befehlen in 8bit Modus. Sie hat 8 16bit Register R0..R7, von denen aber R7 der PC ist und R6 der SP sind, sowie die restlichen R0..R5 6 Allzweckregister (und damit genau gleich viel wie 6809 seine D + X,Y,U,S + DP), von denen aber jeder sowohl Akkumulator wie auch Adressregister wie auch Stackpointer sein kann! Als Adressregister gibt es mit allen von ihnen mit:

Die PDP-11 gilt damit als eines der schönsten und orthogonalsten Befehlssätze überhaupt. Die Ausnahmen sind, dass Addition und Subtraktion kein 8bit können, und XOR kein vollständiges Zweiadress kann, beides weil die Befehlscodes ausgingen. (Da der Vorgänger PDP-8 weder Subtraktion noch XOR hatte, und die PDP-11 viele Befehlscodes mit Vergleichen und Bit Tests verbraucht, nehm ich an, dass diese beiden erst nachträglich addiert wurden, und man dabei die Vergleich und Bit Tests nicht mehr opfern wollte. Auch mit sowas muss man in Assembler und beim Compiler schreiben umgehen können.)

Strike ist die PDP-11 ein Minicomputer von 1970 (und damit älter als der Intel 4004!) und damit auch kein Mikroprozessor, aber es gab DEC-eigene LSI-11 sowie später F11 (Fonz-11) und J11 (Jaws-11) Mikroprozessor Varianten davon, und das VCFe ist ohnehin nicht auf Mikroprozessor Rechner beschränkt. Nur haben die wenigsten hier Zugriff auf eine PDP-11, ausser mit Emulatoren. Anderseits war diese auch die Inspiration/Vorbild der 6809, und erst recht der 68000 (welche in Macintosh und Atari ST und Amiga drin ist, und dort recht ähnliche Forth Implementationen erlaubt, wenn auch diese 8+8 Register hat, die einten 8 mit aller Arithmetik, die anderen 8 als Adressen). (Die ersten Ausgaben von Unix wurden auf einer PDP-11/20 und PDP-11/40 geschrieben, viele frühe Unix Workstations waren daher auch mit 68000ern laufend.)

Für Forth benutzen ist sinnvoll: R0 als TOS Cache, R1 für temporäres, R2 als W (falls gebraucht), R3 als IP (falls gebraucht), R4 als USER Basis, R5 als Datenstack, R6 offensichtlich als Returnstack. Wieder genau passende Register, wie bei der 6809.

Der PDP-11 direct compiled Code mit TOS Cache wäre dann (nur teilweise, das was bedeutend von 6809 abweicht):

+
ADD (R5)+,R0
(Zwei Register, beide als Parameter, und R0 als ersten Operand und Ziel als den zweiten Operand im Befehl! - ist analog)
AND (und eben nicht analog OR und XOR)
MOV (R5)+,R1: COM R1; BIC R1,R0
(Alle Logik AND/OR/XOR sind hier als 16bit vorhanden, es ist kein 2 mal 8bit nötig. Aber AND ist wegen Designfehler nur als BItClear (BIC) Befehl vorhanden, mit invertiertem zweiten Operanden, wesshalb man separat laden und mit COMplement (COM) vor-korrigieren muss. OR ist normal wie Addition und Subtraktion, lediglich mit BItSet (BIS) komisch benamst. XOR ist wegen Mangel an Befehlscode Platz nicht orthogonal, mit als zweiten Operanden nur ein Register, kein Speicherzugriff, also braucht es 2 Befehle MOV (R5)+,R1; XOR R1,R0)
DUP
MOV R0,-(R5)
(alle LD und ST sind hier MOV, auch die mit dem Speicher)
SWAP
MOV (R5)+,R1; MOV R0,-(R5); MOV R1,R0
(Es hat hier auch kein XTHL Gegenstück, also muss man hier wieder "im Dreieck kopieren", auch 3 Befehle)
!
MOV (R5)+,(R0); MOV (R5)+,R0
(R0 kann auch ein Adressregister sein (im Gegensatz zum 6809 D in X umkopieren müssen), und dank Zweiadressrechner kann man auch eine Direktkopie von Stack zu Speicher in einem befehl machen, ohne via D zu gehen, und damit 2 Befehle benötigen)
@
MOV (R0),R0
(Wieder ohne D in X umkopieren)
>R
MOV R0,-(R6); MOV (R5)+,R0
(Hier und bei R> keine Direktkopie Stack zu Stack, weil wieder der TOS Cache im Weg ist)
Routine Branch
JMP 42
(2Wort/4Byte, ausser bei Kurzdistanz +/-128Worte/256Bytes das mit BRA 42 nur 1Wort/2Byte braucht)
Routine Zbranch
MOV R0,R1
MOV (R5)+,R0
(TOS nachladen, wie bei DROP)
CMP #0,R1
(Ein MOV killt aber die Flags, also musste man zuvor in R1 kopieren und jetzt R1 testen. Bei TOS = 0 ist nun Zero Flag = 1)
BEQ 42
(BEQ ist "Sprung wenn Test gleich war". Das reicht wenn innerhalb Kurzdistanz +/-128Worte/256Bytes, sonst muss man mit BNE als "Weiter wenn Test auf ungleich" einen JMP 42 Sprung überspringen/vermeiden)

Ein direct compiled ist hier also noch kompakter als beim 6809, und damit schlicht das schnellste. Neben den 6809 + - DUP DROP sind hier auch OR @ sowie EXIT und teils Branch nur 1Wort/2Byte Befehle. AND ist auf 3Wort/6Byte hinauf, aber XOR >R R> sowie Branch sind 2 Wort/4Byte, und ebenso neu ! statt den 8Bytes. Das SWAP ist wieder 3Wort/6Byte gebleiben, 23 OVER auch auf 3Wort/6Byte hinauf. Nur Zbranch ist mit 5oder6Wort/10oder12Byte wirklich gross.

Es ist zumeist auch das kompakteste, zumal ein JSR für subroutine threading hier wegen den 16bit Befehlscodes 2Wort/4Bytes gross ist, und 3 Speicherzugriffe. Und das ist grösser bei einigen der obigen, gleich bei noch mehr, und nur wenig weniger bei dem Grossteil vom Resten (weil bei 23 auch JSR und Daten mit zusammen 3Wort/6Byte wäre). Nur Zbranch wäre 2/5 oder gar 3/6 weniger. Das ist also mehr als 100% langsamer, und das ohne die 25% kleiner. Also geht man wieder wenn schon auf direct/indirect threading los.

Aber auch mit direct/indirect threading ist nicht mehr viel Platz zum sparen, etwa 50% statt 60%. Und das wäre hier genau analog zum 6809, auch ohne JMP Next (mit IP=R3 ist Next nur ein 1Wort/2Byte JMP (R3+)). Das ist nur noch deutlicher kompakter und schneller als beim sehr ineffizienten subroutine threading, aber langsamer als direct compiling. Weitere Implementationen erübrigen sich daher hier fast schon.

MOS Technology 6502

Nach 6809 und PDP-11 kommt nun die 6502 von MOS Technology. Im Gegenteil zu diesen beiden ist sie sehr schlecht zu Forth passend, noch schlechter als die 8080, nur eine 8008 wäre noch schlimmer. Bisher habe ich diesen Prozessor wenig beachtet, trotz dass sie neben der Z80 am VCFe am weitesten verbreitet ist (Apple 1 und 2, Atari 400/800/800XL/1300XL, Commodore PET/VC-20/C64/C128), weil sie für mich nach den Z80 und 6809 erst der dritte Prozessor war, und nach beiden von diesen nicht mehr wirklich beeindruckend war, so primitiv wie sie ist.

Entwickelt wurde sie als 3500 Transistor Billigprozessor in 1975 (die 4bit 4004 hatte in 1971 deren 2300, die 8bit 8008 in 1972 schon 3500, die 8080 in 1974 sogar 5500, die simplere 6800 in 1974 immerhin noch 4100). Dementsprechend kostete sie in 1975 nur $25, als die 8080 und 6800 noch $150 bzw $175 kosteten (und nach der 6502 Einführung über Nacht auf $75 reduziert wurden, auf 3 mal statt 6 bzw 7 mal). Derart billig erlaubte sie einen sehr niedrigen Einstiegspreis/Basispreis, der dann aber nach oben mit mehr/teureren Speicherverbrauch bezahlt werden musste, sowie mit geringer Nutzdatenzugriff zu Codezugriff Effizienz. Dies war akzeptabel, zumal MOS Technology auch sehr billige ROMs herstellte, die mehr Platz pro Kosten Effizienz anboten. Sie darf dementsprechend verschwenderischer mit Speicher umgehen, wie auch langsamer sein. Das muss man auch bei all ihrer Probleme mit in Betracht ziehen, nach Leistung/Systempreis angeschaut sieht sie einiges besser aus (oder zumindest weniger schlimm).

Die 6502 ist ein reiner 8bit Prozessor, ohne jegliche 16bit Befehle. Sie hat an Registern wie die 8080 nur 1 8bit Akkumulator, und wie die 6800 von der sie abstammt keinerlei Datenregister. Also das wenigste von beiden. Es hat wie bei der 8080 und 6800 nur einen Stackpointer, der aber wie alles andere nur 8bit gross ist, er kann daher nur die Adressen 256..511 benutzen. Die JMP/JSR/RTS sind wie bei 6800 und 6809 (und bis auf die Namen JMP/CALL/RET auch wie beim 8080) identische 3/3/1 Byte und 3/5/3 Speicherzugriffe. Aber wegen Totzyklen mit 3/6/6 Speicherzugriffe an Zeit, im Vergleich zu 8080 optimale 3/5/3, aber 6800 gar 3/9/5. Andere Adressregister hat es 2, X und Y (eines mehr als die 6800 ihr X), die aber auch nur 8bit gross sind, und wie bei der 6800 nur indiziert arbeiten können (und das wegen nur 8bit auch noch "verkehrt herum" als konstante 8bit/16bitBasis + variables 8bitRegisterOfset, statt variable 16bitAdresse + konstanten nbitOffset). Diese sind aber trotzdem erstaunlich nützlich.

Da es keine Datenregister hat, wird wie bei 6800 und 6809 die Arithmetik direkt vom Speicher gemacht, und das wieder mit vollen 16bit Adressen (und 3Byte Befehlen) oder mit kurzen 8bit Adressen (und 2Byte Befehlen). Es hat wie beim 6800 kein DP Register, also nur 1 Block von 256 Bytes, an Adressen 0..255, also eine Zero Page. Diese ist auch zentral für alles. Die Arthmetik selber hat ADC/SBC nur mit Carry, die ADD/SUB ohne Carry fehlen, also muss man vor jeder Rechnung dieses mit CLC/SEC löschen bzw setzen, damit es keine verfälschende Auswirkung hat.

Indirekt adressieren geht nur via einem Bytepaar Adresse in der Zero Page, was solche Befehle mit 1Byte Befehl plus 1Byte Adresse plus 2Byte indirekte Adresse lesen plus 1Byte Datentransfer auf 5 Speicherzugriffe bringt, also langsam wird. Es gibt dabei auch kein automatisch nebenbei verändern, man muss das separat rechnen. Immerhin gibt es dazu noch direkte ZeroPage=ZeroPage+/-1 Arithmetik (INC/DEC), die aber auch 2Byte und 4Speicherzugriffe braucht. Und diese sind nur 8bit, kein 16bit wie bei 8080 seinen INX/DEX, also braucht es 2 davon, und das zweite darf man nur wenn das erste 0 ergibt, es muss sonst mit einem bedingten Sprung übersprungen werden, insgesammt 4 Befehle, 2+2+2+2=8 Bytes, 5+4+2+4=15Zugriffe. Dazu wird als Sprung BNE $+2 benutzt (mit Test auf nicht-Null, = kein Überlauf zu Null), statt mit BCC $+2 (Test auf nicht-Carry, = kein Überlauf zu nächste Bitstelle), weil INC/DEC kein Carry setzen, damit sie in Adressrechnungen nicht das Carry von Datenrechnungen Serien von ADC/SBC stören. (Die 8080 macht das analog, 8bit INC/DEC sind Arithmetik und setzen Carry, 16bit INX/DEX sind Adressrechnungen und setzen gar keine Flags.)

Einen Lichtblick gibt es. Das sind die beiden Indexregister X und Y. Sie sind zwar nur "halbe" mit 8bit, und deswegen verkehrt herum addiert, aber sie retten manches arges Leistungsproblem. Als Beispiel zum Vergleich die schon oft benutzte Kopierschleife:

Kopierschleife als Pseudocode
QA = Adresse Anfang Quell Array
ZA = Adresse Anfang Ziel Array
AN = Anzahl Bytes
Loop:
  TEMP = Speicher[QA]; QA = QA + 1
  Speicher[ZA] = TEMP; ZA = ZA + 1
  AN = AN - 1; if(ZeroFlag=0)goto Loop
Kopierschleife als 8080 Code
LXI H,Adresse-Anfang-Quell-Array
LXI D,Adresse-Anfang-Ziel-Array
LXI B,Anzahl-Bytes
Loop:
  MOV A,M; INX H
  STAX D; INX D
  DEC C; JNZ Loop
  DEC B; JNZ Loop
  (Das 16bit DEX B geht hier nicht)
  (weil es keine Flags setzt, also 2 mal 8bit)
  (DEC mit je einem eigenen JNZ)
(Das sind 11 Befehle, 21 Bytes, und 9 Speicherzugriffe pro Schleifendurchlauf (255 von 256 mal))
Kopierschleife als 6809 Code
LDX Adresse-Anfang-Quell-Array
LDU Adresse-Anfang-Ziel-Array
LDY Anzahl-Bytes
Loop:
  LDA ,X+
  STA ,U+
  LEAY -2,Y; BNE Loop
  (Nur die LEA mit X und Y setzen das Zero Flag(
  (mit U und S aber nicht, also Y als Zähler)
(Das sind 7 Befehle, 18 Bytes, und 10 Speicherzugriffe pro Schleifendurchlauf. Für besser kann man von LDA/STA zu LDD/STD gehen, mit 16bit für halbe Anzahl Durchläufe. Noch besser wär dann 16bit in LDU/STU und ein schnellerer Zähler mit DEC B; BNE Loop; DEC A; BNE Loop (LEAY ist langsam, mit 3 Totzyklen))
Kopierschleife als 6502 Code, naiv übertragen
LDA #Adresse-Anfang-Quell-Array-untere-8bit
STA ZP-QA-unten
LDA #Adresse-Anfang-Quell-Array-obere-8bit
STA ZP-QA-oben
LDA #Adresse-Anfang-Ziel-Array-untere-8bit
STA ZP-ZA-unten
LDA #Adresse-Anfang-Ziel-Array-obere-8bit
STA ZP-ZA-oben
LDA #Anzahl-Bytes-untere-8bit
STA ZP-AN-unten
LDA #Anzahl-Bytes-obere-8bit
STA ZP-AN-oben
(Kopierorgie 3 16bit Zahlen in 8bit Portionen in die Zero Page)
LDX #0
(Weil uns X sonst die Adressen bei (,X) verfälscht)
Loop:
  LDA (ZP-QA-unten,X)
  (Das gibt es nicht als () ohne ,X drin)
  INC ZP-QA-unten
  BNE $+2
    (Zweites INC überspringen,)
    (nur jedes 256ste mal, wenn -unten=0)
    INC ZP-QA-oben
  STA (ZP-ZA-unten,X)
  INC ZP-ZA-unten
  BNE $+2
    INC ZP-ZA-oben
  DEC ZP-AN-unten; BNE Loop
  (Und auch hier in 2 8bit DEC Schritte)
  (Das erste ist zumeist nicht 0)
  DEC ZP-AN-oben; BNE Loop
  (Das zweite folglich auch nur jedes 256ste mal)
(Das sind 25 Befehle, 50 Bytes, und 26 Speicherzugriffe pro Schleifendurchlauf (255 von 256 mal). Wie man sieht wird die Kopierschleife hier naiv übersetzt zu katastrophal gross und dementsprechend auch saumässig ineffizient und langsam, mit 26 im Gegensatz zu 8080 mit 9 und 6809 mit 10, Faktor 2.5 bis 3)
Kopierschleife als 6502 Code, mit Indexregister ausnutzen
LDA #Adresse-Anfang-Quell-Array-untere-8bit
STA ZP-QA-unten
LDA #Adresse-Anfang-Quell-Array-obere-8bit
STA ZP-QA-oben
LDA #Adresse-Anfang-Ziel-Array-untere-8bit
STA ZP-ZA-unten
LDA #Adresse-Anfang-Ziel-Array-obere-8bit
STA ZP-ZA-oben
(Kopierorgie 2 16bit Zahlen in 8bit Portionen ist unvermeidbar)
LDY #0
LDX #0
(Hier werden die Indexregister genutzt, Offset und Zähler)
Loop:
  LDA (ZP-QA-unten),Y
  STA (ZP-ZA-unten),Y
  (Weil Y als Offset zur Adresse addiert wird)
  (gibt es kein INC der beiden -unten)
  INY
  (Und Y selber ist nur 1Byte und 1Zugriff)
  BNE YNotZero
    (Dies nur jedes 256ste mal, Y=0 wird)
    INC (ZP-QA-oben)
    INC (ZP-ZA-oben)
    INX
  YNotZero:
  CPY #Anzahl-Bytes-untere-8bit; BNE Loop
  (Das erste ist zumeist nicht ein Treffer)
  CPX #Anzahl-Bytes-obere-8bit; BNE Loop
  (Das zweite folglich auch nur jedes 256ste mal)
(Das sind 21 Befehle, 40 Bytes, und 17 Speicherzugriffe pro Schleifendurchlauf (255 von 256 mal). Und das trotz zusätzlichen CPY Vergleichsrechnungen. Gerade die Speicherzugriffe wurden also durch Nutzung der Indexregister zu 17/26 (= etwa 3/5), und somit effizienter, und damit das ganze etwa 5/3 mal so schnell, und nur noch Faktor 2 langsamer als 8080 und 6809)
Kopierschleife als 6502 Code, mit umgekehrt laufendem Index
LDA #Adresse-Anfang-Quell-Array-untere-8bit
STA ZP-QA-unten
LDA #Adresse-Anfang-Quell-Array-obere-8bit
CLC; ADC #Anzahl-Bytes-obere-8bit
STA ZP-QA-oben
LDA #Adresse-Anfang-Ziel-Array-untere-8bit
STA ZP-ZA-unten
LDA #Adresse-Anfang-Ziel-Array-obere-8bit
CLC; ADC #Anzahl-Bytes-obere-8bit
STA ZP-ZA-oben
(Kopierorgie 2 16bit Zahlen in 8bit Portionen, aber mit den Adressen fast zum Ende des Blockes verschoben, noch mehr Codeaufwand aber spart später Zeit, mit CPY/CPX vermeiden)
LDY #Anzahl-Bytes-untere-8bit
LDX #Anzahl-Bytes-obere-8bit
(Hier werden Indexregister auf Anfang+Anzahl, und damit auf 1 nach dem Ende des Blockes gesetzt, zum von hinten nach vorne kopieren)
DEY
(Y zählt nun abwärts, auf das Ende des Blockes)
BEQ YZero
(für den Fall, dass genau Y=0 wird)
Loop:
  LDA (ZP-QA-unten),Y
  STA (ZP-ZA-unten),Y
  (Y zur Adresse addiert gibt das Blockende)
  (gibt es kein DEC der beiden -unten)
  DEY
  (Y nun abwärts, für nächsten)
  BNE Loop
YZero:
  (Dies nur jedes 256ste mal, wenn Y=0 wird)
  LDA (ZP-QA-unten),Y
  STA (ZP-ZA-unten),Y
  DEY
  (Diese alle kopieren. Weil aber vor DEC -oben)
  (Rechnung ist duplizierter Code unvermeidbar)
  DEC (ZP-QA-oben)
  DEC (ZP-ZA-oben)
  DEX
  CPX #255; BNE Loop
  (Abbruch wenn X = 255 = unten aus Block hinaus)
(Das sind 28 Befehle, wieder 50 Bytes (wegen den Duplikaten), aber nur noch 13 Speicherzugriffe pro Schleifendurchlauf (255 von 256 mal), ohne auch den zusätzlichen CPY, und somit noch effizienter, und damit wird das ganze mit 13/26 (= 1/2) nochmals schneller, zu doppelt so schnell, und nur noch Faktor 1.5 langsamer als 8080 und 6809, und damit akzeptabel)

Hier sieht man wie wichtig es ist, den Prozessor den man benutzt zu kennen, wo er Stärken hat, die seine Schwächen kompensieren können, weil dabei immerhin 26 zu 13 als Halbierung der Zeit, bzw 26/9.5=2.7 zu 13/9.5=1.4 drin liegt, von Katastrophal zu akzeptabel. Ein Compiler tut nun einmal übersetzen, einen Compiler Schreiben ist in etwa einen Übersetzer ausbilden, und dazu muss man die Zielsprache ihre Möglichkeiten sehr gut beherrschen.

Wie sieht nun der Code einer Forth Implementation für den 6502 aus? Mangels jeglicher 16bit Befehle, und ohne kombinierte Stack+Arithmetik wird er wie beim AVR viel Code brauchen, also ist nichts mit direct compiling. Mit subroutine threading wird es 3 Bytes pro JSR brauchen, 50% über einem direct oder indirect threading, aber etwas mehr Speicherverbrauch ist ein Teil des 6502 Ansatzes. Anderseits wird ein direkt/indirekt threading sehr viel langsamer zum entthreaden, ohne Adressregister für ein effektives IP (und die Indexregister können hier leider gar nicht helfen). Also nimmt man hier subroutine threading.

Damit muss man den Code direkt mit PC++ ausführen, mit JSR und RTS, folglich mit SP als den Returnstack. Das ist wegen dem 8bit SP limitiert auf 256 Bytes, aber das reicht locker aus, ANSI empfiehlt in ANS Forth 24Wort/48Byte an Returnstack zu haben. Die Daten können daher nicht auf den Prozessorstack, der aber ohnehin nur mit 8bit PHA/PLA benutzbar ist, und auch keine Arithmetik im gleichen Befehl wie Stackzugriff hat (was die Zero Page Speicherzugriffe alle können), also verliert man nicht viel. Ohne Register ist auch kein TOS Cache möglich, also im ersten Ansatz geradeaus, wie mit dem naiven 8080 Code. Alles andere muss in die Zero Page, die als "256 Register" dienen muss, und damit auch einen TOS "Cache" bieten kann.

Zuerst kommt eine naive Implementation, mit der Datenstack Adresse in der Zero Page, und Zugriff auf den Stack mit (nn,X), mit permanent X=0 gesetzt, wie oben in der naiven Kopierschleife. Separat davon ist auch ein TOS "Cache" in der Zero Page, wenigstens ist dort direkte nn Adressierung.

Der 6502 naive subroutine threading Code wäre dann (nur teilweise, zum den Aufwand zeigen):

+
Add:
LDA (D-Stack-Adr-unten,X); INC D-Stack-Adr-unten
  BNE $+2; INC D-Stack-Adr-oben
CLC; ADC TOS-unten; STA TOS-unten
LDA (D-Stack-Adr-unten,X); INC D-Stack-Adr-unten
  BNE $+2; INC D-Stack-Adr-oben
ADC TOS-oben; STA TOS-oben
RTS
(Wie man sieht ist das einiges an Aufwand, weit schlimmer als selbst bei der 8080 subroutine threading Subtraktion mit BC Datenstack. 14 statt 9 Befehle, 26 statt 9 Bytes, 46 statt 13 Speicherzugriffe, also 3.5 mal langsamer, und damit komplett katastrophal!)

Es gibt aber ein bessere Implementation. Hier wird der Datenstack Pointer in ein Indexregister gespeichert, am besten in X und nicht in Y, damit die (),Y Adressierung frei bleibt. Dann wird mit 0,X indiziert auf den Stack zugegriffen, und mit INX/DEX verändert, was einiges schneller wird. Also wieder mal Indexregister als Rettung. Dabei kann man auch gleich 2,X nutzen für auf das zweite Stackelement zugreifen. Wieder ein Fall von den Prozessor kennen, die darauf wirksamen Tricks. Eine Limite ist, dass der Datenstack damit in die Zero Page passen muss, was wegen 8bit X auf 256 Bytes limitiert, aber das reicht auch hier locker aus, ANSI empfiehlt in ANS Forth 32Wort/64Byte an Datenstack zu haben.

Der 6502 Indexregister Stack subroutine threading Code wäre dann (wieder nur teilweise, zum den geringeren Aufwand zeigen, der Rest ist dann nach dem selbigen Muster 1:1 zu übersetzen):

+
Add:
CLC; LDA 0,X; ADC TOS-unten; STA TOS-unten
LDA 1,X; ADC TOS-oben; STA TOS-oben
INX; INX
RTS
(Wie man sieht deutlich weniger, 10 statt 14 Befehle, 17 statt 26 Bytes, 22 statt 46 Speicherzugriffe, wieder nur die Hälfte, und weit effizienter und mehr als doppelt so schnell, und damit von 46/13=3.5 zu nur noch 22/13=1.7 mal langsamer, wieder akzeptabel)
(Man kann sogar eines der beiden INX einsparen, wenn man den Stack von z.B. 32*2Bytes in 2*32Bytes umordnet, mit allen unteren Bytes zusammen (in Adressen 0..31, mit Index 0,X), und allen oberen zusammen (in Adressen 32..63, mit Index 32,X))

Novix NC4000

Bisher hatten wir alles normale Standardprozessoren, die eigentlich alle für Assembler designt wurden, vielleicht mit etwas Ausrichtung auf typische Algol-artige Hochsprachen compilieren, die aber auch nur einen Stack brauchen und möglicherweise indizierte Adressierung. Nun kommt der Novix NC4000, der mitte 1980er spezifisch für Forth compilieren designt worden ist, mit Forth Erfinder Charles Moore als einen Beteiligten. Dieser wird heute noch hergestellt, in Weiterentwicklung, als Harris RTX-2000.

Der NC4000 ist ein reiner 16bit Prozessor, mit 16bit Speicher, wie die PDP-11, und ebenso doppelt so schnell. Er hat aber keine 8bit Befehle. Er kann nicht einmal separate Bytes zum Speicher herauslesen, der auch nur wortweise adressiert wird. Dazu muss man 16bit lesen und dann shiften und maskieren, aber das wird ohnehin nur in C! und C@ benutzt.

Der ganze Datenpfad und die Register sind dafür auf die direkte Ausführung von Forth Befehlen ausgelegt. Es hat dazu spezialisierte Register für den TOS (T genannt), das zweite Stackelement (N genannt für NEXT), und das erste Returnstack Element (I genannt für Index, weil dort auch der FOR .. NEXT Zähler/Index ist). Ausserdem hat es die beiden Stacks (in zwei separaten Chip-externen vom 64kWort/128kByte Hauptspeicher unabhängigen 256Wort/512Byte Stackspeichern), sowie deren Adressregister (die daher auch nur 8bit sind).

Diese sind alle derart verdrahtet, dass mehrere forthtypische Datenbewegungen zwischen ihnen gleichzeitig möglich sind, womit die meisten Primitives in einem Befehl und einem Speicherzugriff an Zeit ablaufen. Das gilt selbst für sowas ansonsten aufwendiges wie SWAP, ohne das "im Dreieck kopieren".

Die Stackspeicher laufen auch gleichzeitig wie der Hauptspeicher, und brauchen daher auch ihre eigenen Anschlusspins, und der NC4000 Chip hat daher auch ein damals noch monstergrosses 121 Pin Gehäse. Dafür können aber neben den Registern auch alle 3 Speicher gleichzeitig bearbeitet werden, in einem Multispeicherzugriff, von 16+16+16=48bit.

Den Datenstack kann man damit unabhängig von Hauptspeicher benutzen (und ebenso den Returnstack). Nur die ! @ sowie 16bitLiteral gehen auf den Hauptspeicher los. Damit wird zumeist der nächste Befehl geholt während der letzte noch ausgeführt wird. Damit bekommt man fast die ganze Harward Geschwindigkeit, ohne dessen Forth kastrierende Limiten. Das erhöht die Effizienz noch weiter, mit Chancen auf über 50%.

Alle Befehle sind 1Wort/2Byte, ausser dem 16bitLiteral mit der 16bit Konstante als zweites Wort (es gibt aber auch 5bitLiteral in 1Wort/2Byte). Es gibt auch keine 2Wort/4Byte Befehle, und keine 2 Speicherzugriff Befehle ausser denen mit Hauptspeicherzugriffen, also ! @ sowie 16bitLiteral. Selbst der CALL besteht aus nur Bit15=0 und einer 15bit (Bit14..0) Adresse. Damit ist subroutine threading gleich kompakt wie direct oder indirect threading, und immer noch weit schneller, wesshalb hier subroutine threading gemacht wird. Es sind damit kein IP oder W nötig. Alle anderen Befehle, mit Bit15=1, fallen mit Bit14..12 auswählend in 8 Befehle die in 3 Gruppen passen. Insgesammt ergibt das:

Die eigentlichen 1000.oooo.oooo.oooo Rechnen und Datenstack Befehle, und der 11xy.oooo.oool.llll Speicherzugriff Subset davon, sind dann extern mikrocodiert. Das heisst die einzelnen 12 bzw 7 "o" Bits steuern direkt individuelle Datenpfad Features an, die damit auch beliebig kombinierbar sind, zum teilweise mehrere Primitives in einem Befehl packen. Der Rekord sind 5*2 Varianten 4er Kombinationen von SWAP OVER +/-/AND/OR/XOR 2*/2/ in einem Befehl. Damit kann man die Effizienz auf teilweise über 100% treiben. Die "o" Bits sind dabei folgende:

Weil damit alle wichtigen Primitives 1Wort/2Byte sind, sind diese wieder gleich kompakt wie subroutine oder direct oder indirect threading, wesshalb hier direct compiling gemacht wird. Alles aufwendigere als 1 Befehl wird zu Secondaries (wie ROT als >R SWAP R> SWAP, die in Forth codiert sind, und wiederum mit direct compiling entstehen, und damit troth Forth Code gleich schnell sind wie normale subroutine threading Primitives die in Assembler codiert sind.

Das alles läuft mit bis zu 8MHz ab (sofern die Speicher das auch aushalten, normal waren underclocked auf 4MHz), in 1986er CMOS Technologie. Daher waren auch nur 2*8bit Paare von schnellen EPROM (mind 2Forthsystem) sowie SRAM (mind2Hauptspeicher + 2Datenstack + 2Returnstack) Speicherchips brauchbar.

(Als Vergleich: die 8068 und 68000 waren trotz damals schnellerem NMOS nur 8MHz, und das mit 4 Takten pro Speicherzugriff, also nur 2MHz Speicherzugriffe, und oft mehrere Speicherzugriffe pro Befehl, und oft mehreren Befehlen pro Forth Wort. Damit war der NC4000 etwa 10 mal schneller als diese 16bit (und 30 mal schneller als eine 6809 mit direct compiled und 100 bis 300 mal schneller als alle anderen mit subroutine oder gar direct/indirect threading). Und das trotz der viel kleinere Chip sein als diese. Der Name NC4000 kommt davon, dass der Chip ein Gate Array ist, mit 4000 CMOS Standardgatter (a je 4 Transistoren), also 16000 Transistoren insgesammt. Die 8086 und 68000 hatten 29000 bzw 38000 Transistoren)

Auch der Returnstack ist auch unabhängig von Hauptspeicher. Damit ist ein CALL gleich schnell wie ein JMP, nur 1Wort Befehl, und nur 1 Speicherzugriff. Der RET ist noch kompakter, er ist bei allen Rechenbefehlen in Form von Bit5 eingebaut, welches bei Bit5=1 zusätzlich zur Rechnung auch noch zurückspringt, und damit strikte einen 1/16Wort Befehl und 0 Zugriffe kostet! Das ist zumindest so, wenn vor dem RET ein Arithmetik Befehl ist. Ein RET nach einem CALL kann man aber wie üblich per tail call optimieren. Und nach einen Branch kann man es gleich ganz weglassen. Nur nach einem Zbranch Loop muss man einen NOP hinstellen, alle Bit11..0 = 0, und dann nur Bit5 = 1 setzen. Mit diesen schnellen CALL und noch schnelleren RET sind auch Secondaries noch kompakter und schneller, womit man Primitives mit mehreren Befehlen erst recht zu subroutine compiling oder gar Secondaries machen kann. Das ROT als >R SWAP R> SWAP Secondary ist ganze 4Wort (inklusive dem RET im zweiten SWAP) und 5 Speicherzugriffe (inklusive dem aufrufenden CALL Rot).

(Als Vergleich: Ein simples + braucht beim NC4000 1 Zugriff, PDP-11 2 Zugriffe, 6809 4 Zugriffe, eine 8080 mit TOS Cache ohne Prozessorstack direct compiled 9 Zugriffe und subroutine threading 9+8=17, eine 6502 mit X Stack subroutine compiled 22 Zugriffe! Ein SWAP alleine ist beim NC4000 1 Zugriff, PDP-11 5 Zugriffe, 6809 10 Zugriffe, 8080 direct compiled 15 und subroutine threading 15+8=23!)

Ein weiterer Vorteil der separaten Stacks ist, dass wenn der ganze 256Byte Block vollgeschrieben wird, die 8bit Stackadresse wieder zu 0 wird, und es damit wieder von vorne losgeht. Dieses Verhalten nennt man wraparound, und solche Stacks zirkuläre Stacks. Damit ist kein Überschreiben vom Hauptspeicher mehr möglich, das nennt man einen Stacküberlauf bei einem PUSH DUP OVER oder Literal zuviel bzw einen Stackunterlauf bei einem POP oder Arithmetik zuviel. Damit ist, sobald ein ABORT" beide Stacks gekillt hat, ein weiterarbeiten mit einem garantiert unbeschädigten Dictionary möglich. Aber es kommt noch besser: Die Stacks müssen weder beim Aufstarten initialisiert, noch beim ABORT" gelöscht werden, können es hier aber. Beim Returnstack wird QUIT ohnehin niemals einen Rücksprung machen, und beim Datenstack bleibt einfach der Inhalt unbeachtet und unbenutzt liegen, nicht anders als bei einem HP RPN Taschenrechner.

(Auf anderen Prozessoren müssen die Stacks einfach genug gross sein, dass man sie hoffentlich nie überläft. Das vermeiden würde Tests nach jedem verändern brauchen, die viel Zeit kosten, oder man müste ein wraparound simulieren, mit einem AND nach jedem verändern, was auch einiges kostet. Am ehesten geht das noch mit 8bit RegisterOffset wie beim 6502, sowie dessen 8bit SP. Das gibt von sich aus einen problemlosen Returnstack wraparound ohne jeglichen Aufwand, aber der X Datenstack kann problematisch sein. Damit würde die ganze Zero Page überschrieben werden, womit jegliche nicht-Datenstack Nutzung davon (z.B. zumindest die ! @ brauchen ein LDA/STA (Adresse-unten),Y) kollidiert. Also wird man bei diesen die beiden Adressbytes immer wegspeichern und restaurieren müssen. Bei den 6510 bzw 8502 der C64 bzw C128 versagt dies dann ohnehin. Diese haben bei Adressen 0 und 1 einen 6bit Port, dessen Überschrieben die Speicherverwaltung killen würde, mit fast garantiertem Absturz. MOS Technology hätte den Port besser bei 0200 und 0201 angelegt, oder sie weggelassen und die Speicherverwaltung in IO bereich mit 2 CIA PIO Bits gemacht.)

Neben dem NC4000 Prozessor ist aber auch das dafür geschriebene cmForth sehr neuartig und optimierter:

Gerade auch mit letzterem wurde die Sprache an die Hardware Möglichkeiten angepasst. Dies ist auch typisch Charles Moore. Eines seiner Aussagen ist, dass er der einzige sei, der nie Forth lernen musste, weil er einfach seinen Programmierstil benutzt habe, und das sei eben Forth geworden. Daher verwandelt er auch sein Forth genauso wie seinen Programmierstil. Er meint auch, dass jeder sein eigenes Forth schreiben sollte, das sein eigener Programierstil ist, und das er in und auswendig kennt. Ebenfalls sollte man auch andere ihre Forths anschauen und gutes daraus nehmen, alle sich nach und nach verbessernd, und dabei wiederum selber kopiert werden. Damit läuft seine Ansicht darauf hinaus, dass Forth Systeme schreiben analog zu einem wissenschaftlichen Diskurs wird, immer bessere Entdeckungen und Theorien verbreitend. Dementsprechend hat er auch cmForth zu public domain erklärt, damit jeder es nutzen kann, wie wissenschaftliche Erkenntnisse. Dementsprechend ist er auch ein Gegner von ANSI ihrem ANS Forth Standard, das er als "den Stand von vor 20 Jahren festschreiben" anschaut. Das wäre dann analog zu einem Dogma zementieren sein.

Diverse MuP20/P20 MuP21/P21 F21 i21

Wenn Charles Moore schon sein Forth stetig verwandelt und verbessert, auch bei andern schauend, dann wundert es nicht, dass er dies auch mit seinen Prozessoren macht, stetig verbessernd, und auch andere anschauend. Einer den er angeschaut hat, ist ein 32bit Forth Prozessor namens ShBoom, von Patriot Systems. Über diesen findet man wenig Dokumentation, ausser Aussagen dass es statt naheliegenden riesigen 32bit Befehlen eben 4 8bit Befehle in ein 32bit Wort packt, und damit nur alle 4 Befehle einen Befehlscode Speicherzugriff braucht, und damit noch schneller wird.

Dabei hat Moore in diversen Firmen und Projekten eine Serie von nach und nach verbesserten Prozessoren erzeugt, angefangen mit den MuP20/P20 MuP21/P21 und später F21 und i21. Diese sind alle 20bit Prozessoren, daher auch das 20 im Namen beim MuP20/P20, weil Charles Moore 16bit (und +/-32k Zahlenbereich) für zu klein, aber 32bit (und +/2M Zahlenbereich) für zu gross hält, und dazwischen 20bit (und +/-512k Zahlenbereich) als ideal erachtet, zumal damit beim MuP21/P21 noch ein DIP40 Gehäuse drin lag (was beim F21 zu einem PLCC68 wurde), mit 20Pin Datenbus und 10Pin Adressbus (multiplexed 2*10bit für 1MWort DRAM, sowie simplex 1*10bit für 1k IO, und mit Datenbus auf 10bit reduziert und 10+10bit Adresse für 1MByte 8bit Flash oder SRAM).

Der Datenpfad ist analog zum NC4000, abgesehen von den 4 Bits mehr. Es hat das T Register. Die beiden N und I Register fehlen teilweise, da die beiden Stacks nun auf dem Chip sind, was 2*(16+8+1)=50Pins spart. Sie sind dafür kleiner, wie gross variert (genaue Zahlen fehlen mir zumeist, F21 und i21 haben T S(=N) und R(=I) sowie 2*16 Stacks, MuP20/P20 und MuP21/P21 sollen noch kleiner sein, unter 10!), was aber ausreicht. Die beiden Stack Adressen Register sind nicht mehr schreib/lesbar, weil mit zirkulären Stacks keine Notwendigkeit dazu mehr da ist. Trotz Stacks sind sie Chips noch kleiner geworden, der MuP20/P20 hat noch ganze 6500 Transistoren, sowie MuP21/P21 7000, die F21 bzw i21 leicht über 10'000.

Völlig neu ist der Befehlssatz, mit 4 5bit Befehlen in 20bit, und damit ohne extern mikrocodiert. Die 5bit sind dann Indizes in einen internen Befehlsdecoder seinem ROM (oder eher seinem PLA). Damit gibt es aber auch keine kombinierten Befehle mehr, welche aber ohnehin schwierig vom Compiler auszunutzen waren, sondern einfach 4 Einzelbefehle pro Wort zu holen, was jeglichen Code beschleunigt, auch den von einem simplen nicht auf den Prozessor optimierenden Compiler (mit nur generischem tail call/recursion optimieren). Das ergibt theoretisch bis zu 400% Effizienz, aber real maximal etwa 80% davon nutzbar, also etwa 0.8*400%=320%. Damit können diese Chips aber auch mit simplen langsamen FP DRAMs (bzw ab F21 SDRAMs) optimal laufen, und schnell werden, und das ohne irgendwelche Caches zu nutzen und ohne deren Aufwand.

Dazu wird erst recht die ganze Arithmetik im Stack statt Hauptspeicher benötigt, mit nur selten Variablenzugriffe, zum nicht mit (S)DRAM Pagewechseln den Speicher ausbremsen (bzw mit im Page bleiben die Bandbreite vermehrfachen). Der FP DRAM bzw SDRAM Controller ist dazu direkt im Prozessorchip drin (in PCs ist er vor dem Athlon um ca Jahr 2000 extern im Chipset drin). Beim F21 läuft das SDRAM solange im Page geblieben wird mit 100MHz Zugriffe und liefert 400MHz 5bit Befehle zum 400MHz und 400MIPS Prozessor (und das Mitte 1990er). Beim MuP21/P21 war das noch 1/4 davon, also 100MHz und 100MIPS aus DRAMs mit 25MHZ im Page (real sind wegen Pagewechselpausen 80MIPS erreichbar). Man erhält damit also sehr viel Leistung trotz kein Cache (damals waren PCs etwa bei Pentium II mit 200..300MHz und massiven 2-level Caches, die beim Pentium II für den 2nd Level einen zweiten Chip im teuren Gehäse brauchten).

Damit sind auch Konstanten und Adressen problematisch. Diese werden daher auch als n*5bit in die Befehle gepackt, wobei CALL scheints in einigen der Chips (AFAIK die MuP20/P20 und MuP21/P21) nur eine 10bit(!?!) Konstante hat, also nur Aufrufe innerhalb einer 1kWort (= 4k*5bitBefehle) Page an Code zulässt (weiter braucht langsame berechnete Sprünge mit EXECUTE). Nach den 2k*16bitBefehle des cmForth war das dem Charles Moore scheints genug. Andere haben sich aber gross darüber beschwert, wesshalb es ab dem F21 mehr ist, wahlweise 10bit 1kWort Pages oder 15bit 2*16kWort Pages, und letzteres mit Home Page und Current Page. Branch/Zbranch sollen mit 5bit Adressen um +/-16Worte (= +/-64Befehle) springen können.

Die ! @ verwenden die 20bit Stackdaten als Adressen, was 1MWort Speicher erlaubt, immerhin 2.5MByte. Dazu verwenden sie aber scheints eine Adressrechnung mit einer Addition darin, die mit deren Carry 21bit Adressen generiert. Der namensgebende Unterschied von MuP20/P20 zu MuP21/P21 war die Nutzung dieses Carry als Adressraumverdoppler zu 21bit Adressen, wobei die MuP21/P21 fest 1MWort Carry-los adressiertes DRAM und dazu mit-Carry IO und Flash unterstätzt. Ab F21 wird das DRAM zu identisch grossem SDRAM.

Ein weiteres Speicherdetail ist, dass im NC4000 der ! sehr schwierig war. Das benutzen von 2 Stackelementen kostet bei normalen Prozessoren oft mehrere Befehle, und beim NC4000 mehrere interne Datenverschiebungen, die sich gegenseitig behinderten. Im diesen Chips werden die ! @ nun "aufgespalten" in je 2 Befehle, einerseits die Adresse vom TOS zu einem separaten Adressregister "A" transferieren, und dann Speicher TOS schrieben oder lesen mit immer A als Adresse. Als Nebeneffekt kann analog zum PC++ auch ein A++ gemacht werden, womit nun A einmal vor Schleifen gesetzt werden kann, und dann in der Schleife nur noch !A++ @A++ benutzt werden muss, was Forth beschleunigt, weil kein Daten und Adressen Gemisch auf dem Stack ist. Ab dem F21 wird auch das oberste Returnstack Element als zweite Adresse mit !R++ @R++ benutzbar, für Kopierschleifen. Strikte wird mit all diesem der Forth Stack Ansatz aufgeweicht, aber nur für einen weit verbreiteten spezifischen Vorteil mit geringem Aufwand, und genau dafür ist Charles Moore ja bereit, sein Forth zu verändern/optimieren.

Ein weiteres unübliches Feature ist neben dem (S)DRAM Controller auch der auf dem Prozessor integrierte Videogenerator, und das in den frühen 1990ern, während Intel erst in den späten 2000ern Video in den Chipset integrierte! Dieser war zumindest bei den MuP20/P20 und MuP21/P21 ein Bitmap NTSC TV Videogenerator mit ein 20bit Wort für 4 5bit Pixel, mit 0..15=16 Farben und 16..31 Steuerkommandos für den Videoframe bauen. Der Chip selber kann kein Frame zeichnen, er kann nur einen dauernden Strom von 5bit vom Speicher schaufeln, auch während dem Zeilen- und Bildrücklauf, mit dann eben den Steuerkommandos drin. Video kostet etwa 1/4 der Speicherbandbreite und damit auch der Geschwindigkeit. Ab F21 ist statt NTSC ein kombinierter NTSC oder RGB/VGA Generator drin, sowie noch DMA basierte 8bit AD und DA Wandler mit je 20MSamples Durchsatz, sowie ein DMA basierter serieller Netzwerkprozessor, ebenfalls ist ein PIO Port auf dem Chip drauf, womit der F21 Prozessor eigentlich ein System on Chip (SoC) ist, und das mit bloss leicht über 10'000 Transistoren, in PLCC68. Ein Experiment war ein 3 Chip (F21 Prozessor + SDRAM + Flash) Miniaturrechnerchen, das 400MIPS liefert, und in eine Maus passt.

Neben den Prozessoren ist aber auch das dafür geschriebene MachineForth bzw HardwareForth bzw colorForth weiter optimiert:


Home | Artikel | VCFe Forth Interna

Diese Seite ist von Neil Franklin, letzte Änderung 2011.05.06