Hello, Guest the thread was called6.8k times and contains 154 replays

last post from M. J. at the

Virtuelle Maschinen und Bytecode-Interpreter am 6502/6510 Prozessor

  • Hi, ich denke der Thread-Titel sagt schon, worum es geht.


    Die Idee für diesen Thread kam mir in einem anderen Thread mit dem Titel


    Opcode-Dispatchmethoden bzw. Indirekte Sprünge


    Ich zitiere einen Post teilweise von dort hierher zum Start:


    Quote from M. J.

    Ja, gerne. Das Thema interessiert mich auch. Habe selber vor einiger Zeit mal eine virtuelle Maschine für einen hypothetischen 16-Bit-Risc-Prozessor (Zwei-Register-Befehle mit 16 Registern, d. h. 4 Bit pro Register) geschrieben, die einigermaßen schnell läuft.
    ...
    Von der extremen RISC-Philosophie bin ich letzten Endes wieder abgewichen, da so die Integration von Immediate-Konstanten (auch für Sprungbefehle bzw. Unterprogrammaufrufe) programmtechnisch einfach zu aufwendig und zu langsam wurde. Nichtsdestoweniger verbrauchen die allermeisten Befehle nur 16 Bit, da es für die häufigen MOVE-, ADD- und CMP-Befehle Kurzformen gibt. Die Einführung dieser Kurzformen war auch der Grund, wieso ich keine 3-Register-Befehle verwende, da sie a) nur selten wirklich gebraucht werden, aber b) viel Platz in der ISA veranschlagen.

    Ich habe vor allem deshalb 3 Register Befehle genommen, damit man viele Befehle synthetisieren kann, wie ein MOV als ADD r3, r4, r0 (r0 immer 0) = MOV r3, r4
    usw.


    Ich denke, du hast dafür eigene Befehle?

  • Ich denke, du hast dafür eigene Befehle?

    Ja, richtig. Aber der Mehraufwand dafür ist sehr gering, hingegen die Geschwindigkeitssteigerung in der Ausführung enorm. Zum einen ist das Dekodieren von drei Registern umständlicher (bei zwei Registern kann man den Registersatz mit den 6502 X- und Y-Registern direkt adressieren), zum anderen dauert eine Addition auch länger als ein direktes Umkopieren.

  • Ja diese Idee hatte ich auch schon.


    Richtig interessant wäre das, wenn man den Bytecode als Output von einem Hochsprache Compiler bekommen würde.
    Oder meinst du Java Bytecode??


    Der LCC Compiler gibt Bytecode aus.
    Das nutzt zB. ein FPGA Softcore aus, der X32.




    Es gibt ja für den C64 sehr große EPROM Module, wo der Interpreter laufen könnte.
    Der Bytecode ist extrem klein, so dass die 64kb RAM schon viel bringen.


    Im EPROM könnte man auch Funktionen ablegen, quasi eine CLIB für Zugriff auf Peripherie, was dann die Bytecode Apps schlank machen würde.

  • Ich speichere immer den INHALT eines der 3 Register in A (bereits am Ende des Dispatchers), und die NUMMER der Reg kommt ins X- die andere ins Y-Register, so gehe ich in den jeweiligen Handler.


    Aber natürlich hast du recht. Ich denke deiner wird weitaus flotter sein.


    Aber, was machst du mit den vielen Bits?
    Ich denke, du hast einen 8-Bit Opcode (Ich nur 4-Bit)?


    Bei mir ist es so:


    Byte 1: 7-4 -> Opcode, 3-0 -> Destination Register (im X-Reg als Index)
    Byte 2: 7-4 -> Source Register 1 (INHALT gleich ins A-Reg), 3-0 -> Source Register 2 (im Y-Reg als Index)


    So gehe ich in den jeweiligne Handler rein dann.


    Add r4, r8, r12 --> r4 (Index im X) = r8 (Inhalt im A) + r12(Index im Y)

  • Als kleines Beispiel die Abarbeitung eines Move-Befehls. Nach der allgemeinen Dekodierung springt der Befehlsinterpreter über einen indirekten Sprung in die folgende Routine, wobei der Akkumulator den Index des Zielregisters beinhaltet und das Y-Register den Index des Quellregisters.

  • Welche indirekte Sprung-Methode benutzt du?


    Ich verweise dich weiter auf diesen Thread von mir:


    Opcode-Dispatchmethoden bzw. Indirekte Sprünge


    Und falls ich zu spät für deine Antwort geantwortet habe, ich habe oben meine extreme Risc-ISA als pdf angehängt.
    Bis zu den beiden Branches hatte ich mein Fragment so weit fertig.
    Dann hat mich die Lust verlassen.


    P.S. sollte in deinem Code-Beispiel nicht "A = Zielregister" eher "X = Zielregister" lauten, oder übersehe ich da etwas?

  • Aber, was machst du mit den vielen Bits?

    Der reine Befehlscode ist in den allermeisten Fällen im oberen Byte abgelegt, nur in ganz paar Ausnahmen findet eine weitere Spezifizierung im unteren Byte statt. Daher kann man das oberste Byte nehmen für die Auswertung in der Interpreterschleife.
    Von den 256 Befehlsmöglichkeiten sind aber nur wenige voll genutzt, d. h. die vollständigen 8 Bit geben den Befehl an:
    15-8 = Befehl
    7-4 = Quellregister
    3-0 = Zielregister
    Viele Befehle werden auch codiert als:
    15-12 = Befehl
    11-8 = Register
    7-0 = 8-Bit Immediate-Wert (wird vorzeichenerweitert)
    Mit letzteren läßt sich sehr viel Platz im Code sparen.

    sollte in deinem Code-Beispiel nicht "A = Zielregister" eher "X = Zielregister" lauten

    Theoretisch ja, allerdings gibt es Befehle, in denen das X-Register nicht den Index beinhaltet. Da der Transfer des Wertes von A nach X bei vielen, aber nicht bei allen Befehlen auftritt, habe ich diesen in die spezifische Befehlsbearbeitung verschoben.

    Welche indirekte Sprung-Methode benutzt du?

    Nur Ram mit Selbstmodifikation. Die Befehlsdekodierung teile ich auf in Befehle, bei denen das Highbit gesetzt ist (Kurzbefehle mit einem Register und einer Konstanten) und nicht gesetzt ist (sonstige Befehle):

  • Ich hab mal einen kleinen Compiler für eine Basic/Pascal-änliche Sprache geschrieben, die VM-Stackcode (eine hypothetische von mir erfundene Stack-Maschine) erzeugt.
    Geschrieben in meiner Lieblingsprogrammiersprache Pure Basic (recht unbekannt, aber ich liebe sie :) )


    Der Code einer Stack-Maschine ist recht einfach zu optimieren, deshalb habe ich eine Stack-Maschine gewählt, ein Herr namens Tanenbaum hat da einen Artikel geschrieben (uralt, aber extrem gut mMn):
    http://www.nada.kth.se/~mosavi…eephole/p21-tanenbaum.pdf


    Im Netz gibts aber auch Diskussionen über die Dalvik-VM (https://de.wikipedia.org/wiki/Dalvik_Virtual_Machine), dass die besser optimieren würde (=Register-Maschine). Habe mich da zuwenig eingearbeitet, um ein Endurteil abzugeben. Ich mag aber Stackmaschinen irgendwie gerne.


    Wie auch immer, auch ich denke, dass man am 6502 mit Stack-Maschinen besser klarkommt.
    Den Stack kann man mit X oder Y indexmäßig addressieren, wenn man mit 16-Bit-Zahlen arbeitet, dann würde ich eine extra Stack für LO/HB empfehlen. Dann kann man mit einem Stackpointer in X oder Y ohne eine dex oder inx gleich beide Bytes abholen.


    Waren nicht die guten alten Pascal p-Maschinen auch Stackmaschinen?
    google: p-Source a guide to the apple pascal system
    Edit: habe da grad nachgeguckt, ja, war definitiv eine Stack-Maschine, das Fragezeichen kann man streichen.


    Die Java VM ist eine Stack-Maschine.

  • Quote from M.J.

    Nur Ram mit Selbstmodifikation. Die Befehlsdekodierung teile ich auf in Befehle, bei denen das Highbit gesetzt ist (Kurzbefehle mit einem Register und einer Konstanten) und nicht gesetzt ist (sonstige Befehle):

    Mit "Kurzbefehle" meinst du die mit einer 8-bit immediate Konstanten?


    Wie in:

    Quote from M.J.

    Viele Befehle werden auch codiert als:
    15-12 = Befehl
    11-8 = Register
    7-0 = 8-Bit Immediate-Wert (wird vorzeichenerweitert)


    Quote from M.J.

    Theoretisch ja, allerdings gibt es Befehle, in denen das X-Register nicht den Index beinhaltet. Da der Transfer des Wertes von A nach X bei vielen, aber nicht bei allen Befehlen auftritt, habe ich diesen in die spezifische Befehlsbearbeitung verschoben.

    Ah, ich habe den WERT eines der Registers bereits für alle Befehlshandler in der Dispatch-Routine vorgeladen.
    Deshalb nenne ich es auch "ra" in meinem ISA-pdf oben.
    Das ist das Register mit dessen Wert A bereits belegt ist, bei Eintritt in den Befehlshandler.


    Abschließend möchte ich sagen, dass dein 2-Register-Ansatz interessant klingt, ich bin schon am Entwerfen einer entsprechenden ISA für mich ;-)

  • Den Stack kann man mit X oder Y indexmäßig addressieren, wenn man mit 16-Bit-Zahlen arbeitet, dann würde ich eine extra Stack für LO/HB empfehlen. Dann kann man mit einem Stackpointer in X oder Y ohne eine dex oder inx gleich beide Bytes abholen.

    Brauchst Du gar nicht. (Korrektur. Hatte ich zunächst falsch verstanden.) Du meinst wahrscheinlich sowas wie: Da sich die Befehle in der Regel immer auf den TOS und den darunterliegenden Wert beziehen, reicht es aus, so etwas zu schreiben wie:

    Tanenbaum

    Tanenbaum... Tanenbaum... Tanenbaum... Wo habe ich den Namen bloß schon einmal gehört...? ^^

    Ich hab mal einen kleinen Compiler für eine Basic/Pascal-änliche Sprache geschrieben, die VM-Stackcode (eine hypothetische von mir erfundene Stack-Maschine) erzeugt.

    Wow! Klingt gut. Wie umfangreich ist die Sprache? (Gibt es sowas wie Arrays, Strings, Records, TYPE-Definitionen usw.? Welche Befehle, Schleifentypen sind enthalten? Sind auch Prozeduren mit lokalen Variablen und Parametern eingebaut?)

    Wie auch immer, auch ich denke, dass man am 6502 mit Stack-Maschinen besser klarkommt.

    Dem kann ich zustimmen. Der Vorteil der Stackmaschine ist, daß man die Register nicht aus dem Befehlscode extrahieren muß, wodurch die Befehlsabarbeitung schneller wird. Der Nachteil ist natürlich, daß man in der Regel Werte, die öfters nacheinander gebraucht werden, nicht im Stack lagern kann, was beim wahlweisen Registerzugriff möglich wäre. Dafür ist der Code aber trotzdem im Durchschnitt recht kompakt.
    Übrigens empfehle ich Dir, den Stapel aufzuspalten in einen Datenstapel (vergleichbar mit dem Stapel des Prozessors) und einen Evaluationsstapel, vergleichbar mit den Registern im Prozessor oder den Registern der FPU beim x86. Normalerweise reicht eine Tiefe von 12 für den Evaluationsstapel aus, sofern man zwei Befehle einbaut, um den Inhalt des Stapels im Ram zu sichern und von dort wiederherzustellen.

    Waren nicht die guten alten Pascal p-Maschinen auch Stackmaschinen?
    google: p-Source a guide to the apple pascal system

    Oh ja, und ich habe darauf sogar damals[tm] programmieren gelernt und mir später auch mal die p-Maschine genauer angesehen. Das System war aufgrund der Natur einer emulierten virtuellen Maschine etwas langsam, aber erstaunlich leistungsfähig. Für damalige Verhältnisse eine Meisterleistung.

  • Wow! Klingt gut. Wie umfangreich ist die Sprache? (Gibt es sowas wie Arrays, Strings, Records, TYPE-Definitionen usw.? Welche Befehle, Schleifentypen sind enthalten? Sind auch Prozeduren mit lokalen Variablen und Parametern eingebaut?)

    Bis zu komplexen Datentypen bin ich nie gekommen:


    1) Conditionals und Schleifen (if-elseif-else-endif, repeat-until, repeat-forever, repeat-while, while-wend, break, continue)


    2) integers und strings als Datentypen


    3) Vollständige Math Expressions sowie Conditional expressions evaluation mit eigenem Evaluation stack, wie von dir vorgeschlagen (Precendence rules wie in Pascal genommen: https://www.tutorialspoint.com…_operators_precedence.htm)
    - mit Typetypen, die vom absteigendem Parser zurückdifundieren, somit erkennt er, wenn Types nicht zusammenpassen und zeigt Fehler an. gerade dieser Teil mit den Typefehler kostete mich 2 Jahre lol, war nirgends in der Lit., die ich mir angelesen habe, für mich verständlich beschrieben, so habe ich nach viel Probiererei und Kopfzerbrecherrei das entwickelt :-) )


    4) ein paar Konsolenbefehle, um eine IO zu machen (input, print)


    5) goto, User-Labels


    6) Prozeduren im Anfangsstadium (nie ganz fertiggemacht) - ist aber nicht so kompliziert



    Kennst du Crenshaw? http://www.pp4s.co.uk/main/tu-trans-comp-jc-intro.html
    Wirth vmtl. schon: http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
    Das umfangreichste und coolste Buch, das ich gelesen habe (habe diePapierversion damals über Amazon aus USA kommen lassen LOL), ist: gamescripting mastery varanese (selber googeln)


    Habe aber (nun, "aber" ist wohl nicht das richtige Wort) alles INNERHALB der High-Level-Programmiersprache mit den Mitteln der Programmiersprache gemacht und eben nicht in X86-ASM.
    So ist der Evaluation-Stack eben ein Array von Pure Basic. Die Rekursion, die für nested ifs, whiles usw. notwendig ist, entsteht wie von selbst durch eben rekursiven call der Pure Basic Subroutines.


    Am 6502 in ASM sieht das anders aus, da kann ich kein Basic-Array nehmen, da müssen wir das direkt im RAM machen, wie das eben die p-Maschine auch macht. Das ist zusätzlich eine Heraussforderung.

  • Du meinst wahrscheinlich sowas wie: Da sich die Befehle in der Regel immer auf den TOS und den darunterliegenden Wert beziehen, reicht es aus, so etwas zu schreiben wie:

    Ich denke, dass tom42 eher zwei getrennte Stacks für Lo und Hi-Byte meint, so dass über zwei verschiedene Base-Addressen mit demselben unveränderten Index-Register auf beide zugegriffen wird?


    Und: Super, toll zu lesen, das Thema! Danke euch beiden vorerst. Ich lass einmal wirken und senfe demnächst.


    OK, nein, eins will ich doch zum Thema stellen: Angenommen ein Hybrid aus Stack und Register. Mir erscheint das insofern vernünftig, als bei komplexeren Operationen (z.B. float EXP oder sowas) es ziemlich angeraten scheint, die Operanden in der ZP an absoluten Addressen zu halten, sonst wirds echt langsam. Aber das bedeutet, es dürfte bezüglich der Ops einen "Break Even" geben ab dem sich das Kopieren von Operanden in die ZP bzw,. vom Stack in fixe Register auszahlt.


    Ich bin da noch nicht wirklich durchdacht, habt ihr euch da mehr überlegt?


    Ach und noch eine Frage an M.J: Wenn deine Sprungtabelle in der ZP ganz unten ist, nimmst du 00 und 01 aber schon aus, oder?

  • Wow, daybyter, sowas habe ich gesucht :-)


    Quote from BlondMammuth

    Ich denke, dass tom42 eher zwei getrennte Stacks für Lo und Hi-Byte meint, so dass über zwei verschiedene Base-Addressen mit demselben unveränderten Index-Register auf beide zugegriffen wird?

    Ja, BlondMammuth, das habe ich gemeint.

    Quote from BlondMammuth

    Ach und noch eine Frage an M.J: Wenn deine Sprungtabelle in der ZP ganz unten ist, nimmst du 00 und 01 aber schon aus, oder?

    In meiner VM tu ich das zumindest. Woz tut es in SWEET16 nicht, weil er einen 6502 im Apple drinnen hat.
    Da ich aber am C64-Emulator frickle (6510), habe ich dort den Port.
    Somit starte ich mit dem SWEET16 R0 (=Accumulator) bei $02/$03 (Ich hab mir die SWEET16 umgeschrieben auf C64).
    Edit: Sorry, ich habe das falsch verstanden, was du gemeint hast, ich beziehe mich auf die 16 virtuellen Register der SWEET16 VM.
    Egal, es gilt dennoch, $00/$01 sollte man beim 6510 lieber in Ruhe lassen.

  • tom42 : Danke für die Links. Werde ich mir mal in Ruhe ansehen.

    mit Typetypen

    Sowas benötigt man in der Tat, wenn es in der Sprache keine strenge Typisierung gibt. Bei Pascal bräuchte man dies nicht, da zu jeder Variable der Typ zur Compilezeit bekannt ist, so daß man verschiedene Befehle, z. B. Addition für Integer- oder Addition für Fließkommazahlen, erzeugen kann.

    Habe aber (nun, "aber" ist wohl nicht das richtige Wort) alles INNERHALB der High-Level-Programmiersprache mit den Mitteln der Programmiersprache gemacht und eben nicht in X86-ASM.

    Assembler für den Interpreter ist auf PCs nicht zwingend notwendig, nur wenn man wirklich die maximale Geschwindigkeit rausholen will. Theoretisch könnte man eine virtuelle Maschine auch in C64-Basic schreiben, jedoch wäre der Gebrauch eine nervliche Herausforderung.

    Die Rekursion, die für nested ifs, whiles usw. notwendig ist, entsteht wie von selbst durch eben rekursiven call der Pure Basic Subroutines.

    Tip: Wenn man die Kontrollstrukturen aufbricht in ihre Bestandteile (Vergleiche, bedingte Sprünge usw.) braucht man wie in Assembler keine rekursiven Aufrufe mehr für die Abarbeitung von Schleifen. Diese haben einen großen Nachteil: Möchte man z. B. eine Prozedur vorzeitig mittels "return" verlassen, aber der Programmzähler befindet sich innerhalb verschachtelter Schleifen, hat man das Problem, daß man diese ganzen rekursiven Aufrufe irgendwie rückabwickeln muß.

    Ich nehme an, dass du damit das bezeichnest, was ich als "jmp DISPATCH" beschreiben würde?

    Gut erkannt. DISPATCH heißt bei mir (in diesem Fall) befehl.

    Warum nicht "rts"?

    Unterprogrammaufrufe mittels JSR und RTS sind zu langsam. Der Befehl wird mittels JMP (ind) angesprungen und springt am Ende mit JMP abs zurück zur Schleife. Der Grund dafür ist, daß die virtuelle Maschine auf Geschwindigkeit ausgelegt ist, nicht auf minimale Codelänge.

    Ich denke, dass tom42 eher zwei getrennte Stacks für Lo und Hi-Byte meint,

    Das waren in dem Beispiel reg_0 und reg_1. ^^

    Mir erscheint das insofern vernünftig, als bei komplexeren Operationen (z.B. float EXP oder sowas) es ziemlich angeraten scheint, die Operanden in der ZP an absoluten Addressen zu halten, sonst wirds echt langsam.

    Da hast Du völlig recht. Das ist wirklich ein Problem bei der Einbindung von Fließkommaroutinen in die Stackmaschine. Mit dem üblichen Verfahren kommt man nicht umhin, vor einer Fließkommaoperation die Werte vom Stapel zu holen und in die Fließkomma-Akkumulatoren zu kopieren, dann die Routine aufzurufen und anschließend das Ergebnis wieder auf den Stack zu schreiben. Gemessen jedoch an der generell langsamen Abarbeitung von Fließkommaoperationen wirken sich diese zusätzlichen Befehle nicht so sehr aus.
    Übrigens: Die Stackmaschine von ApplePascal (p-Code) speichert alle Werte auf dem 6502-Prozessorstack, d. h. für jede Operation werden zunächst die Werte vom Stapel mit PLA geholt und das Ergebnis mit PHA zurückgeschrieben. Das ist noch langsamer als der Zugriff über zp, x.

    Wenn deine Sprungtabelle in der ZP ganz unten ist, nimmst du 00 und 01 aber schon aus, oder?

    Ja, auf jeden Fall. Die Position des Stapels in der ZP ist im Grunde genommen egal und muß nicht direkt 0 sein.

  • Quote from M.J.

    Sowas benötigt man in der Tat, wenn es in der Sprache keine strenge Typisierung gibt. Bei Pascal bräuchte man dies nicht, da zu jeder Variable der Typ zur Compilezeit bekannt ist, so daß man verschiedene Befehle, z. B. Addition für Integer- oder Addition für Fließkommazahlen, erzeugen kann.

    Möglicherweise habe ich falsche Fachausdrücke verwendet. Genau das meinte ich. Auch bei mir ist es zur Compilezeit bekannt (wobei ich mich auch schon mal an einer Sprache versucht habe, wo die Variablen jeden Typ annehmen können, der Typ also am Stack dazugespeichert wird).
    Aber die Technik, in einem rekursiv absteigenden Parser die Typen durch einen Rückgabewert sozusagen aufsteigen zu lassen, die habe ich erst nach langem Probieren und Hirnzermartern gecheckt, das meinte ich.


    Quote from M.J.

    Tip: Wenn man die Kontrollstrukturen aufbricht in ihre Bestandteile (Vergleiche, bedingte Sprünge usw.) braucht man wie in Assembler keine rekursiven Aufrufe mehr für die Abarbeitung von Schleifen. Diese haben einen großen Nachteil: Möchte man z. B. eine Prozedur vorzeitig mittels "return" verlassen, aber der Programmzähler befindet sich innerhalb verschachtelter Schleifen, hat man das Problem, daß man diese ganzen rekursiven Aufrufe irgendwie rückabwickeln muß.

    Nein, nein, rekursiv sind die Pure Basic Prozeduren (=rekursiv absteigender Parser), die das Ausgeben der entsprechenden VM-Befehle besorgen. Somit ist ein "break" oder "continue" recht einfach. Er springt einfach das End-Label bei "break" oder das Start-Label bei "continue" an und ist draußen bzw. wieder am Anfang. Kein VM-Stack wird da belastet oder verwendet. In der VM ist da nix rekursiv bei diesen Strukturen.


    Quote from M.J.

    Unterprogrammaufrufe mittels JSR und RTS sind zu langsam. Der Befehl wird mittels JMP (ind) angesprungen und springt am Ende mit JMP abs zurück zur Schleife. Der Grund dafür ist, daß die virtuelle Maschine auf Geschwindigkeit ausgelegt ist, nicht auf minimale Codelänge.

    Sehr gute Idee.
    Wäre ein selbstmodifizierender JMP direkt nicht schneller als ein JMP (ind)?
    Das LO- und HI-Byte musst du ohnehin in einen Vektor/Pointer schreiben, da kannst du es ja gleich in den Programmcode schreiben, oder übersehe ich da was?
    http://www.6502.org/tutorials/6502opcodes.html#JMP

  • Genau das meinte ich.

    Ah, Entschuldigung. Mein Fehler.

    rekursiv sind die Pure Basic Prozeduren

    Ich befürchte, ich hab's noch nicht kapiert. :( (Ist anscheinend schon ein bißchen spät für mich...) Ich hatte das so verstanden, daß der Interpreter in Pure Basic geschrieben ist und bei einer Schleifenanweisung sich rekursiver Aufrufe bedient, also z. B.

    Wenn der Compiler so aufgebaut ist (bzw. sein muß), ist das kein Problem, sofern er als Ergebnis eine nichtrekursive Struktur auswirft z. B. eine Folge von Vergleichs- und Sprungbefehlen. Falls aber der Interpreter selbst solch eine rekursive Struktur aufweisen sollte, gibt es ein Problem.

    Wäre ein selbstmodifizierender JMP direkt nicht schneller als ein JMP (ind)?

    Nein, da man bei einem JMP beide Adressbytes patchen müßte. (Die virtuelle Maschine wird sicherlich länger werden als eine Speicherseite.) Außerdem muß man das Sprungziel vorher noch über eine Tabelle ermitteln. Bei JMP (ind) liegt die Sprungtabelle (für maximal 128 Befehle) zu Beginn einer Speicherseite, so daß nur der Befehl * 2 genommen und damit das Lowbyte des Befehls gepatcht werden muß.