Werkzeuge und Beispiele Abstrakte Maschinen

Die Werkzeuge sind alle auf der Übungsmaschine g0.complang.tuwien.ac.at installiert.

Die Beispiele finden Sie in einem Paket, das Sie auf der g0 wie folgt auspacken können:

tar xfJ /usr/ftp/pub/anton/lvas/abstrakte-maschinen/examples/examples.tar.xz

Sie erhalten dann ein Verzeichnis examples, das Sie mit

cd examples

betreten. Dort finden Sie eine Reihe von Dateien, die diverse Themen der Lehrveranstaltung illustrieren. Sie können sich mit make diverse generierte Dateien erzeugen lassen, im Folgenden werden die Befehle, um die Dateien zu erzeugen, trotzdem gezeigt, daneben aber auch noch die Befehle, um sich dann etwas anzeigen zu lassen.

Disassemblieren von `.class`-Dateien

javac Example.java     # .class-file erzeugen
javap -c Example.class # .class-file disassemblieren
javap -v Example.class # liefert mehr Informationen

Java-Beispiele: Example.java Example2.java

Gforth decompilieren/disassemblieren:

Gforth mit gforth oder gforth-fast starten, Quellcode von z.b.

: square ( n -- n² ) dup * ;
see-code square

reinpasten, und dann:

see square        \ nahe am Quellcode
simple-see square \ eher Richtung VM Disassembler
see-code square   \ Disassembliert VM code und native code

Interpreter dispatch

Das zugehörige .o-File mit z.B. make switch.o erzeugen und mit objdump -d switch.o disassemblieren.

Code copying, stack caching, VM Superinstructions

gforth-fast aufrufen und z.B.:

: square ( n -- n² ) dup * ;
see-code square

gforth-fast --ss-number=0 --ss-states=1 --opt-ip-updates=0 --no-super hat code copying, aber der kopierte Code entspricht dem vollständigen Original (inkl. dispatch):

--ss-number=0 schaltet statische VM superinstructions aus.
--ss-states=1 schaltet stack caching aus.
--opt-ip-updates=0 scahltet die IP-Update-Optimierung aus.
--no-super kopiert den dispatch-code immer mit.

gforth-fast --ss-number=0 --ss-states=1 --opt-ip-updates=0 wäre normales code copying (Dispatch wird weggelassen, wenn der VM-Befehl kein VM-Kontrollflussbefehl ist).

Jetzt können Sie andere Optionen weglassen, um die entsprechende Optimierung einzuschalten.

Den Effekt von static VM superinstructions bei Abwesenheit von stack caching sehen Sie schön an der Definition

: square {: n -- n^2 :} n n * ;

wenn Sie sich den Code anschauen, den gforth-fast --ss-number=0 --ss-states=1 erzeugt, und mit dem vergleichen, den gforth-fast --ss-states=1 erzeugt (die VM superinstruction ist dabei die erste: >l @local0; in der nächsten Zeile steht dann auch noch der VM-Befehl des zweiten Befehls der VM superinstruction, also @local0, aber der ist Teil der VM superinstruction).

Dass stack caching dabei auch in diesem Fall einen Teil des Vorteils von VM superinstructions vorwegnimmt (also VM superinstructions weniger lohnend macht), sieht man, wenn man den Code, der von den oben genannten Gforth-Varianten ausgegeben wird, mit dem vergleicht, was herauskommt, wenn man --ss-states=1 weglässt.

Register VMs vs. stack caching

C-Code für die Implementierung einiger VM-Befehle, und der zugehörige Assemblercode, erzeugt mit clang -O2 -Wall -S

stack-caching.c und stack-caching.s. minus00 minus11 minus44 wären die Implementierungen von minus in single-state stack caching mit 0 (minus00), 1 (minus11), bzw. 4 (minus44) stack items in Registern.

minus01 ist die Implementierung von minus, bei der der Stack-Zustand von 0 Items in Registern zu 1 Item in Registern übergeht. Entsprechend für minus21. Idealerweise wird bei multi-state stack caching öfter minus21 verwendet als eine der anderen Varianten (minus11 steht z.B. bei gforth-fast auch zur Verfügung, wird aber selten gewählt).
register.c und register.s. Eine Register-VM-Implementierung, bei der r0-r2 in realen Registern liegen und die VM-Register ab r3 im Speicher, mit spezialisierten Befehlen für Zugriffe auf r0-r5. add_general zeigt den allgemeinen Fall (funktioniert aber nicht fü Zugriffe auf r0-r2). add_r3_r4_r5 zeigt einen spezialisierten Fall, bei dem die Operanden im Speicher der realen Maschine liegen, und add_r0_r1_r2 zeigt einen Spezialfall, bei dem alle Operanden in Registern der realen Maschine liegen.

