Ideen & Entwicklungsschritte

1. Erstmal ein ISA-Spec!

Bevor man loslegt, sollte man einen Plan haben (und am besten schriftlich fixieren), wohin die Reise gehen soll! Wenn man erstmal anfängt zu definieren, stellt man schnell fest, was noch so alles fehlt. Zunächst habe ich eine Spezifikation der neuen 32-Bit “Instruction Set Architecture” (ISA) erstellt. Im Laufe der Zeit habe ich diese immer wieder erweitert, je nach Erfordernis. Irgendwann passten dann die Bitmasken nicht mehr so richtig (es war halt nix mehr frei) und das einfache Ausgangsschema musste verlassen werden (die blau & dunkelgrün hinterlegten Befehle) - 🗣“beim nächsten Mal wird alles 64-Bit & viel viel besser …”

Eine kleine Feature-Liste:

16 Integer Register ✔
Pseudo-Ops (vereinfachte Befehlssyntax) ✔
Return mit variabler Zahl von Rückgabeparametern (wenn auch derzeit nur 0=keiner oder 1=einer genutzt …) ✔
Interrupt-Support (Hardware & Software), erfordert weitere Flags ✔
Programmzählerrelativer Code (erforderlich wg. nachladbarer “Apps”, getrennt vom “Betriebssystem”) ✔
Indirekte Sprünge (anhand eines Registerinhalt), erforderlich für späteren Funktionszeigersupport ✔
Trennung von globalem (“OS”) & statischem (“App”) Framepointer ✔
Geänderte Variablen(nicht)initialisierung ✔
Einige “Spezialbefehle” zur Kommunikation mit der “CPU” (dem Emulator) ✔
Fliesskommaunterstützung (16 Float Register) ✔

Für eine wirklich detaillierte Aufschlüsselung gibt es die Referenz.

2. Die “Hardware” will auch umrissen sein …

Der Emulator bleibt weiterhin eine Harvard-Architektur, d.h. RAM & ROM werden getrennt adressiert, jeweils 512K. Es sollen mehr “Devices” unterstützt werden, nicht nur ein einfacher Schwarz/Weiss-Bildschirm und die Tastatur. Für Timer-Interrupts wird ein Hardware-Timer erforderlich sein. Um nachladbare Programme zu ermöglichen, wird ein persistenter Speicher erforderlich sein (vulgo: eine Festplattenunterstützung). Im Detail kann das in der Beschreibung zum Betriebssystem nachgelesen werden.

3. Erste Schritte

Mit obigen Festlegungen kann jetzt zunächst ein Assembler für die neue Architektur geschrieben werden. Mit dem kann man dann “Spielmaterial” für den - ebenfalls neu zu erstellenden - Emulator erzeugen.

Wenn hier was geht, kann man sich dem Übersetzer von VM-Code zu Assembler widmen. Auch hier kann man auf bereits im Kurs (s.o.) erstellte Sourcen zurückgreifen und muss (zunächst) nur die Code-Erzeugung anpassen.

Im Frontend, dem Jack-Compiler, muss man Anpassungen wg. der variablen Anzahl von Rückgabeparametern vornehmen.

Jetzt kann man also bereits Jack-Programme für die neue Architektur übersetzen und auf dem Emulator laufen lassen. Gut, dann zum nächsten Punkt …

4. Verbesserungen

Fehlermeldungen

Schnell kommt das Bedürfnis nach verbesserten Fehlermeldungen auf. Falls es noch nicht klar war: Das nimmt im Frontend einen sehr großen Raum ein (20 - 30%) … und es ist nie genug! Das es gelegentlich nicht mal hilfreich ist, kennt jeder von seinem C-Compiler (strukturell durch Parser bedingt - könnte allerdings mit zusätzlichen Parsing-Läufen gelöst werden … ☮).

Im Backend sollte auch noch nach fehlenden Symbolen gesucht werden …

Inline Assembly

Mittels inline Assemblercode in der Hochsprache erschließt man spezielle Prozessorbefehle (die nie vom Compiler erzeugt würden). Damit kann man dann z.Bsp. das Flag-Register in lokale Variablen umladen - und dann direkt in der Hochsprache damit arbeiten. Auch kann man jetzt recht frei am Stack “rumfummeln” was erstaunliche Möglichkeiten erschliesst (z.Bsp. variable Argumentlisten 💡!).

