Zig
From Sousuke.org
Contents |
Was ist Zig?
Zig ist ein MIPS32 Simulator. Momentan befindet sich Zig in der Entwicklungsphase.
Vorschlag: Durch geeignete Aufteilung in Module wäre es eventuell möglich, nicht nur MIPS32, sondern auch andere "Sprachen" zu unterstützen. Lediglich der Parser und der Compiler müssen zusammenarbeiten, damit man beste Performanz erreicht. Es ist jedoch möglich, eine maschinenunabhängige Schittstelle zwischen Precompiler und Compiler bereitzustellen, sodass auf jeder Maschine ein bestimmtes Minimum an unterstützten Compilerroutinen zur Verfügung gestellt werden. In diesem Fall wird zwar keine optimale Performanz erreicht, aber die Anpassung an eine bestimmte Zielmaschine ist damit um einiges einfacher. Genau genommen ist die die Idee gar nicht neu. Der Java Bytecode lässt sich mit der Ausgabe von einem solchen Precompiler vergleichen. Er ist maschinenunabhängig - und dadurch portabel -, aber genau dadurch werden bestimmte maschinenspezifische Features nicht ausgenutzt.
Mission
Die Simulation von MIPS-Maschinen soll so effizient wie möglich erfolgen. Um das zu erreichen wird der MIPS Code zuerst in ein Äquivalent umgewandelt, der dann auf der Zielmaschine direkt von der CPU ausgeführt wird. Die Kommunikation mit dem Benutzer erfolgt dabei durch Aufrufen bestimmter Funktionen, die vom Simulator bereitgestellt werden und in das kompilierte Programm eingebaut werden. Der Simulator SPIM spielt bei der Entwicklung eine große Rolle, indem er uns immer wieder motiviert, an dem Projekt weiter zu arbeiten.
Hinweis: der folgende Abschnitt behandelt den Aufbau von dem Compiler, NICHT den Simulator!
Ereignis-gesteuerter Prozess
Die Grundlage der Kommunikation zwischen den Modulen stellen die Ereignisse (events) dar, die über einen gemeinsamen Medium (bus) an alle verfügbaren Einheiten (modules) geleitet werden. Ein Ereignis kann zusätzliche Daten beinhalten, die von Modulen verarbeitet werden können. Alle Module registrieren alle auftretenden Ereignisse und können (müssen aber nicht) ihren inneren Zustand beim Eintreffen eines passenden Ereignesses ändern. Die Reaktion auf Ereignisse hängt von dem Aufbau des Moduls ab. Ein Modul kann Ereignisse erzeugen. Die Funktionsweise eines Moduls wird durch die Spezifikation von Ereignissen, auf die das Modul reagieren kann und die Spezifikation von Ereignissen, die ein Modul erzeugen kann bestimmt. Die erzeugten Eregnisse hängen von dem Zustand des Moduls ab, der durch definierte Ereignisfolgen eingestellt werden kann. Jedes Modul ist "unabhängig". Es braucht zur Verarbeitung keine Existenz eines anderen Moduls. (aber das notwendige Auftreten von Ereignissen, um das Modul zu steuern) Insofern handelt es sich um eine "Black-Box", die mit dem System nur durch das Austauschen von Eregnissen kommuniziert.
Die Verwendung von Blackboxes bietet den Vorteil, dass sie die Details der Implementierung verbirgt. Dadurch muss sich der Programmierer nur um die Beschreibung des zu lösenden Problems kümmern und nicht darum, WIE das Problem gelöst werden soll. Diese Idee stellte die Motivation für die Entwicklung von objektorientieren Programmierung dar. In unserem System gehen wir einen Schritt weiter und nehmen dem Programmierer die Entscheidung ab, welche Module sich mit der Problemlösung befassen sollen. Durch dynamische Anbindung von Modulen an den Bus bzw. Versetzung einzelner Module in den aktiven oder schlafenden Modus können die Ereignisse von den Modulen verarbeitet werden, die für diese Aufgabe am besten geeignet sind. Die Steuerung dieser Einheiten können wiederum andere Module (master) übernehmen.
Noch mal zusammengefasst: Ereignisse sind abstrakt. Sie stellen die Basis der Kommunikation dar. Alles basiert auf Reaktion und Erzeugung von Ereignissen. Sie können komplex oder primitiv sein. Die Möglichkeit, neue beliebige Ereignisse zu erschaffen oder miteinander zu kombinieren erlaubt uns, eine alternative "Sprache" zur Beschreibung und Lösung des Problem zu erschaffen. Diese erfüllt einige Kriterien, die man von einer guten Sprache erwartet: sie ist einfach (es gibt nur eine Menge von Ereignissen), maschinenunabhängig, und das Beste ist: sie ist erweiterbar in der natürlichen Weise, was sie zu einer sehr mächtigen Sprache machen kann.
Flexibilität
Die dynamische Anbindung von Modulen an den Bus erlaubt einfaches Austauschen, Update, Erweiterung von Systemkomponenten. Außerdem können einzelne Module auch verteilt realisiert werden, was die vereinfachte Parallelisierung von Rechenprozessen erlaubt.
Erweiterbarkeit
Ein saueberer Entwurf bietet die Grundlage für eine einfache und schnelle Implementierung. Leider können zukünftige Änderungen nur teilweise berücksichtigt werden, sodass ein vollkomener Entwurf ausgeschlossen ist. Trotzdem kann man sich Mechanismen überlegen, die die Erweiterung des Systems vereinfachen.
In unserem System gestaltet sich die Erweiterung als besonders einfach, weil lediglich neue Module hinzugefügt werden und nur minimale Änderungen an den bereits bestehenden Modulen vorgenommen werden müssen. Das lässt sich auch damit erklären, dass die Module nur auf bestimmte Ereignisse reagieren und somit von anderen Modulen und Ereignissen völlig unbeeinflusst bleiben.
Hinweis
Die Ideen von "Event driven programming" sind seit einiger Zeit bekannt. Ich habe allerdings nicht viel gefunden, wo die Anwendung dieses Prinzips auf das komplette System übertragen worden ist. Nur teilweise wird das angewendet und es wird fast nicht abstrahiert. Beispiele sind z.B. die Programmierung von GUIs oder anderen Benutzerschnittstellen, die Steuerung von Geräten oder Prozessoren, die auf bestimmte Interrupts reagieren.
Zielmaschinen
Zur Zeit werden nur x86-Zielmaschinen unterstützt.
Datenstrukturen
Hier werden die wichtigsten Datenstrukturen deklariert.
Aufbau
Am Anfang war der Code. Und der Code war ein MIPS ASM Code. Dieser Code wurde von dem Compiler in einen x86-Code übersetzt. Dann kam der Linker und vereinte den übersetzten ASM Code mit der Simulator-bibliothek und es enstand eine Executable.
Zig besteht also aus einen Compiler, einer Bibliothek und einem Linker. (ok, ok... das Linken übernimmt zur Zeit gcc)
Simulator
Es werden globale Variablen zur Verfügung gestellt und Speicherbereiche reserviert. Drei Speicherbereiche müssen alloziert werden: Code Segment, Data Segment und Stack Segment. Außerdem muss eine ATT (Address Translation Table) zur Verfügung gestellt werden. Also müssen folgene globale Daten reserviert werden:
- Code Segment, ein Speicherbereich mit dem Code, das von der CPU ausgeführt wird (ab Adresse 0x40000)
- Code Start Address, Code Segment Size
- Data Segment, ein Speicherbereich mit den Daten, die vom Programm benutzt werden (ab Adresse 0x100000)
- Data Start Address, Data Segment Size
- Stack Segment, ein Speicherbereicht mit dem Stack (ab Addresse 0x800000-STACK_SIZE)
- Stack Start Address, Stack Segment Size
- Register File, beinhaltet 32 Register $0 bis $31
- Program Counter, wird beim Debuggen benötigt
- HI und LO Register, zur Durchführung von arithmetischen Operationen
- Next Code Breakpoint, die Addresse des nächsten Breakpoints in dem Code Segment
- Data Breakpoint List, eine Liste mit sortierten Breakpoint Adressen
- Data Breakpoint List Length
- Address Translation Table, eine Tabelle zur Übersetzung von MIPS Adressen in reele Adressen
Module (etwas veraltet)
Um die Implementierung zu vereinfachen, wird der Compiler in Module aufgeteilt. Jeder Modul erfüllt eine bestimmt Aufgabe.
Parser
Die Aufgabe des Parsers ist es, Dateien mit Assembler Code in Tokens zu zerlegen und diese an den Precompiler weiterzureichen. Der Syntax wird überpfüft und Labeladressen, sowie einige Informationen werden hier zusammengefasst, wie Zeilennummern im Quellcode.
Precompiler
Der Precompiler übernimmt die Auswertung von Tokens und steuert den Compiler. Hier wird entschieden, welche Stufen eingebaut werden, die ATT wird angepasst und der Ablauf des Programms festgelegt.
Compiler
Der Compiler wandelt die Kommandos in ausführbare Maschinenbefehle um, die er dann in eine Objektdatei reinschreibt.
Address Translation Table
Da x86-Befehle keine einheitliche Struktur, insbesondere unterschiedliche Längen aufweisen, entstehen dadurch Komplikationen, die bei der Simulation berücksichtigt werden müssen. So wird die Zieladresse bei einem Jump oder Call zuerst mit Hilfe der ATT transformiert. Die meisten Sprungaddressen können zur Kompilierungszeit berechnet werden, aber falls die Addresse zur Laufzeit bestimmt werden soll, wie z.B. bei jr-Befehlen, so muss diese Tabelle auch zur Laufzeit zur Verfügung stehen. Die Address Translation Table ordnet jeder MIPS Adresse innerhalb des Codesegments genau einen reelen Offset zu. Außerdem wird jeder Adresse die Adresse des nächsten Breakpoints und die Zeilennummer des Quelltextes zugeordenet.
Simulationsstufen
Timeout Check:
dec COUNTER jz TIMEOUT_HANDLER
Die Simulation eines Befehls erfolgt in mehreren Stufen. Man unterscheidet zwischen globalen und lokalen Stufen, sowie zwischen essentiellen und optionalen Stufen. Globale Stufen werden bei allen Befehlen auf die gleiche Weise ausgeführt. Lokale Stufen unterscheiden sich von Befehl zu Befehl. Essentielle Stufen werden immer ausgeführt und optionale Stufen können, müssen aber nicht ausgeführt werden. Diese Einteilung ermöglicht eine äußerst flexible Impementierung von Zig. So können globale Stufen auf gleiche Weise kompiliert werden, das den Aufwand für den Compiler senkt. Außerdem hat der Benutzer die Möglichkeit, optionale Stufen auszuschalten, um das Kompilierte Programm an seine Bedürfnisse anzupassen. Es folgt eine Auflistung aller Stufen. Diese ist aber noch nicht vollständig und gilt nur als ein Vorschlag. Alle Erweiterungen und Ideen sind natürlich willkommen.
Hinweis: Die angegebenen Stufen können in kleinere Unterteilt werden, wenn es Sinn macht. Die folgenden Stufen werden in der Reihenfolge aufgelistet, in der sie auch ausgeführt werden.
Address Calculation
ADDRCALC ist eine globale essentielle Stufe. Hier werden die Datenddressen für die Load/Store-Befehle berechnet. Eigentlich wird hier die Adresse nicht "berechnet", sondern nur an die Zielmaschine angepasst. x86-Prozessoren unterstützen viele Adressierungsmodi, sodass die Berechnung von Hardware durchgeführt werden kann. Manchmal ist es aber notwendig, die Adresse auf Gültigkeit zu überprüfen. In diesem Fall wird die Adresse wirklich "berechnet" und erst nachdem die Adresse überprüft wird findet der Zugriff statt.
Address Checking
ADDRCHECK ist eine globale optionale Stufe. Um Abstürze zu vermeiden, können Speicheradressen auf Gültigkeit überprüft werden. So wird sichergestellt, dass der Speicherzugriff problemlos erfolgen kann. Ist die Adresse nicht in Ordnung, so wird der Simulator aufgerufen.
Data Breakpoint
DATABREAK ist eine globale optionale Stufe. Ähnlich dem code-segment-breakpoint kann auch ein Breakpoint ausgelöst werden, wenn auf bestimmte Speicherstellen zugegriffen wird. Dies lässt sich aber bezüglich der Effizient nicht so einfach realisieren, wie der code-segment-breakpoint, da die Speicherzugriffe nicht notwendigerweise sequentiell erfolgen. Stattdessen muss eine Liste implementiert werden, die durchsucht wird und, falls nötig, der Simulator aufgerufen.
Execution
EXEC ist eine lokale essentielle Stufe. Hier wird der Befehl ausgeführt, Registerfile aktualisiert und die Daten in den Speicher geschrieben.
Register Update
REGUPDATE ist eine lokale essentielle Stufe. Hier wird das Ergebnis einer Operation ins Registerfile gespeichert.
Program Counter Update
PCUPDATE ist eine lokale optionale Stufe. Um die Verwaltung von program-counter einfacher zu gestalten, wird er einfach jedes Mal aktualisiert. Das vereinfacht die Berechnung der Zieladresse bei Jumps und Calls, kostet aber etwas mehr Aufwand.
Program Counter Checking
PCCHECK ist eine globale optionale Stufe. Um zu vermeiden, dass an eine Stelle gesprungen wird, die gar nicht existiert, wird die Zieladresse überprüft. Dies muss nicht immer passieren, sondern nur in den Fällen, bei denen die Zieladresse zur Laufzeit bestimmt wird (z.B. bei jr-Befehlen).
Code Breakpoint
CODEBREAK ist eine globale optionale Stufe. Der Simulator verwaltet die Breakpoints, die auf bestimmte code-segment Adressen gesetzt werden. Dabei wird einfach der program-counter mit der Breakpointaddresse vergliechen und, falls nötig, der Simulator aufgerufen. Die Adresse des nächsten Breakpoints wird immer zur Verfügung gestellt, sodass bei der Überprüfung nur ein Vergleich notwendig ist. Die Aktualisierung von next-breakpoint soll nur im Fall von Jumps oder Calls stattfinden. Dies kann ebenfalls effizient erfolgen, indem zu jeder mips Adresse neben der entsprechenden intel Adresse auch die nächste Breakpointadresse in der address-translation-table gespeichert wird.
Timeout Checking
TIMECHECK ist eine globale optionale Stufe. Endlosschleifen in dem simulierten Programm dürfen den Simulator nicht blockieren. Deshalb soll nach einer endlichen Anzahl von Befehlen der Simulator aufgerufen werden. Um dies zu garantieren, wird bei jeder ausgeführter Instruktion ein timeout-counter dekrementiert. Erreicht dieser den Wert Null, so wird der Simulator aufgerufen. Der timeout-counter kann dann wieder gesetzt und die Ausführung fortgesetzt werden.
Compiler Interface
Der Compiler stellt Routinen zur Verfügung, die maschinenspezifischen Code erzeugen. Um die Performanz zu optimieren, müssen diese Routinen sorgfältig gewählt werden und für jede Zielmaschine einzeln angepasst werden.
Namenskonvention !!! DAS MUSS AUF JEDEN FALL NOCH BESPROCHEN WERDEN !!!
Routinen
FUNC_NAME := <MODUL>[_(<ARCH> | <MODE>)]_<NAME>
Zum Beispiel eine Compilerroutine auf einer x86-Maschine zum Laden des Akkumulators: com_x86_load_reg(reg src);
intel x86
errno com_x86_load_reg(reg src);
Lade die Daten aus dem Register src in den Akkumulator.
errno com_x86_store_reg(reg dst);
Speichere den Inhalt des Akkumulators in den Register dst;