Dalvik

Auf der Übungsmaschine g0 ist dalvik-exchange installiert (das ansonsten üblicherweise dx heißt, aber auf Debian war der Name schon belegt, also wird es dalvik-exchange genannt).

Das installierte dalvik-exchange weigert sich, .class-files zu verarbeiten, die für eine neuere Java-Release gebaut wurden als 9. Daher hier eine mögliche Verwendung:

javac --release 9 Example.java
dalvik-exchange --dex --output=Example.dex --dump-to=Example.dexdump Example.class

Dabei erzeugt dieser Aufruf von dalvik-exchange eine .dex-Datei (also das, was eine Dalvik-VM-Implementierung als Input verwenden würde) und eine menschenlesbare Beschreibung des Inhalts der .dex-Datei (insbesondere auch des Dalvik-VM codes) in der Datei Example.dexdump. Sie können auch die --output-Option weglassen, dann funktioniert --dump-to trotzdem, und umgekehrt.

Kosten von Boxing in Java

Boxing1.java Berechnung mit long (unboxed).
Boxing2.java Berechnung mit Long (boxed).

Geschwindigkeitsmessungen mit

javac Boxing1.java Boxing2.java
# mit JIT compiler
time java Boxing1
time java Boxing2
# mit Interpreter
time java -Xint Boxing1
time java -Xint Boxing2

Webassembly

Compilieren von C oder C++ nach Webassembly:

clang -Os -Wall -fno-inline-functions --target=wasm64 -c Example2.c -o Example2.wasm

Das -fno-inline-functions ist da, damit man in unserem Beispiel sehen kann, wie Aufrufe funktionieren; kann man auch weglassen, wenn man das nicht sehen will. Das -Os sorgt für relativ kompakten Code. Ohne -O bläht das Halten von lokalen Variablen im Speicher den Code auf, mit -O2 oder -O3 das loop unrolling.

Man kann auch code für wasm32 erzeugen lassen.

Disassemblieren von Webassembly:

wasm-objdump -d Example2.wasm

VMGen

Bauen eines Compilers in eine VM (mit sofortiger Ausführung) für die Mini-Sprache aus dem Anhang des Compilerbau-Skriptums:

cd vmgen-ex
make        # Details siehe ausgeführte Kommandos oder Makefile
make check  # funktioniert es?

Danach ein Beispielprogramm laufen lassen:

time ./mini fib.mini

Das VM-Programm nach dem Compilieren disassemblieren, danach laufen lassen:

./mini -d fib.mini

Einen Trace des VM-Programms beim Laufen anzeigen lassen:

./mini -d fib.mini

Und alle Befehlssequenzen (ohne Einsprünge und mit Sprüngen nur am Schluss) mit Ausführungsfrequenzen bei diesem Lauf anzeigen lassen, und dann alle in statische Superinstructions verwandeln:

./mini -p fib.mini
# anzeigen lassen
#  die Zahlen sind dynamische Ausführungen der konkreten Befehlssequenz
#  dieselbe Sequenz kann auch anderswo vorkommen
# eine Statistik über die Sequenzen aus mehreren Runs verschiedener Programme
awk -f stat.awk <(./mini -p fib.mini 2>&1 >/dev/null) <(./mini -p test.mini 2>&1 >/dev/null)
#  die erste Spalte  sagt, in wievielen Runs die Sequenz vorgekommen ist
#  die zweite Spalte ist die statische Häufigkeit der Sequenz
#  die dritte Spalte ist die dynamische Häufigkeit der Sequenz
# Jetzt kann man anhand dessen diverse Sequenzen auswaehlen, z.B. alle
#  Sequenzen, die in fib.mini und test.mini vorkommen, und die dann
#  in statische superinstructions umwandeln:
awk -f stat.awk <(./mini -p fib.mini 2>&1 >/dev/null) <(./mini -p test.mini 2>&1 >/dev/null) |
     awk '$1>1' |          #Auswahl
     awk -f seq2rule.awk | #Umwandeln
     sort >mini-super.vmg