Nachteil: Der Code ist nicht mehr portabel (was zunächst mangels Alternative völlig wurscht war).

HV2OS & HV2FS

Das ursprüngliche BIOS/Betriebssystem wird aufgepeppt und nach & nach zu einem “richtigen” Betriebssystem ausgebaut (“HV2OS”). Dazu zählt insbesondere die Möglichkeit, Programme (“apps”) nachzuladen & zu starten (und auch: von Apps andere Apps nachzustarten).

Damit Programme aber an variable Adressen geladen werden können, sollte es programmzähler-relative Sprünge geben. Warum? Sonst explodiert die Relokationstabelle (s.u.), d.h. jede lokale Verzweigung oder Sprung müsste erfasst werden 💡!

Also: im HV2 Spec. wieder passende Opcodes nachzurüsten …

So, jetzt ist doch alles bereit!? Nicht ganz: Innerhalb eines Programms reicht das, was aber ist mit Sprüngen nach außerhalb (z.Bsp. OS-Funktionsaufruf)?

Nun kommt der “Trick” (ok, natürlich ein alter Hut!): Wenn man jedem Programm eine Relokationstabelle mitgibt - also ins Binary mitreinkompiliert - kann ein “Loader” im Betriebssystem die dort aufgeführten Offsets - die rein “zufällig” relative Adressreferenzen darstellen 🤔😎 - dynamisch anpassen. Et voilà! Funktionsaufrufe in “Fremdprogrammen” (hier: HV2OS) sind möglich.

Anmerkung: Aus Geschwindigkeitsgründen sind Funktionsaufrufe als direkte Sprünge ausgeführt und nicht als S/W-Interrupts (dort hätte das Problem so gar nicht existiert!) Außerdem wurden getrennte Register für den statischen Variablenzugriff festgelegt, im OS gilt der GLOBAL Pointer, sonst STATIC - was wiederum eine passende Compileroption erforderlich macht (OS/Non-OS).

War’s das jetzt? Nope! Es fehlt noch ein Dateisystem um Programme von irgendwoher nachladen zu können (im Original-Kurs gab es nur ein Gesamtprogramm das gestartet wird, ähnlich einem Micro-Controller-Programm - think ESP, Arduino etc.). Der Emulator hält ein relativ dummes “Block Device” vor, es kann nur ganze Sektoren lesen bzw. schreiben. Also erstmal wieder ein (oder eine?) Spec. schreiben: “HV2FS Das Dateisystem”. Es ist sehr primitiv, erledigt aber den Job (Details können hier nachgelesen werden).

Im Betriebssystem gibt es eine Funktion - im “Relocator” Modul - mit der man Programme direkt nachladen (und auch starten!) kann. Diese wiederum stützt sich massiv auf Dateizugriffsfunktionen im Modul “FileSystem”, wo sie so etwas wie die Konkretisierung der Ideen zu HV2FS bilden und das darunterliegende Modul “BlockDevice” für den Zugriff auf die Emulation der HV2 Platform nutzen.
Das Modul “FileSystem” ist auch für den Anwender wichtig, hier finden sich die typischen Dateizugriffsoperationen wie read/write/open/unlink etc. und auch findfirst/findnext zum Durchsuchen des Dateisystems …

Zu guter Letzt gilt es jetzt noch ein Problem zu lösen: Da Betriebssystem & Apps jetzt separat erzeugt werden können, müssen die Einsprungadressen (und zwecks Überprüfung vorzugsweise auch die Argumente) von Funktionen als Symbole vom Betriebssystem exportiert und von Applikationen importiert werden können.

Multitasking

Da ein H/W-Timer nebst Interrupt-Auslösung (und entsprechender Flag-Behandlung) im Emulator zur Verfügung steht, kann ein Task-Switcher erstellt und an den H/W-Timer angebunden werden.

