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 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.
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.
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:
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:
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:
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.
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):
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.
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:
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):
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:
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.
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):
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).
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!)
: 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:
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:
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:
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.
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:
: 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.
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.
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:
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:
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:
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):
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.
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):
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.
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:
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):
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):
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.
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:
Diese Seite ist von Neil Franklin, letzte Änderung 2011.05.06