20. Jul 2017
Lesedauer 17 Min.
Die Selbstbau-CPU programmieren
Eine einfache CPU entwickeln, Teil 3
Von der Hochsprache über den Assembler bis zum Binärcode aus Nullen und Einsen.
Die ersten beiden Teile dieser Serie [1] [2] haben erklärt, wie eine CPU aufgebaut ist und wie man ein einfaches Exemplar selbst programmieren kann und diesem via Instruction Set und Instruction Decoder die ersten Funktionen spendiert. Wie Sie am Ende des zweiten Teils [2] gesehen haben, wird der CPU über Nullen und Einsen im Rahmen von Opcodes mitgeteilt, welche Befehle ausgeführt werden sollen. So schreibt zum Beispiel der Opcode 01000001 den Inhalt des X-Registers in das M-Register.
Der Assembler
Selbstverständlich will niemand die CPU den ganzen Tag lang mit Nullen und Einsen füttern, wenngleich das in den Anfängen der Informatik genau so gemacht wurde. Deshalb wird auch die Selbstbau-CPU nicht direkt über Opcodes und Binärcode programmiert, sondern über sogenannte Mnemonics auf Assembly-Ebene. Der Opcode 01000001 lässt sich zum Beispiel auch als MOV M, X darstellen.
Dabei handelt es sich um einen Assembler-Befehl, welcher Opcode und Binärcode der Ziel-CPU abstrahiert. Assembler-Befehle werden von einem Assembler-Programm in den Binärcode der Ziel-CPU übersetzt.Vor den Assembler kann auch noch eine Hochsprache geschaltet werden, wie etwa C oder C++. Diese müsste dann passenden Assembler-Code generieren. Bild 1 veranschaulicht dieses Abstraktionskonzept.Im Rahmen dieses dritten Teils der CPU-Serie möchte ich Ihnen nun zeigen, wie der Assembler meiner Selbstbau-CPU implementiert ist und wie Sie damit konkrete Programme entwickeln können, ohne dabei mit Nullen und Einsen hantieren zu müssen.Wie bereits in Teil 2 erwähnt, versteht die Selbstbau-CPU auf Maschinenebene RISC-Befehle. Jeder RISC-Befehl steht für eine einzelne Hardware-Operation, die vom Instruction Decoder ausgeführt werden kann.
Auf den RISC-Befehlen aufbauend habe ich ein CISC-basierendes Instruction Set entwickelt, mit dem die CPU mit schon etwas mächtigeren Befehlen programmiert werden kann. Mein CISC Instruction Set ist angelehnt an die Assembler-Sprache für Intels x86-CPUs, da sehr viele Entwickler mit dieser Sprache zumindest ansatzweise vertraut sind. Die Aufgabe des Assemblers besteht darin, die CISC-Befehle in RISC-Befehle zu konvertieren und die generierten RISC-Befehle anschließend in Binärcode umzuwandeln (Bild 2).Jetzt soll es zunächst darum gehen, wie die RISC-Befehle vom Assembler in Binärcode konvertiert werden. Der darauf folgende Abschnitt widmet sich dann den CISC-Befehlen.
RISC Assembly Language
Der komplette Assembler zur Selbstbau-CPU ist in C# implementiert und steht auf GitHub unter der MIT-Lizenz zur Verfügung [3].Für das Parsing der Assembler-Sprache habe ich mich für ANTLR 4.5 entschieden [4], da eine Eigenentwicklung eines Parsers zu komplex gewesen wäre. ANTLR 4.5 ist die einzige Abhängigkeit, die der Assembler zu anderen Komponenten aufweist.
ANTLR bietet über sogenannte g4-Dateien die Möglichkeit, die Syntax einer Programmiersprache zu beschreiben. Bild 3 zeigt einen Ausschnitt der g4-Datei, die die RISC-Befehle des Assemblers beschreibt.Aus dieser g4-Datei generiert ANTLR passende Parser, Lexer und Visitors in C#-Klassen, gegen die man schlussendlich programmieren kann. Ich habe mich für das Generieren von Visitor-Klassen entschieden, da das Implementieren eines passenden Assemblers mithilfe des Visitor-Patterns am einfachsten erschien.
Listing 1: Binärcode zu MOV16 erzeugen
public override Result VisitMOV16(
LowLevelAssemblyParser.MOV16Context context)
{
string destinationRegister =
context.register_16bit(0).GetText();
string sourceRegister =
context.register_16bit(1).GetText();
string opcode = "01";
opcode += GetRegisterOpCode_GeneralPurpose_MOV16(
destinationRegister);
opcode += GetRegisterOpCode_GeneralPurpose_MOV16(
sourceRegister);
opcode += " ; MOV16 " + destinationRegister +
", " + sourceRegister;
assembly.Add(opcode);
return base.VisitMOV16(context);
}
Für jeden RISC-Befehl, den der Assembler verarbeiten muss, habe ich die entsprechende Visitor-Methode überschrieben. Innerhalb der überschriebenen Methode wird dann einfach der für den jeweiligen RISC-Befehl erforderliche Binärcode erzeugt. Listing 1 zeigt das Generieren von Binärcode für den RISC-Befehl MOV16. Wie Sie erkennen können, handelt es sich um ein 1:1-Mapping zwischen RISC-Befehl und dazugehörigem Binärcode. Bei Befehlen wie MOV16 müssen zusätzlich Quell- und Zielregister decodiert werden. Das erledigen entsprechende Hilfsfunktionen.
CISC Assembly Language
Um einiges interessanter ist die CISC Assembly Language, die auf der RISC Assembly Language aufbaut. Die CISC Assembly Language erlaubt das Programmieren der CPU auf der nächsthöheren Abstraktionsebene.Aufgabe des Assemblers ist es, einen CISC-Befehl in mehrere RISC-Befehle zu zerlegen. Dazu muss ein 1:n-Mapping durchgeführt werden. Hier ein konkretes Beispiel eines CISC-Befehls, der zerlegt werden soll:ADD D, E
Dieser Befehl soll den Wert des E-Registers zum aktuellen Wert des D-Registers addieren und das Ergebnis ins D-Register schreiben. Auf CPU-Ebene sind dafür mehrere Einzelschritte auszuführen:
- Setzen des Input A der ALU auf den Wert des Registers D
- Setzen des Input B der ALU auf den Wert des Registers E
- Durchführen der Addition
- Zurückschreiben des Ergebnisses in das Register D
MOV_ALU_IN A, D
MOV_ALU_IN B, E
ADD
MOV_ALU_OUT D
Aufgabe des Assemblers ist es nun, obigen CISC-Code in diese Folge von RISC-Befehlen zu wandeln. Alle unterstützten CISC-Befehle sind wieder in einer g4-Datei beschrieben, siehe Bild 4. Auch für diese Datei erzeugt ANTLR passende Lexer, Parser und Visitor-Klassen, die anschließend zum Generieren von Code verwendet werden. Listing 2 zeigt die Umsetzung des gerade geschilderten Beispiels. Tabelle 1 listet die CISC-Befehle auf, die der Assembler der Selbstbau-CPU aktuell unterstützt.
Listing 2: RISC-Code erzeugen
public override Result VisitADD_R8_R8(
HighLevelAssemblyParser.ADD_R8_R8Context context)
{
string sourceRegister =
context.register_8bit(1).GetText();
string destinationRegister =
context.register_8bit(0).GetText();
// Add the assembly opcodes
assembly.Add(";; BEGIN ADD " +
destinationRegister + ", " + sourceRegister +
" (ADD_R8_R8)");
assembly.Add("MOV_ALU_IN A, " +
destinationRegister);
assembly.Add("MOV_ALU_IN B, " + sourceRegister);
assembly.Add("ADD");
assembly.Add("MOV_ALU_OUT " +
destinationRegister);
assembly.Add(";; END ADD " + destinationRegister +
", " + sourceRegister + " (ADD_R8_R8)");
return base.VisitADD_R8_R8(context);
}
Neben dem Erzeugen von RISC-Code auf Basis von CISC-Befehlen hat der Assembler noch andere wichtige Aufgaben:
- Verarbeiten von Include Files.
- Generieren von Hauptspeicheradressen
- Berechnen der Ziel-Hauptspeicheradresse bei Sprüngen (bedingte und unbedingte Sprünge)
- Erzeugen einer C-Datei, über die mithilfe des angeschlossenen Arduino-Boards der Hauptspeicher der CPU mit dem generierten Programmcode initialisiert werden kann
- Erstellen einer Map-Datei, die zeigt, in welchen Hauptspeicheradressen welche Funktionen geladen worden sind (kann für die Visualisierung von Call Stacks verwendet werden)
Addition von 32-Bit-Zahlen
Nachdem Sie nun einen groben Überblick gewonnen haben, wie der Assembler implementiert und wie aus Assembler-Programmen ausführbarer Binärcode erzeugt wird, möchte ich noch einige wichtige Assembler-Programme vorstellen, die meine CPU bereits ausführen kann.Tabelle 1: CISC-Befehle
|
Das erste Beispiel zeigt, wie Sie mit einer 8-Bit-CPU zwei 32-Bit-Zahlen addieren. Vor der gleichen Herausforderung steht zum Beispiel eine 32-Bit-CPU, wenn Sie zwei 64-Bit-Zahlen addieren soll. In Tabelle 1 sehen Sie, dass es für die Addition zwei verschiedene Befehle gibt: ADD und ADC. Die beiden Befehle können gemeinsam verwendet werden, um zwei beliebige n-Bit-Zahlen zu addieren. Die Idee dahinter ist folgende:
- Die ersten acht Bit der beiden Zahlen werden regulär mit dem ADD-Befehl addiert.
- Gibt es bei der ersten Addition einen Überlauf, wird dieser über den Befehl ADC (Add with Carry) zu den beiden nächsten 8-Bit-Zahlen hinzugefügt.
- Tritt bei der Addition der zweiten acht Bit der Zahl ein Überlauf auf, wird auch dieser per ADC-Befehl bei der Addition der nächsten acht Bit berücksichtigt.
Listing 3: 32-Bit-Zahlen addieren
; Initialize the Stack Pointer
; and the Base Pointer
MOV XL, 0xFF
MOV XH, 0xFF
MOV SP, X
MOV XL, 0
MOV XH, 0
MOV BP, X
; Initialize an address register
MOV XL, 0x00
MOV XH, 0xFF
MOV Y, X
; Initialize the D and E register with the 1st byte
MOV D, [Y]
MOV E, [Y + 4]
ADD D, E
PUSHF
; Write register D to the
; Output Port
OUTB D
; Initialize the D and E register with the 2nd byte
MOV D, [Y + 1]
MOV E, [Y + 5]
POPF
ADC D, E
PUSHF
; Write register D to the
; Output Port
OUTB D
; Initialize the D and E register with the 3rd byte
MOV D, [Y + 2]
MOV E, [Y + 6]
POPF
ADC D, E
PUSHF
; Write register D to the
; Output Port
OUTB D
; Initialize the D and E register with the 4th byte
MOV D, [Y + 3]
MOV E, [Y + 7]
POPF
ADC D, E
; Write register D to the
; Output Port
OUTB D
; Stops the CPU execution
HLT
; 1 094 967 296d
DATA 1111111100000000b, 00000000b ; 1st Byte
DATA 1111111100000001b, 11100000b ; 2nd Byte
DATA 1111111100000010b, 01000011b ; 3rd Byte
DATA 1111111100000011b, 01000001b ; 4th Byte
; 3 100 000 000d
DATA 1111111100000100b, 00000000b ; 1st Byte
DATA 1111111100000101b, 00111111b ; 2nd Byte
DATA 1111111100000110b, 11000110b ; 3rd Byte
DATA 1111111100000111b, 10111000b ; 4th Byte
Den gleichen Ansatz nutzen x86/x64-CPUs. Listing 3 zeigt ein Beispiel, in dem die Zahlen 1094967296 und 3100000000 über die Befehle ADD und ADC addiert werden. Hier können Sie den Nachteil einer 8-Bit-CPU gut erkennen: Sobald Sie mehr als acht Bit gemeinsam verarbeiten möchten, müssen Sie die erforderlichen Operationen auf 8-Bit-Arbeitspakete aufteilen, was bedeutet, dass die Operation entsprechend länger dauert. Eine 32-Bit-CPU führt eine solche Addition mit einem einzelnen ADD-Befehl aus.
Indirect Memory Addressing
Wie Sie in Listing 3 gesehen haben, unterstützt der Assembler auch verschiedene Möglichkeiten, um Hauptspeicher zu adressieren. Einerseits können Sie über eckige Klammern eine direkte Hauptspeicheradresse angeben, die in einem Register gespeichert wird:
MOV D, [Y]
In diesem Fall würde der 8-Bit-Wert aus dem Hauptspeicher (die Adresse steht im Register Y) in das Register D geladen. Man spricht hier von Direct Addressing.Wie Sie mit indirekten Speicheradressen arbeiten, zeigt dieser Befehl:
MOV D, [Y + 1]
In diesem Fall muss die Selbstbau-CPU die korrekte Hauptspeicheradresse erst ausrechnen (Y+1), um den dort hinterlegten Wert ins Register D zu schreiben. Also wird im resultierenden Low-Level Assembly Code die aktuelle Adresse des Registers Y um 1 erhöht und so die effektive Hauptspeicheradresse ermittelt.Damit das klappt, muss die CPU gut mit 16-Bit-Hauptspeicheradressen rechnen können. Dazu gibt es in der Selbstbau-CPU eine Komponente namens 16BIT_ADDER. Das ist ein 16 Bit breiter Ripple Carry Adder, der Hauptspeicheradressen berechnen kann. Schreiben Sie zum Beispiel auf CISC-Assembly-Ebene ein MOV D, [Y + 1], erzeugt der Assembler folgenden RISC-Code:
SET A, "0000"
SET B, "0000"
MOV8
MOV_ALU_OUT XH
SET A, "0001"
SET B, "0000"
MOV8
MOV_ALU_OUT XL
MOV16 J, X
MOV16 X, Y
16BIT_ADDER
MOV16 M, X
LOAD D
Hier wird im Register J der zu addierende Wert gespeichert (in diesem Fall der Binärwert 00000001) und im Register X der Ausgangswert (in diesem Fall der Wert des Registers Y). Anschließend wird das Ergebnis der Addition in das M-Register geschrieben und über den LOAD-Befehl der eigentliche Hauptspeicherzugriff durchgeführt.
Tabelle 2: Status-Flags
|
Verzweigungen
Wenn Sie sich den bisher abgedruckten Assembly-Code ansehen, fällt auf, dass immer nur linearer Code ausgeführt wurde. Verzweigungen kamen bislang nicht vor. Komplette Programme kommen allerdings kaum ohne Verzweigungen aus. Deshalb bietet jede CPU sowohl bedingte als auch unbedingte Sprünge an. Der Unterschied: Ein unbedingter Sprung wird immer durchgeführt. Ein bedingter Sprung wird nur ausgeführt, wenn ein Status-Flag gesetzt ist. Die Selbstbau-CPU implementiert für bedingte Sprünge das Flags-Register, das die vier in Tabelle 2 aufgeführten Status-Flags als Bit-Werte speichert.Die Status-Flags werden von der ALU berechnet und im Flags-Register gespeichert, sobald das Ergebnis der ALU-Operation zurückgeliefert wird. Abhängig vom Flags-Register können bedingte Sprünge im aktuellen Ausbaustand der CPU über die folgenden Assembler-Befehle durchgeführt werden: JNC, JNS, JNZ und JZ.Mit bedingten Sprüngen lassen sich nun sämtliche Kontrolllogiken abbilden, die Sie von höheren Programmiersprachen gewohnt sind: If Then/Else, For, While, Do/While, Switch/Case.Listing 4: Bedingte Sprünge
; The result is stored in
; register F
MOV E, 0
; Initial value
MOV D, 9
; Add the current value of
; register D to the result in
; register F
:LOOP
ADD E, D
; Decrement the value by one
DEC D
; Conditional Jump if the Zero-
; Flag from the ALU is not 1
JNZ :LOOP
; Write register F to the
; Output Port
; OUTB E
; Stops the CPU execution
; HLT
Listing 4 zeigt, wie Sie über eine einfache Schleife und den bedingten Sprungbefehl JNZ die Summe der Zahlen 1 bis 9 berechnen können.
Der Stack
Der Stack – unendliche Weiten. Wir schreiben nun endlich Funktionen! Der Stack ist eines der wichtigsten Konzepte auf Programmier- und CPU-Ebene. Der Stack selbst ist nur eine klar definierte Hauptspeicherregion, in der Daten in einer organisierten Art und Weise abgelegt und wieder ausgelesen werden. Auf dem Stack können Sie zwei elementare Operationen durchführen:- Über den Befehl PUSH wird ein Wert auf dem Stack abgelegt.
- Über den Befehl POP wird der Wert wieder vom Stack gelesen.
- Der aktuelle Wert des Stack Pointers wird um 1 verringert.
- Der Wert des angegebenen Registers wird auf den Stack geschrieben.
- Der aktuelle Wert des Stacks wird in das angegebene Register geschrieben.
- Der aktuelle Wert des Stack Pointers wird um 1 erhöht.
Dieses Stack-Design wurde vor Urzeiten gewählt, damit der Heap (auf dem dynamische Hauptspeicher-Allokierungen vorgenommen werden) und der Stack sauber voneinander getrennt sind. Dies ist insbesondere dann sehr wichtig, wenn Sie nur einen beschränkten Adressraum zur Verfügung haben – wie im Fall der Selbstbau-CPU mit 64 KByte Arbeitsspeicher. Bild 5 veranschaulicht dieses Konzept.
Listing 5: Der Stack
; Initialize the Stack Pointer
MOV XL, 0xFF
MOV XH, 0xFF
MOV SP, X
MOV D, 00001111b
PUSH D
POP E
Damit die Stack-Pointer-Arithmetik über die Befehle PUSH und POP richtig arbeiten kann, muss der Stack Pointer beim Start der CPU initialisiert werden. Listing 5 zeigt, wie Sie den Stack Pointer initialisieren und einen einfachen Register-Transfer über den Stack abbilden können. Im Listing wird der Stack Pointer auf den Wert 0xFFFF initialisiert, das heißt, er liegt ganz am Ende des 64K-Adressraums. Im ersten Schritt wird der Binärwert 00001111 in das Register D geladen. Im nächsten Schritt wird über den Befehl PUSH D der Stack Pointer um 1 reduziert, das heißt, dass dieser nun den Wert 0xFFFE hat. Und auf diese Hauptspeicheradresse wird der Wert des Registers D geschrieben – nämlich 00001111.
Listing 6: PUSH-Implementierung mit RISC-Befehlen
SET A, "1111"
SET B, "1111"
MOV8
MOV_ALU_OUT XL
SET A, "1111"
SET B, "1111"
MOV8
MOV_ALU_OUT XH
MOV16 SP, X
SET A, "1111"
SET B, "0000"
MOV8
MOV_ALU_OUT D
SAVE_FLAGS
SET A, "1111"
SET B, "1111"
MOV8
MOV_ALU_OUT XL
SET A, "1111"
SET B, "1111"
MOV8
MOV_ALU_OUT XH
MOV16 J, X
MOV16 X, SP
16BIT_ADDER
MOV16 SP, X
MOV16 M, SP
STORE D
RESTORE_FLAGS
SAVE_FLAGS
MOV16 M, SP
LOAD E
SET A, "0001"
SET B, "0000"
MOV8
MOV_ALU_OUT XL
SET A, "0000"
SET B, "0000"
MOV8
MOV_ALU_OUT XH
MOV16 J, X
MOV16 X, SP
16BIT_ADDER
MOV16 SP, X
RESTORE_FLAGS
Mit der Ausführung des Befehls POP E wird nun der Wert, auf den der aktuelle Stack Pointer zeigt, vom Hauptspeicher in das Register E geladen. Das heißt, dass nun das Register E den Wert 00001111 enthält. Schlussendlich wird noch der Stack Pointer um 1 erhöht, sodass dieser wieder den Wert 0xFFFF hat. All diese Operationen werden wieder über viele einzelne RISC-Operationen auf CPU-Ebene abgebildet. Listing 6 zeigt den RISC-Code zum PUSH-Befehl.Wie Sie sehen, wird die Komponente 16BIT_ADDER verwendet, um den Wert des Stack Pointers zu dekrementieren beziehungsweise zu inkrementieren – Wiederverwendung ist doch was Schönes!
Listing 7: PUSHF & POPF
; Initialize the Stack Pointer
MOV XL, 0xFF
MOV XH, 0xFF
MOV SP, X
; Sets the Zero Flag to 1
MOV D, 1
MOV E, 1
SUB D, E
; Store the Flags onto the Stack
PUSHF
; Load the Flags from the Stack
; into the G Register
POP G
Zusätzlich besteht über das Befehlspaar PUSHF und POPF die Möglichkeit, den aktuellen Inhalt des Flags-Registers auf den Stack zu schreiben (über PUSHF) beziehungsweise über POPF vom Stack in ein General Purpose Register zurückzuschreiben. Schreibend wird immer nur über eine ALU-Operation auf das Flags-Register zugegriffen. Listing 7 zeigt ein einfaches Beispiel.
Funktionsaufrufe
Und nun geht es ans Eingemachte: Funktionsaufrufe auf Assembly-Ebene! Nachdem ein Stack implementiert ist, steht auch die notwendige Basis für Funktionsaufrufe. Dadurch sind Sie auf Assembly-Ebene in der Lage, Funktionen zu schreiben, die Sie zwecks Wiederverwendbarkeit an einer beliebigen anderen Stelle aufrufen können. Listing 8 zeigt ein Assembly-Programm, das einen einfachen Funktionsaufruf durchführt.Listing 8: Ein einfacher Funktionsaufruf
; Initialize the Stack Pointer
MOV XL, 0xFF
MOV XH, 0xFF
MOV SP, X
MOV F, 11110000b
; Call a subroutine...
CALL :SUBROUTINE
MOV F, 10101010b
; Stops program execution
HLT
:SUBROUTINE
MOV F, 01010101b
RET
Wie Sie anhand des Assembler-Codes erkennen können, wird die Funktion SUBROUTINE aufgerufen, die den Wert des Registers F verändert, und anschließend wird über den Befehl RET wieder zum aufrufenden Code zurückverzweigt.Das sieht jetzt freilich nach elegantem Assembly-Code auf CISC-Ebene aus. Auf RISC-Ebene müssen dafür jedoch eine Vielzahl unterschiedlicher Problematiken gelöst werden:
- Wie werden Parameter-Werte an eine Funktion übergeben?
- Wie werden Ergebniswerte einer Funktion zurückgeliefert?
- Woher weiß der RET-Befehl, an welche Programmstelle er zurückverzweigen soll?
- Wohin werden die lokalen Variablen einer Funktion gespeichert?
- Parameterwerte,
- die Rücksprungadresse sowie
- lokale Variablen.
PUSH 10 ; Number of characters
PUSH 0x00 ; 16-bit memory address – Low Byte
PUSH 0xFA ; 16-bit memory address – High Byte
CALL :_ATOI
In diesem Fall befindet sich der zu konvertierende String an der Hauptspeicheradresse 0xFA00 und das Register D enthält die Anzahl der zu konvertierenden Zeichen. Bild 6 zeigt den Stack Frame dazu.
Der eigentliche Funktionsaufruf wird über den Befehl CALL durchgeführt. Dieser berechnet die Rücksprungadresse – das ist die Hauptspeicheradresse direkt nach dem CALL-Befehl – und schreibt diese ebenfalls auf den Stack. Hier müssen jedoch wieder zwei 8-Bit-Werte auf den Stack geschrieben werden, weil eine Hauptspeicheradresse 16 Bit lang ist. In Bild 7 sehen Sie den vollständigen Stack Frame.
Nun wird zur Funktion verzweigt, indem ein unbedingter Sprung zur Hauptspeicheradresse durchgeführt wird, an der die Funktion abgelegt ist (der Assembler weiß, an welcher Hauptspeicheradresse die Funktion abgelegt wird, da der Assembler auch für das Generieren der Hauptspeicheradressen zuständig ist). Diese Hauptspeicheradresse wird im Assembler-Code über einen sogenanntes Label identifiziert – eingeleitet durch einen Doppelpunkt (etwa :SUBROUTINE). Nun sind wir in der Implementierung der Funktion selbst angekommen. Jede Funktion besteht immer aus drei Teilen:
- Prolog (Einleitung)
- Implementierung (Hauptteil)
- Epilog (Schluss)
- Der aktuelle Base Pointer wird auf dem Stack gesichert.
- Der aktuelle Stack Pointer wird im Base Pointer gespeichert (der alte Base Pointer wurde bereits im vorigen Schritt auf dem Stack zwischengespeichert und kann damit überschrieben werden).
- Der Stack Pointer wird abhängig von dem von den lokalen Variablen benötigten Speicherplatz minimiert. Dadurch wird auf dem Stack Platz für lokale Variablen geschaffen.
PUSH BP
MOV BP, SP
SUB SP, 3
In Bild 8 sehen Sie den Stack Frame, nachdem der Prolog ausgeführt wurde. Wie Sie in der Abbildung erkennen können, wurden am Ende des Stacks (grafisch gesehen oben) drei Byte für lokale Variablen reserviert, die in obigem Listing vom aktuellen Stack Pointer abgezogen wurden. Anhand dieser Grafik lässt sich zudem erkennen, wie mithilfe des Base Pointers auf Übergabeparameter und lokale Variablen zugegriffen werden kann.
Wenn Sie einen positiven Offset beim Base Pointer angeben, referenzieren Sie einen Übergabeparameter; geben Sie einen negativen Offset an, wird eine lokale Variable referenziert. Und genau aus diesem Grund wurde vorher im Rahmen des Prologs der Base Pointer initialisiert: Er bietet eine stabile, nicht veränderbare Referenz auf dem Stack.Freilich könnten Sie – rein theoretisch – auch ohne einen Base Pointer auf die Übergabewerte und die lokalen Variablen zugreifen, indem Sie sich stets direkt auf den aktuellen Stack Pointer beziehen. Allerdings wäre der in diesem Fall erforderliche Code erheblich komplexer, da sich der Stack Pointer mit jeder Zeile Code verändern kann (durch ein PUSH oder POP) und Sie die Änderungen permanent mitprotokollieren müssten.Dieses Konzept nennt sich Frame Pointer Omission (FPO) und wird zum Beispiel auf x64-Architekturen durchgeführt. Dadurch steht das BP-Register als weiteres General Purpose Register zur Verfügung, das der Compiler auch für andere Zwecke verwenden kann.Nun, wie gesagt arbeitet der Assembler zur Selbstbau-CPU mit Base Pointer, der im Rahmen des Prologs initialisiert wird. Danach können Sie per indirekter Adressierung sehr leicht auf Übergabeparameter und lokale Variablen innerhalb der Funktion zugreifen. Hier ein einfaches Beispiel dazu:
MOV D, [BP + 5] ; 2. Parameter
MOV E, [BP + 4] ; 1. Paramter
ADD D, E
; Schreiben einer lokalen
; Variablen
MOV [BP - 1], D
Das Funktionsergebnis kann über den Stack an den Aufrufer zurückgeliefert oder in einem spezifischen Register abgelegt werden. Dies ist abhängig von der gewählten Calling Convention. In meinem Fall liefere ich das Ergebnis – sofern es sich um einen 8-Bit-Wert handelt – immer im Register D zurück.Nachdem die eigentliche Implementierung der Funktion abgearbeitet wurde, wird noch der Epilog ausgeführt, der den Stack Frame der aktuellen Funktion verwirft. Sehen Sie sich dazu den folgenden Assembly-Code näher an. Der Epilog kann wieder über den CISC-Befehl LEAVE automatisch generiert werden.
MOV SP, BP
POP BP
RET
Im Rahmen des Epilogs werden die drei folgenden Aufgaben erledigt:
- Herstellen des alten Stack Pointers (MOV SP, BP)
- Herstellen des alten Base Pointers (POP BP)
- Unbedingter Sprung zurück zum Aufrufer (RET)
Wie Sie im Bild jetzt sehr schön erkennen können, sind die Übergabeparameter des Funktionsaufrufes noch immer auf dem Stack gespeichert. Daher muss der Code, welcher zuvor den Funktionsaufruf durchgeführt hat, jetzt noch die Übergabeparameter vom Stack entfernen:
ADD SP, 3
Dazu werden einfach drei Byte zum Stack Pointer hinzugezählt und der Stack Pointer steht wieder genau dort, wo er vor dem Funktionsaufruf war. Cool, oder?Wie Sie anhand dieses Abschnitts gesehen haben, handelt es sich beim Stack um ein wirklich leistungsfähiges Konzept, durch das Funktionsaufrufe erst möglich werden. Das Schöne daran ist auch, dass es für jeden Funktionsaufruf einen eigenen Stack Frame gibt. Sie können daher innerhalb einer Funktion ohne Probleme eine weitere Funktion aufrufen – es wird einfach ein neuer Stack Frame erzeugt, genau nach dem gleichen Muster wie vorher.
Listing 9: Rekursive Funktionsaufrufe
; Initialize the Stack Pointer
MOV XL, 0xFF
MOV XH, 0xFF
MOV SP, X
MOV F, 1
MOV G, 00010000b
; Call a subroutine...
CALL :SUBROUTINE
; Do something else after the
; recursive function call...
INC G
; Write register G to the
; Output Port
OUTB G
; Stops program execution
HLT
:SUBROUTINE
INC F
CMP F, G
JZ :SUBROUTINE_RETURN
; Recursive call...
CALL :SUBROUTINE
:SUBROUTINE_RETURN
RET
Mit diesem Ansatz sind sogar rekursive Funktionen möglich, da jeder rekursive Funktionsaufruf auch seine eigenen lokalen Variablen innerhalb seines eigenen Stack Frames speichert. Listing 9 zeigt einen einfachen rekursiven Funktionsaufruf.Eine weitere wichtige Funktion, die Stack Frames erfüllen, ist das Generieren eines Call Stacks, den Ihnen jeder Debugger zurückliefern kann. Ein Call Stack zeigt ganz genau auf, welche Funktion welche Funktion aufgerufen hat und wie die einzelnen Übergabeparameter und lokalen Variablen ausgesehen haben. Diese Informationen werden aus den einzelnen Stack Frames ermittelt.Wie Sie beim Prolog gesehen haben, wird immer der alte Base Pointer auf den Stack gepusht. Und der aktuelle Base Pointer zeigt genau auf diese Adresse auf dem Stack. Daher zeigt der aktuelle Base Pointer immer genau auf die Hauptspeicheradresse, an welcher der Base Pointer der vorherigen Funktion auf dem Stack abgelegt ist.
Dadurch entsteht eine einfach verkettete Liste, mit deren Hilfe Sie sich durch die verschiedenen Stack Frames bewegen und einen vollständigen Call Stack ermitteln können.
Bild 10 veranschaulicht dieses Konzept.
Bild 10 veranschaulicht dieses Konzept.
Listing 10: Call-Stack-Analyse
:_STACKBACKTRACE
ENTER 0
MOV H, 0
; Initialize the registers with
; the current BP
MOV X, BP
MOV D, XH
MOV E, XL
:BP_NOT_NULL
; Load the memory content of the
; current BP (pointer to
; the previous stack frame) into
; the registers
MOV XH, D
MOV XL, E
MOV Y, X
; Load the BP of the previous
; stack frame into the registers
MOV D, [Y]
MOV E, [Y + 1]
; Write out the higher byte of
; the return address
MOV XL, [Y + 2]
OUTB XL
; Write out the lower byte of
; the return address
MOV XL, [Y + 3]
OUTB XL
; Check if the lower byte of the
; BP is NULL.
; We should also check here the
; higher byte of the BP if it
; is NULL...
CMP E, H
; We haven‘t yet reached the 1st
; stack frame, therefore we
; walk again down the stack
JNZ :BP_NOT_NULL
LEAVE
RET
Der Assembler-Code in Listing 10 zeigt eine einfache Implementierung, wie der Call Stack von verschachtelten Funktionsaufrufen über die Stack Frames analysiert werden kann. Dazu werden einfach die entsprechenden Rücksprungadressen über den OUTB-Befehl an einen der Output-Ports der CPU geschrieben.
Fazit
Im Rahmen dieses Artikels haben Sie gesehen, wie Sie bereits mit einfachen Befehlen wirkungsvolle Programme für die Selbstbau-CPU schreiben können. Einerseits haben Sie in groben Zügen erfahren, wie Sie einen einfachen Assembler implementieren können, und auf der anderen Seite habe ich Ihnen die von mir für die Selbstbau-CPU implementierte Assembler-Sprache vorgestellt.Ich hoffe, dass ich Ihnen mit dieser dreiteiligen Artikelserie Appetit auf die Interna einer CPU gemacht habe und Sie nun ein besseres Verständnis dafür haben, was auf Bit-Ebene so alles passiert, wenn die CPU Assembler-Befehle ausführt. In diesem Sinne: PRINT("Good Bye").Fussnoten
- Klaus Aschenbrenner, Eine einfache CPU entwickeln, Teil 1, Die CPU? Bau ich selber!, dotnetpro 6/2017, Seite 122 ff.,
- Klaus Aschenbrenner, Eine einfache CPU entwickeln, Teil 2, Architektur der Selbstbau-CPU, dotnetpro 7/2017, Seite 126 ff.,
- Der Assembler zur Selbstbau-CPU auf GitHub, https://github.com/KPU-RISC/KPU
- Objektorientierter Parsergenerator ANTLR, https://www.antlr.org/