Die Integration wird über ein zusätzliches “Tasks”-Modul im Betriebssystem bereitgestellt (und ja: ein “yield()” gibt’s auch!). Schnell zeigt sich: Ohne Semaphoren wird das nix! Also die HV2 Platform Spec. nach einmal überarbeitet und einen entsprechenden (atomic) Befehl hinzugefügt.

Aus Semaphoren kann man dann Mutexe & “Critical Sections” ableiten. Alles zusammen findet sich im Modul “Semaphore” im Betriebssystem.

Print

Schön wäre eine Ausgabefunktion mit variabler Argumentzahl und Formatierungsmöglichkeit (Nein, so etwas war nicht Bestandteil des Original-Kurses!). Angelehnt an das bekannte printf() von “C”, findet sich jetzt Entsprechendes im Modul “Output” als “Output.print”.
Fun fact: Dieser Wunsch war ursprünglich der Auslöser für das Implementieren von “Inline Assembly” (s.o.) …

Optimierungen 1

Im Original werden die lokalen & Instanz-Variablen mit Null initialisiert. Hier könnte also ausgedünnt werden! Problem: Das ist ein “breaking Change” mit anderen Jack-Sources.

Lösung: Sourcen überarbeiten & wo nicht möglich eine Compiler-Option, die die Initialisierung per Compiler erzwingt ("- -initlocals", zu verwenden mit VM2ass.bin).

In der Praxis nutzt etwa die Hälfte der existierenden Jack-Programme dieses - durchaus zweifelhafte - Feature der Originalsprache.