# und jetzt mini mit diesen statischen Superinstructions bauen
make  # mini mit den neuen Superinstructions bauen
./mini -d fib.mini # disassemblieren
perf stat ./mini fib.mini  # Performance messen
# oder man nimmt einfach alle, die in fib.mini vorkommen, und verwandelt sie in superinstructions:
./mini -p fib.mini 2>&1 >/dev/null |
     awk -f stat.awk |
     awk -f seq2rule.awk | #Umwandeln
     sort >mini-super.vmg
make  # mini mit den neuen Superinstructions bauen
./mini -d fib.mini # disassemblieren
perf stat ./mini fib.mini  #Performance messen
# ganz ohne statische superinstructions:
echo >mini-super.vmg
make
perf stat ./mini fib.mini

Wobei die Verwendung genau der Superinstructions, die als Sequenzen im Programm vorkommen, nicht realistisch für die übliche Verwendung ist, sondern zeigt, welcher Speedup mit den statischen Superinstructions (zumindest bei dieser Anwendung) im besten Fall erreichbar ist.

Bei der verwendeten Art, wie der Compiler Befehle zu Superinstructions zusammenbaut, muss es für eine superinstruction

a_b_c_ = a b c

auch eine Superinstruction für a b geben (aber nicht für b c), sonst wird a_b_c_ nie erzeugt. Aus mini -p kommen alle Untersequenzen heraus, inkl. in diesem Fall b c. Im Fall der Optimierung genau auf fib.mini hin könnte man die entfernen, aber im Allgemeinen kommen kürzere Sequenzen an mehr Stellen vor als längere, wenn man also die längere zu einer Superinstruction macht, ist es meist auch sinnvoll, alle Untersequenzen zu Superinstructions zu machen.

Name	Last modified	Size

Parent Directory		-
Boxing1.class	2026-06-09 15:18	518
Boxing1.java	2026-04-15 12:13	290
Boxing2.class	2026-06-09 15:18	707
Boxing2.java	2026-04-15 12:11	379
Example.class	2026-06-09 15:18	326
Example.dex	2026-06-09 15:18	636
Example.dexdump	2026-06-09 15:18	15K
Example.java	2026-03-12 13:51	185
Example2.c	2026-04-21 16:37	261
Example2.class	2026-06-09 15:18	421
Example2.dex	2026-06-09 15:18	696
Example2.dexdump	2026-06-09 15:18	16K
Example2.java	2026-03-12 14:10	195
Example2.wasm	2026-06-09 15:18	569
Example2.wat	2026-06-09 15:18	3.5K
Makefile	2026-06-09 12:18	1.7K
call.c	2026-03-19 10:25	170
call.o	2026-06-09 15:18	1.4K
code-copying.S	2026-03-25 13:24	1.2K
code-copying.c	2026-03-25 13:24	666
code-copying.o	2026-06-09 15:18	1.6K
code-copying.s	2026-06-09 15:18	1.2K
dalvik.c	2026-04-07 13:43	547
dalvik.s	2026-06-09 15:18	1.2K
dtc-tc.c	2026-03-20 15:18	423
dtc-tc.o	2026-06-09 15:18	960
dtc.c	2026-03-20 12:44	610
dtc.o	2026-06-09 15:18	1.7K
dtc.s	2026-03-19 13:45	1.2K
examples.tar.xz	2026-06-09 16:54	16K
examples/	2026-06-09 16:54	-
itc.c	2026-03-20 12:44	637
itc.o	2026-06-09 15:18	1.8K
register.c	2026-05-28 15:35	1.0K
register.s	2026-06-09 15:18	1.6K
stack-caching.c	2026-03-30 14:58	1.1K
stack-caching.s	2026-06-09 15:18	2.3K
stack-multi.c	2026-03-31 14:37	655
stack-multi.s	2026-06-09 15:18	1.4K
switch.c	2026-03-12 17:17	497
switch.o	2026-06-09 15:18	1.8K
vmgen-ex/	2026-06-09 14:49	-

Apache/2.4.67 (Debian) OpenSSL/3.0.18 Server at www.complang.tuwien.ac.at Port 443