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
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">override</span> Result <span class="hljs-title">VisitMOV16</span>(</span><br/><span class="hljs-function"><span class="hljs-params"> LowLevelAssemblyParser.MOV16Context context</span>) </span><br/>{ <br/> <span class="hljs-keyword">string</span> destinationRegister = <br/> context.register_16bit(<span class="hljs-number">0</span>).GetText(); <br/> <span class="hljs-keyword">string</span> sourceRegister = <br/> context.register_16bit(<span class="hljs-number">1</span>).GetText(); <br/> <br/> <span class="hljs-keyword">string</span> opcode = <span class="hljs-string">"01"</span>; <br/> opcode += GetRegisterOpCode_GeneralPurpose_MOV16(<br/> destinationRegister); <br/> opcode += GetRegisterOpCode_GeneralPurpose_MOV16(<br/> sourceRegister); <br/> opcode += <span class="hljs-string">" ; MOV16 "</span> + destinationRegister + <br/> <span class="hljs-string">", "</span> + sourceRegister; <br/> assembly.Add(opcode); <br/> <br/> <span class="hljs-keyword">return</span> <span class="hljs-keyword">base</span>.VisitMOV16(context); <br/>}
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:<span class="hljs-keyword">ADD</span><span class="bash"> D, E </span>
<span class="bash"> </span>
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
<span class="hljs-keyword">MOV_ALU_IN </span>A, D
<span class="hljs-keyword">MOV_ALU_IN </span><span class="hljs-keyword">B, </span>E
<span class="hljs-keyword">ADD </span>
<span class="hljs-keyword">MOV_ALU_OUT </span>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(<br/> HighLevelAssemblyParser.ADD_R8_R8Context context) <br/>{ <br/> string sourceRegister = <br/> context.register_8bit(<span class="hljs-number">1</span>).GetText(); <br/> string destinationRegister = <br/> context.register_8bit(<span class="hljs-number">0</span>).GetText(); <br/> <br/> // <span class="hljs-keyword">Add</span> the assembly opcodes <br/> assembly.<span class="hljs-keyword">Add</span>(<span class="hljs-string">";; BEGIN ADD "</span> + <br/> destinationRegister + <span class="hljs-string">", "</span> + sourceRegister + <br/> <span class="hljs-string">" (ADD_R8_R8)"</span>); <br/> assembly.<span class="hljs-keyword">Add</span>(<span class="hljs-string">"MOV_ALU_IN A, "</span> + <br/> destinationRegister); <br/> assembly.<span class="hljs-keyword">Add</span>(<span class="hljs-string">"MOV_ALU_IN B, "</span> + sourceRegister); <br/> assembly.<span class="hljs-keyword">Add</span>(<span class="hljs-string">"ADD"</span>); <br/> assembly.<span class="hljs-keyword">Add</span>(<span class="hljs-string">"MOV_ALU_OUT "</span> + <br/> destinationRegister); <br/> assembly.<span class="hljs-keyword">Add</span>(<span class="hljs-string">";; END ADD "</span> + destinationRegister + <br/> <span class="hljs-string">", "</span> + sourceRegister + <span class="hljs-string">" (ADD_R8_R8)"</span>); <br/> <br/> <span class="hljs-keyword">return</span> base.VisitADD_R8_R8(context); <br/>}
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 <br/>; and the Base Pointer <br/>MOV XL, <span class="hljs-number">0xFF</span> <br/>MOV XH, <span class="hljs-number">0xFF</span> <br/>MOV SP, X <br/>MOV XL, <span class="hljs-number">0</span> <br/>MOV XH, <span class="hljs-number">0</span> <br/>MOV BP, X <br/> <br/>; Initialize an address register <br/>MOV XL, <span class="hljs-number">0x00</span> <br/>MOV XH, <span class="hljs-number">0xFF</span> <br/>MOV Y, X <br/> <br/>; Initialize the D and E register with the <span class="hljs-number">1</span>st byte <br/>MOV D, [Y] <br/>MOV E, [Y + <span class="hljs-number">4</span>] <br/>ADD D, E <br/>PUSHF <br/> <br/>; Write register D to the <br/>; Output Port <br/>OUTB D <br/> <br/>; Initialize the D and E register with the <span class="hljs-number">2</span>nd byte <br/>MOV D, [Y + <span class="hljs-number">1</span>] <br/>MOV E, [Y + <span class="hljs-number">5</span>] <br/>POPF <br/>ADC D, E <br/>PUSHF <br/> <br/>; Write register D to the <br/>; Output Port <br/>OUTB D <br/> <br/>; Initialize the D and E register with the <span class="hljs-number">3</span>rd byte <br/>MOV D, [Y + <span class="hljs-number">2</span>] <br/>MOV E, [Y + <span class="hljs-number">6</span>] <br/>POPF <br/>ADC D, E <br/>PUSHF <br/> <br/>; Write register D to the <br/>; Output Port <br/>OUTB D <br/> <br/>; Initialize the D and E register with the <span class="hljs-number">4</span>th byte <br/>MOV D, [Y + <span class="hljs-number">3</span>] <br/>MOV E, [Y + <span class="hljs-number">7</span>] <br/>POPF <br/>ADC D, E <br/> <br/>; Write register D to the <br/>; Output Port <br/>OUTB D <br/> <br/>; Stops the CPU execution <br/>HLT <br/> <br/>; <span class="hljs-number">1</span> <span class="hljs-number">094</span> <span class="hljs-number">967</span> <span class="hljs-number">296</span>d <br/>DATA <span class="hljs-number">1111111100000000</span>b, <span class="hljs-number">00000000</span>b ; <span class="hljs-number">1</span>st Byte <br/>DATA <span class="hljs-number">1111111100000001</span>b, <span class="hljs-number">11100000</span>b ; <span class="hljs-number">2</span>nd Byte <br/>DATA <span class="hljs-number">1111111100000010</span>b, <span class="hljs-number">01000011</span>b ; <span class="hljs-number">3</span>rd Byte <br/>DATA <span class="hljs-number">1111111100000011</span>b, <span class="hljs-number">01000001</span>b ; <span class="hljs-number">4</span>th Byte <br/> <br/>; <span class="hljs-number">3</span> <span class="hljs-number">100</span> <span class="hljs-number">000</span> <span class="hljs-number">000</span>d <br/>DATA <span class="hljs-number">1111111100000100</span>b, <span class="hljs-number">00000000</span>b ; <span class="hljs-number">1</span>st Byte <br/>DATA <span class="hljs-number">1111111100000101</span>b, <span class="hljs-number">00111111</span>b ; <span class="hljs-number">2</span>nd Byte <br/>DATA <span class="hljs-number">1111111100000110</span>b, <span class="hljs-number">11000110</span>b ; <span class="hljs-number">3</span>rd Byte <br/>DATA <span class="hljs-number">1111111100000111</span>b, <span class="hljs-number">10111000</span>b ; <span class="hljs-number">4</span>th 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, <span class="hljs-string">[Y]</span>
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, <span class="hljs-string">[Y + 1]</span>
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:
<span class="hljs-symbol">SET</span> A, <span class="hljs-string">"0000"</span>
SET <span class="hljs-keyword">B, </span><span class="hljs-string">"0000"</span>
<span class="hljs-keyword">MOV8 </span>
<span class="hljs-keyword">MOV_ALU_OUT </span>XH
SET A, <span class="hljs-string">"0001"</span>
SET <span class="hljs-keyword">B, </span><span class="hljs-string">"0000"</span>
<span class="hljs-keyword">MOV8 </span>
<span class="hljs-keyword">MOV_ALU_OUT </span>XL
<span class="hljs-keyword">MOV16 </span>J, X
<span class="hljs-keyword">MOV16 </span>X, Y
<span class="hljs-number">16</span>BIT_ADDER
<span class="hljs-keyword">MOV16 </span>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 <span class="hljs-built_in">result</span> is stored <span class="hljs-keyword">in</span> <br/>; register F <br/>MOV E, <span class="hljs-number">0</span> <br/> <br/>; Initial <span class="hljs-built_in">value</span> <br/>MOV D, <span class="hljs-number">9</span> <br/> <br/>; Add <span class="hljs-keyword">the</span> current <span class="hljs-built_in">value</span> <span class="hljs-keyword">of</span> <br/>; register D <span class="hljs-built_in">to</span> <span class="hljs-keyword">the</span> <span class="hljs-built_in">result</span> <span class="hljs-keyword">in</span> <br/>; register F <br/>:LOOP <br/>ADD E, D <br/> <br/>; Decrement <span class="hljs-keyword">the</span> <span class="hljs-built_in">value</span> <span class="hljs-keyword">by</span> <span class="hljs-literal">one</span> <br/>DEC D <br/> <br/>; Conditional Jump <span class="hljs-keyword">if</span> <span class="hljs-keyword">the</span> Zero- <br/>; Flag <span class="hljs-built_in">from</span> <span class="hljs-keyword">the</span> ALU is <span class="hljs-keyword">not</span> <span class="hljs-number">1</span> <br/>JNZ :LOOP <br/> <br/>; Write register F <span class="hljs-built_in">to</span> <span class="hljs-keyword">the</span> <br/>; Output Port <br/>; OUTB E <br/> <br/>; Stops <span class="hljs-keyword">the</span> CPU execution <br/>; 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 <span class="hljs-keyword">Stack</span> Pointer <br/><span class="hljs-keyword">MOV</span> XL, 0xFF <br/><span class="hljs-keyword">MOV</span> XH, 0xFF <br/><span class="hljs-keyword">MOV</span> SP, X <br/> <br/><span class="hljs-keyword">MOV</span> <span class="hljs-keyword">D</span>, 00001111b <br/>PUSH <span class="hljs-keyword">D</span> <br/>POP <span class="hljs-keyword">E</span>
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
<span class="hljs-symbol">SET</span> A, <span class="hljs-string">"1111"</span> <br/>SET <span class="hljs-keyword">B, </span><span class="hljs-string">"1111"</span> <br/><span class="hljs-keyword">MOV8 </span><br/><span class="hljs-keyword">MOV_ALU_OUT </span>XL <br/>SET A, <span class="hljs-string">"1111"</span> <br/>SET <span class="hljs-keyword">B, </span><span class="hljs-string">"1111"</span> <br/><span class="hljs-keyword">MOV8 </span><br/><span class="hljs-keyword">MOV_ALU_OUT </span>XH <br/><span class="hljs-keyword">MOV16 </span><span class="hljs-built_in">SP</span>, X <br/>SET A, <span class="hljs-string">"1111"</span> <br/>SET <span class="hljs-keyword">B, </span><span class="hljs-string">"0000"</span> <br/><span class="hljs-keyword">MOV8 </span><br/><span class="hljs-keyword">MOV_ALU_OUT </span>D <br/>SAVE_FLAGS <br/>SET A, <span class="hljs-string">"1111"</span> <br/>SET <span class="hljs-keyword">B, </span><span class="hljs-string">"1111"</span> <br/><span class="hljs-keyword">MOV8 </span><br/><span class="hljs-keyword">MOV_ALU_OUT </span>XL <br/>SET A, <span class="hljs-string">"1111"</span> <br/>SET <span class="hljs-keyword">B, </span><span class="hljs-string">"1111"</span> <br/><span class="hljs-keyword">MOV8 </span><br/><span class="hljs-keyword">MOV_ALU_OUT </span>XH <br/><span class="hljs-keyword">MOV16 </span>J, X <br/><span class="hljs-keyword">MOV16 </span>X, <span class="hljs-built_in">SP</span> <br/><span class="hljs-number">16</span>BIT_ADDER <br/><span class="hljs-keyword">MOV16 </span><span class="hljs-built_in">SP</span>, X <br/><span class="hljs-keyword">MOV16 </span>M, <span class="hljs-built_in">SP</span> <br/>STORE D <br/>RESTORE_FLAGS <br/>SAVE_FLAGS <br/><span class="hljs-keyword">MOV16 </span>M, <span class="hljs-built_in">SP</span> <br/>LOAD E <br/>SET A, <span class="hljs-string">"0001"</span> <br/>SET <span class="hljs-keyword">B, </span><span class="hljs-string">"0000"</span> <br/><span class="hljs-keyword">MOV8 </span><br/><span class="hljs-keyword">MOV_ALU_OUT </span>XL <br/>SET A, <span class="hljs-string">"0000"</span> <br/>SET <span class="hljs-keyword">B, </span><span class="hljs-string">"0000"</span> <br/><span class="hljs-keyword">MOV8 </span><br/><span class="hljs-keyword">MOV_ALU_OUT </span>XH <br/><span class="hljs-keyword">MOV16 </span>J, X <br/><span class="hljs-keyword">MOV16 </span>X, <span class="hljs-built_in">SP</span> <br/><span class="hljs-number">16</span>BIT_ADDER <br/><span class="hljs-keyword">MOV16 </span><span class="hljs-built_in">SP</span>, X <br/>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 <span class="hljs-keyword">the</span> Stack Pointer <br/>MOV XL, <span class="hljs-number">0xFF</span> <br/>MOV XH, <span class="hljs-number">0xFF</span> <br/>MOV SP, X <br/> <br/>; Sets <span class="hljs-keyword">the</span> Zero Flag <span class="hljs-built_in">to</span> <span class="hljs-number">1</span> <br/>MOV D, <span class="hljs-number">1</span> <br/>MOV E, <span class="hljs-number">1</span> <br/>SUB D, E <br/> <br/>; Store <span class="hljs-keyword">the</span> Flags onto <span class="hljs-keyword">the</span> Stack <br/>PUSHF <br/> <br/>; Load <span class="hljs-keyword">the</span> Flags <span class="hljs-built_in">from</span> <span class="hljs-keyword">the</span> Stack <br/>; <span class="hljs-keyword">into</span> <span class="hljs-keyword">the</span> G Register <br/>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 <span class="hljs-keyword">Pointer</span> <br/>MOV XL, 0xFF <br/>MOV XH, 0xFF <br/>MOV SP, X <br/> <br/>MOV F, 11110000b <br/><span class="hljs-keyword"> </span><br/><span class="hljs-keyword">; C</span>all<span class="hljs-function"><span class="hljs-keyword"> a subrout</span>i</span>ne.<span class="hljs-keyword">.. </span><br/><span class="hljs-keyword">C</span>AL<span class="hljs-function"><span class="hljs-keyword">L :SUBROUT</span></span>INE <br/> <br/>MOV F, 10101010b <br/> <br/>; St<span class="hljs-function"><span class="hljs-keyword">ops pro</span></span>gram execution <br/>HL<span class="hljs-function"><span class="hljs-keyword">T </span></span><br/><span class="hljs-function"><span class="hljs-keyword"> </span></span><br/><span class="hljs-function"><span class="hljs-keyword">:SUBROU</span></span>TINE <br/>MOV F, 01010101b <br/>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.
<span class="hljs-keyword">PUSH</span> <span class="hljs-number">10</span> ; Number of characters
<span class="hljs-keyword">PUSH</span> <span class="hljs-number">0</span>x00 ; <span class="hljs-number">16</span>-bit memory address – Low <span class="hljs-keyword">Byte</span>
<span class="hljs-keyword">PUSH</span> <span class="hljs-number">0</span>xFA ; <span class="hljs-number">16</span>-bit memory address – High <span class="hljs-keyword">Byte</span>
<span class="hljs-keyword">CALL</span> :_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.
<span class="hljs-keyword">PUSH </span><span class="hljs-keyword">BP </span>
<span class="hljs-keyword">MOV </span><span class="hljs-keyword">BP, </span><span class="hljs-built_in">SP</span>
<span class="hljs-keyword">SUB </span><span class="hljs-built_in">SP</span>, <span class="hljs-number">3</span>
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 <span class="hljs-keyword">D</span>, [BP + <span class="hljs-number">5</span>] ; <span class="hljs-number">2.</span> <span class="hljs-keyword">Parameter</span>
MOV <span class="hljs-keyword">E</span>, [BP + <span class="hljs-number">4</span>] ; <span class="hljs-number">1.</span> Paramter
ADD <span class="hljs-keyword">D</span>, <span class="hljs-keyword">E</span>
; Schreiben einer lokalen
; Variablen
MOV [BP - <span class="hljs-number">1</span>], <span class="hljs-keyword">D</span>
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.
<span class="hljs-keyword">MOV</span> <span class="hljs-built_in">SP</span>, <span class="hljs-built_in">BP</span>
<span class="hljs-keyword">POP</span> <span class="hljs-built_in">BP</span>
<span class="hljs-keyword">RET</span>
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:
<span class="hljs-keyword">ADD </span><span class="hljs-built_in">SP</span>, <span class="hljs-number">3</span>
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 <span class="hljs-keyword">Pointer</span> <br/>MOV XL, 0xFF <br/>MOV XH, 0xFF <br/>MOV SP, X <br/> <br/>MOV F<span class="hljs-number">,</span> 1 <br/>MOV G, 00010000b <br/><span class="hljs-keyword"> </span><br/><span class="hljs-keyword">; C</span>all<span class="hljs-function"><span class="hljs-keyword"> a subrout</span>i</span>ne.<span class="hljs-keyword">.. </span><br/><span class="hljs-keyword">C</span>AL<span class="hljs-function"><span class="hljs-keyword">L :SUBROUT</span></span>INE <br/><span class="hljs-keyword"> </span><br/><span class="hljs-keyword">;</span> Do somethi<span class="hljs-keyword">ng e</span>lse after the<span class="hljs-keyword"> </span><br/><span class="hljs-keyword">; recurs</span>i<span class="hljs-function"><span class="hljs-keyword">ve funct</span></span>i<span class="hljs-keyword">on c</span>all... <br/>INC G <br/><span class="hljs-built_in"> </span><br/><br/><br/><span class="hljs-built_in">; Wr</span>ite register G to the <br/>; Output Port <br/>OUTB G <br/> <br/>; Sto<span class="hljs-function"><span class="hljs-keyword">ps prog</span></span>ram execution <br/>HLT<span class="hljs-function"><span class="hljs-keyword"> </span></span><br/><span class="hljs-function"><span class="hljs-keyword"> </span></span><br/><span class="hljs-function"><span class="hljs-keyword">:SUBROUT</span></span>INE <br/>INC F <br/>CMP F, G <br/>JZ :SUBROUTINE_RETURN <br/><span class="hljs-keyword"> </span><br/><span class="hljs-keyword">; Recurs</span>i<span class="hljs-keyword">ve c</span>all.<span class="hljs-keyword">.. </span><br/><span class="hljs-keyword">C</span>AL<span class="hljs-function"><span class="hljs-keyword">L :SUBROUT</span></span>INE <br/> <br/>:SUBROUTINE_RETURN <br/>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 <br/>ENTER <span class="hljs-number">0</span> <br/> <br/>MOV H, <span class="hljs-number">0</span> <br/> <br/>; Initialize <span class="hljs-keyword">the</span> registers <span class="hljs-keyword">with</span> <br/>; <span class="hljs-keyword">the</span> current BP <br/>MOV X, BP <br/>MOV D, XH <br/>MOV E, XL <br/> <br/>:BP_NOT_NULL <br/>; Load <span class="hljs-keyword">the</span> memory content <span class="hljs-keyword">of</span> <span class="hljs-keyword">the</span> <br/>; current BP (pointer <span class="hljs-built_in">to</span> <br/>; <span class="hljs-keyword">the</span> previous stack frame) <span class="hljs-keyword">into</span> <br/>; <span class="hljs-keyword">the</span> registers <br/>MOV XH, D <br/>MOV XL, E <br/>MOV Y, X <br/> <br/>; Load <span class="hljs-keyword">the</span> BP <span class="hljs-keyword">of</span> <span class="hljs-keyword">the</span> previous <br/>; stack frame <span class="hljs-keyword">into</span> <span class="hljs-keyword">the</span> registers <br/>MOV D, [Y] <br/>MOV E, [Y + <span class="hljs-number">1</span>] <br/>; Write out <span class="hljs-keyword">the</span> higher <span class="hljs-keyword">byte</span> <span class="hljs-keyword">of</span> <br/>; <span class="hljs-keyword">the</span> <span class="hljs-literal">return</span> address <br/>MOV XL, [Y + <span class="hljs-number">2</span>] <br/>OUTB XL <br/> <br/>; Write out <span class="hljs-keyword">the</span> <span class="hljs-built_in">lower</span> <span class="hljs-keyword">byte</span> <span class="hljs-keyword">of</span> <br/>; <span class="hljs-keyword">the</span> <span class="hljs-literal">return</span> address <br/>MOV XL, [Y + <span class="hljs-number">3</span>] <br/>OUTB XL <br/> <br/>; Check <span class="hljs-keyword">if</span> <span class="hljs-keyword">the</span> <span class="hljs-built_in">lower</span> <span class="hljs-keyword">byte</span> <span class="hljs-keyword">of</span> <span class="hljs-keyword">the</span> <br/>; BP is <span class="hljs-literal">NULL</span>. <br/>; We should also check here <span class="hljs-keyword">the</span> <br/>; higher <span class="hljs-keyword">byte</span> <span class="hljs-keyword">of</span> <span class="hljs-keyword">the</span> BP <span class="hljs-keyword">if</span> <span class="hljs-keyword">it</span> <br/>; is <span class="hljs-literal">NULL</span>... <br/>CMP E, H <br/> <br/>; We haven‘t yet reached <span class="hljs-keyword">the</span> <span class="hljs-number">1</span>st <br/>; stack frame, therefore we <br/>; walk again down <span class="hljs-keyword">the</span> stack <br/>JNZ :BP_NOT_NULL <br/> <br/>LEAVE <br/>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., http://www.dotnetpro.de/A1706CPU
- Klaus Aschenbrenner, Eine einfache CPU entwickeln, Teil 2, Architektur der Selbstbau-CPU, dotnetpro 7/2017, Seite 126 ff., http://www.dotnetpro.de/A1707CPU
- Der Assembler zur Selbstbau-CPU auf GitHub, https://github.com/KPU-RISC/KPU
- Objektorientierter Parsergenerator ANTLR, http://www.antlr.org/