Im Original muß jede Funktion immer mittels “return”-Anweisung beendet werden. Die HV2 CPU unterstützt jedoch im Opcode 0..255 Rückgabewerte (RETURN #<n>). Von hier ist es jetzt nur noch ein kleiner Schritt weiter zum Weglassen der “return”-Anweisung bei void-Funktionen.

Mehr Speicher

Da die I/O-Ebene des Kurs-Originals beibehalten (Screen, Keyboard) und nur der I/O-Bereich erweitert wurde um zusätzliche Geräte, stellt sich ein interessantes Problem, wenn man den “RAM”-Speicher erweitern will: Wie adressieren?

Einfacher als man zunächst denkt (Highmem u.ä.?): Einfach in der Memory-Freelist einen Block hinter dem I/O-Bereich anhängen. Läuft …

Cursor blinken

Manchmal sind es die kleinen Dinge! Wenn man die Eingabefunktionen mit einer Cursorblinkfunktionalität aufpeppt, sieht alles gleich viel echter aus …

TSR Unterstützung

Es wäre schön, wenn sich zusätzliche “Hilfsprogramme” im Speicher verankern ließen und z.Bsp. über S/W- oder H/W-Interrupts erschlossen werden könnten (erinnert sich noch jemand an Borlands Sidekick?). Diese früher “terminate-and-stay-resident” (TSR) genannte Funktionalität soll vom Loader unterstützt werden.

Der HV2Clock-Source ist ein Beispiel dafür, eine Uhr die parallel zum eigentlichen Programm oben rechts mitläuft.

make Unterstützung

Lange habe ich ein einfaches Script für die einzelnen Kompilationsschritte verwendet. Mit einer zunehmenden Zahl an Programmen (“Apps”) wird das doch etwas mühsam. Irgendwann habe ich dann mal eine Makefile-Hierarchie gebastelt (die mittlerweile - für mehrere Platformen - reichlich kompliziert geworden ist). 🗣“Beim nächsten Mal nehm’ ich CMake, versprochen!”

Mathematik

Wenn man “float” Datentypen unterstützt, macht das nur Sinn, wenn man auch eine passende Library - mit trigonometrischen & hyperbolischen Funktionen - anbietet, das “Math” Modul wurde entsprechend erweitert (ich war noch nie so oft bei Wikipedia & Wolfram Researchs Alpha unterwegs …).

Shell: Kommandozeilenparameter & Environment

Es ist naheliegend, nach dem Betriebssystem-Boot automatisch eine Shell auf angeschlossenen BlockDevices zu suchen & ggf. zu starten. Kaum hat man so etwas gebaut, sollen den von dort aus startbaren “Apps” natürlich auch Parameter übergeben werden können. Auch wären “Environment-Variablen” schön …

Das erfordert ein paar Anpassungen in der Shell (Shell.bin) und ein zusätzliches Hilfsmodul “Environment”. Mit diesem kann man ggf. neue Environments erzeugen oder einfach das eigene an nachgestartete “Apps” vererben (also alles wie gehabt).

Woher kommt das ursprüngliche Environment? Die Shell liest eine Datei “.config” aus. Die dort erkannten Variablen werden als String-Array “envp” an nachzustartende Applikationen übergeben (der letzte Eintrag im Array ist “null”).

Kommandozeilenparameter werden von der Shell als “argc” (Anzahl der übergebenen Parameter) und “argv” (Array von Strings der einzelnen Parameter) übermittelt wie folgt:

function int main(int argc, Array argv, Array env) {
  ... 
  return 0;
}

Hinweis: Ja, der Rückgabewert wird jetzt auch ausgewertet, ein Wert ungleich Null gilt als Fehler (nothing new on the western front!).

Funktionszeiger

Irgendwann habe ich Funktionszeiger nachgerüstet, die Möglichkeiten sind einfach zu verführerisch! Jede Variable kann als Funktionszeiger genutzt werden (ohne speziellen Datentyp also). Man weist einfach eine Funktion als Variablenwert zu (ohne “()”), danach kann man die Funktion aufrufen über den Variablennamen (mit angehängten “()”, ggf. auch mit Argumenten).

Spracherweiterungen

Es gibt zusätzlich zur Original-Sprache (Jack) ein switch- & ein for-Statement (inkl. continue & break - die ich dann auch gleich in die while-Schleife übernommen habe …). Details finden sich hier hier.

Farbgrafik

Irgendwann hatte ich den Wunsch, von dem winzigen Schwarz/Weiss-Bildschirm des Emulators wegzukommen (bei Bedarf). Dafür gibt es jetzt ein “Colour Graphics Device” (CGD) und natürlich passend dazu ein System-Modul “ColourGraphicsDevice”.

Die Shell erkennt, wenn ein CGD verfügbar ist und bootet sogar automatisch auf diesen Schirm. Über die Kommandozeile kann man zwischen den Bildschirmen wechseln (scr 0 -> Schwarz/Weiss mit geringer Auflösung, scr 1 -> CGD).

Sofern man den Emulator mit der Option “- -BigScreen” startet, wird das CGD sogar auf den ganzen Bildschirm ausgedehnt (mit dann höherer Auflösung).

Hinweis: Wenn der Emulator mit “- -BigScreen” aber ohne “- -CGD” Option gestartet wird, erscheint der hochskalierte Schwarz/Weiss-Bildschirm flächenfüllend.

Hat man einen Farbbildschirm, könnte man auf die Idee kommen, hierfür ein Spiel zu schreiben - sieht einfach besser aus! Dadurch kommt dann der Wunsch nach Sprite-Unterstützung von ganz alleine. Das CGD enthält also auch eine einfache Sprite-Engine (für automatische Spritebewegung & Kollisionserkennung etc.) zur Entlastung der CPU (wie überhaupt diese “intelligente Grafikkarte” per Kommando-Pipeline angesteuert wird).
Das Spiel findet sich als “CGDGame” in den Projekt-Quellen 🤸🏁.

Sound

Kein Spiel ohne Sound! Es gibt also ein Sound-Modul (dessen Implementierung im Emulator ich mehrfach geändert habe zwecks Latenz-Verbesserung) und ein passendes System-Modul “Sound”. Das “CGDGame” zeigt, was so geht …

Optimierungen 2

Wenn man sich den erzeugten Assembler-Code im Detail ansieht, findet man überflüssige Sprünge, doppelte Negierungen und noch einige andere “Macken”. Dies ist der häppchenweisen Code-Erzeugung geschuldet. Zwecks Elimination habe ich einen zusätzlichen Optimizer gebastelt, der den Assembler-Code noch einmal verkürzt (und damit performanter macht).

Auch die VM-Code-Erzeugung konnte verbessert werden.

Argumentkontrolle

Die Anzahl der übergebenen Argumente wird jetzt kontrolliert (da die Sprache keine strenge Typüberwachung kennt - alles ist vom selben Basistyp - werden die Datentypen selbst nicht überwacht).

Interessant: Es stellten sich umgehend einige Fehler in bestehenden OS-Modulen raus ✔.

Wenn man jetzt variable Argumentlisten wieder erlauben will, benötigt man ein entsprechendes Attribut für Funktionen, daher: varargs als Funktionsattribut!

Operator Precedence

Im Original-Kurs gibt es keine Bewertungsreihenfolge für Operatoren (d.h. man musste alles explizit klammern). Relativ spät habe ich noch die sonst übliche Bewertungsreihenfolge im Frontend-Compiler nachgerüstet.

Profiler

Da der Emulator alle Zustände der CPU kennt, ist ein Profiler hier nur eine Fingerübung. Interessanter ist eher der Umgang mit Qt5 (ich habe hierfür einiges über Qt-Stylesheets gelernt 💡!) und das Durchwühlen der zugehörigen Jack-Quellen zwecks Aggregation der Zählerdaten auf den verschiedenen Ebenen.

Optimierungen 3

Interessant ist, was der Profiler zu Tage fördert: Die großen Zeitfresser sind häufig die konditionierten Verzweigungen wie z.Bsp.

if (op1 <comparison> op2) {
  ...
}

Wenn man hierfür besseren VM-Code generieren könnte?

Geht! Ich habe den VM-Code erweitert um entsprechend zusammengefasste Varianten:

if-eq-not-goto <label>
if-lt-not-goto <label>
if-gt-not-goto <label>

Dazu passend habe ich in der HV2-CPU den Opcode JUMP<condition> <label> nachgerüstet. Zusammen mit Register-Indirektem Laden & optionalem Pre-Dekrement kann so ein Code-Shrink von bis zu 15% erreicht werden ✅!

Einige zusätzliche bedingte Zuweisungs-Opcodes ermöglichen eine weitere Verbesserung: SETFLAG & SET<cond>. Die Details zu den HV2 Opcodes finden sich hier.

Instruction Cache Usage Analysis

Bei früheren FPGA-Arbeiten hatte ich durch eigene Beobachtung festgestellt, welchen enormen Impact die Limits des Speicherinterfaces auf die CPU-Performance haben (bedeutet: Cache-Notwendigkeit).

Vor einiger Zeit hatte ich daher die Idee, so etwas wie einen Instruction Cache Pre-Fetch zu erproben (erste Überlegungen finden sich hier … wurden aber im Laufe der Tests mehrfach revidiert!). Warum nicht auf der HV2 Platform? Ja, hier gehen natürlich nur Trockentests mit unterschiedlicher Pipeline-Zahl & Längen. Wenn man damit ein paralleles (zur normalen Instruktionsverarbeitung) Laden simuliert, könnte man zumindest eine potentielle Nutzbarkeit erproben.

Die Resultate bei einer automatischen Erzeugung waren eher durchwachsen … vermutlich deshalb findet man (nach meiner Kenntnis) keine aktuelle Architektur, die so etwas unterstützt. 🤔

Naja, wenigstens zwei Callgraphs (1x Root->Leafs, 1x Leafs->Root) können jetzt als Nebeneffekt ausgegeben werden (könnte z.Bsp. für Code-Coverage-Prüfungen genutzt werden 🤘).

Mouse Support

Mausabfragen sind jetzt möglich.

Exception Handling

Ziemlich spät habe ich ein schachtelbares Exception-Handling Konstrukt integriert (try/catch). Das ist doch sehr viel eleganter …
Eigentlich müsste man jetzt das ganze OS umschreiben auf die neuen Möglichkeiten?!

5. Ein Language Server

Nachdem ich einige Zeit mit einem der “Nand2Tetris Syntax Highlighting” VSC Extensions gearbeitet hatte, kam ich auf die Idee eine eigene Extension für “XJack” zu schreiben. Zunächst erweiterte ich nur das Syntax-Highlighting gemäß den Anforderungen der Sprache, auf Dauer war mir das aber zu wenig.

Ich wollte den Language-Server in Python schreiben, nicht direkt die “native” Umgebung für VSC-Extensions.

Ein wenig Recherche förderte “pygls” zu Tage, ein Framework der “dunklen Seite”, oh je 🎃… aber komplett eingerichtet für’s “Extension-Development” in VSC und mit brauchbarer Dokumentation & Verbreitung.

Wenn man dann was zusammengeschraubt hat, taucht eine Frage auf: Woher kommt der “Content”?

Ich habe dann das Compiler-Frontend um die Verarbeitung von “speziellen” Kommentaren erweitert (/** … */), d.h. sie landen in separaten “*.hlp”-Dateien die der Language-Server auslesen kann.

Kleiner Schönheitsfehler: Man muß erst einmal kompilieren bevor die Informationen zur Verfügung stehen (🗣“nobody is perfect!”).

Grund: Man müsste sonst ständig das Getippte durchgehen & bewerten, da rauscht der Lüfter & schwitzt die CPU! So erfolgt die Erzeugung der kontext-sensitiven Hilfe quasi als Seiteneffekt der Kompilierung - kein zusätzlicher Stress 🧘☯.

6. AMD64 als zusätzliches Target

Irgendwann hatte ich die Idee, das Compiler-Backend (VM -> Assembler) um eine weitere Architektur zu erweitern, nämlich die des Hosts (AMD64 SysV/Linux ABI 🐧). Eigentlich bin ich kein x86-Experte von Haus aus, aber was nicht ist, kann ja noch werden 🎉!

Es zeigt sich, das bei den Architekturen fast nichts zusammenpasst (Stack invertiert, abweichende Stackpointerbehandlung, völlig anderer Function-Calling-Contract). Uff! Na denn, wer keine Arbeit hat, macht sich welche 🏋!

Host OS Anbindung

Der Compiler konstruiert alle Funktionsaufrufe als <Modul>.<Funktion> Symbol. Hier muß also ein Name-Mapping her um z.Bsp. Linux Systemfunktionen ansprechen zu können.

Die Idee: Als Pseudo-Modul Extern einführen und hierfür den “rohen” Funktionsnamen belassen. Nicht so elegant wie ein zusätzliches Attribut aber einfach - also schnell - zu implementieren …

Prä-Prozessor

Nicht alles läßt sich gleich behandeln, da gibt es schon bei der Erweiterung von 32 auf 64 Bit einige Abweichungen. Um hier aber eine Gleichbehandlung zu ermöglichen (z.Bsp. durch “Wrapper”), habe ich im Compiler-Frontend noch einen “Arme-Leute”-Präprozessor eingebaut. Er kennt lediglich folgendes Konstrukt:

#ifdef < HV2 | AMD64 >
  ...
#endif

Damit kann man jetzt je nach Zielarchitektur verschiedene Codeteile aus- bzw. einblenden.

Terminal Support

Zunächst kam der Wunsch auf, das aktuelle (ANSI-)Terminal auch richtig ansteuern zu können. Da denkt man natürlich sofort an “ncurses”, aber wollte ich wirklich so ein Riesending einbinden? Nein, mit “termio” & ein bisschen “Eingabeentpufferung” kommt man auch recht weit 🏁!

Blöd bloß: In der Eile hab’ ich vergessen, das API an die bestehenden Ausgabekanäle anzupassen. Naja, vielleicht später mal …

HV2OS 64-bit Emulation

Wie wäre es jetzt mit einer Bereitstellung der Funktionen des Betriebsystems inkl. der HV2-Devices? Unbedingt! Damit stünden auf einen Schlag alle Devices zur Verfügung und die gleichen Sourcen werden auch im AMD64-Modus ausführbar.

Ich habe also aus dem existierenden hv2e32 Emulator eine abgespeckte 64-Bit Variante hv2e64 gestrickt und die HV2OS-Module angepasst für beide Zielarchitekturen.

7. Was (bleibt zu) tun?

Ich habe einige Vorüberlegungen zu ableitbaren Klassen angestellt, Details finden sich hier.
Die API-Vereinheitlichung steht auch noch an!
Vermutlich noch einige Bugfixes …