KAL
Menu

Target: Stack VM

Desain set instruksi untuk stack VM yang menjadi sasaran codegen proyek kursus.

Daftar isi

Topik ini menetapkan set instruksi untuk mesin sasaran berbasis stack yang menjadi sasaran codegen sepanjang modul ini. Pembaca memperoleh enumerasi opcode sebagai IntEnum, tabel dokumentasi yang menyatakan stack effect dan semantik tiap opcode, serta konvensi penyandian bytecode sebagai list[tuple[str, ...]]. Setelah membaca topik ini, pembaca dapat menyebutkan seluruh opcode stack VM, menjelaskan perbedaan instruksi aritmetika, komparasi, dan kontrol alur, serta membaca bytecode yang dihasilkan codegen.

Stack VM sebagai sasaran codegen#

Pilihan sasaran codegen menentukan bentuk keluaran back end. Pada jalur ini, codegen menargetkan mesin sasaran berbasis stack, yaitu mesin yang menyimpan operand sementara pada sebuah tumpukan dan menyebut operand secara implisit lewat puncak tumpukan tersebut. Instruksi ADD tidak menyebut nama register, melainkan mengambil dua nilai dari puncak tumpukan, menghitung jumlahnya, lalu mendorong hasil itu kembali. Akibatnya, satu instruksi cukup disandikan sebagai opcode tanpa operand, sehingga bytecode menjadi ringkas.

Alasan utama pemakaian model stack adalah kesederhanaan codegen. Karena urutan instruksi pada mesin stack sama dengan urutan evaluasi pohon ekspresi, codegen cukup menelusuri AST secara post-order: kunjungi anak kiri, kunjungi anak kanan, lalu keluarkan opcode operator. Tidak diperlukan alokasi register, sehingga pass alokasi register yang menjadi beban modul optimasi dapat ditunda. Sebagian besar bytecode portabel produksi, termasuk JVM bytecode dan WebAssembly, mengikuti model yang sama persis untuk alasan ini.

Set instruksi yang ditetapkan di sini mencakup lima belas opcode fungsional ditambah satu pseudo-instruksi LABEL. Kelompok pertama adalah instruksi aritmetika ADD, SUB, MUL, dan DIV yang masing-masing mengambil dua puncak tumpukan, menghitung hasil a OP b dengan a berada di bawah b, lalu mendorong hasilnya. Kelompok kedua adalah komparasi EQ, LT, dan GT yang menghasilkan bool. Kelompok ketiga adalah kontrol alur JUMP dan JUMP_IF_FALSE, sedangkan kelompok terakhir adalah akses lingkungan STORE dan LOAD, lalu PUSH, POP, dan PRINT.

Tabel set instruksi#

Tabel berikut merangkum mnemonic, stack effect, dan semantik tiap opcode. Stack effect menyatakan perubahan kedalaman tumpukan setelah instruksi dijalankan, dengan +1 berarti menambah satu elemen, -1 berarti mengurangi satu, dan 0 berarti tetap.

OpcodeMnemonicStackSemantik
PUSHPUSH x+1dorong nilai literal x ke puncak stack
POPPOP-1buang elemen puncak stack
ADDADD-1pop dua (a di bawah b), dorong a + b
SUBSUB-1pop dua (a di bawah b), dorong a - b
MULMUL-1pop dua (a di bawah b), dorong a * b
DIVDIV-1pop dua (a di bawah b), dorong a / b
EQEQ-1pop dua, dorong bool (a == b)
LTLT-1pop dua, dorong bool (a < b)
GTGT-1pop dua, dorong bool (a > b)
NOTNOT0pop satu, dorong bool negasinya
JUMPJUMP lbl0lompat ke label lbl
JUMP_IF_FALSEJUMP_IF_FALSE lbl-1pop satu, lompat ke lbl bila falsy
STORESTORE name-1pop satu, simpan ke env[name]
LOADLOAD name+1dorong env[name] ke puncak stack
PRINTPRINT-1pop satu, cetak ke stdout
LABELLABEL name0penanda posisi lompatan (pseudo)

Konvensi a di bawah b pada ADD, SUB, MUL, dan DIV krusial karena urutan operand menentukan hasil untuk operasi nonkomutatif. Bila codegen membangkitkan a - b, urutan yang benar adalah mengevaluasi a lebih dahulu sehingga a berada di bawah, lalu mengevaluasi b sehingga b berada di puncak, baru SUB dipanggil. Jika urutan terbalik, hasil menjadi b - a tanpa pesan error apa pun. Demikian pula DIV untuk pembagian dan LT atau GT untuk komparasi. Codegen bertanggung jawab menjaga urutan ini, sedangkan VM hanya mengikuti urutan pop yang ditetapkan.

Pseudo-instruksi LABEL bukan opcode fungsional. Tugas LABEL hanya menandai posisi di bytecode yang menjadi sasaran JUMP dan JUMP_IF_FALSE. Pendekatan ini dipakai agar bytecode tetap dapat dibaca manusia: lompatan menyebut nama label seperti L_end_1 alih-alih indeks numerik yang harus dihitung ulang setiap kali instruksi di depannya berubah. Interpreter membangun pemetaan nama label ke indeks instruksi pada satu pass awal, kemudian mengganti nama label dengan indeks saat eksekusi.

Konvensi penyandian bytecode#

Bytecode disimpan sebagai list[tuple[str, ...]]. Setiap instruksi adalah sebuah tuple dengan elemen pertama berupa nama opcode sebagai string, diikuti operand bila ada. Instruksi tanpa operand direpresentasikan sebagai tuple satu elemen, sedangkan instruksi dengan operand direpresentasikan sebagai tuple dua atau tiga elemen. Contoh bytecode untuk program let x = 1 + 2; print x; adalah [("PUSH", 1), ("PUSH", 2), ("ADD",), ("STORE", "x"), ("LOAD", "x"), ("PRINT",)].

Berkas vm_spec.py berisi enumerasi opcode sebagai IntEnum dan tabel dokumentasi yang menjadi kontrak codegen dan interpreter VM. Enumerasi sebagai IntEnum memberi dua keuntungan: nama opcode dapat dirujuk sebagai Opcode.PUSH sehingga codegen terhindar dari salah ketik string, dan nilai integer tersedia bila bytecode perlu disandikan ke format biner pada modul lanjutan.

python vm_spec.py 
"""Spesifikasi set instruksi stack VM sebagai sasaran codegen.

Kontrak set instruksi (dipakai ulang oleh codegen dan interpreter VM):

    PUSH x          dorong nilai literal x ke puncak stack
    POP             buang elemen puncak
    ADD SUB MUL DIV pop dua (a di bawah b), dorong hasil a OP b
    EQ LT GT        pop dua, dorong bool hasil komparasi a OP b
    NOT             pop satu, dorong bool negasinya
    JUMP lbl        lompat ke label lbl
    JUMP_IF_FALSE lbl  pop satu, lompat ke lbl bila falsy
    STORE name      pop satu, simpan ke env[name]
    LOAD name       dorong env[name]
    PRINT           pop satu, cetak ke stdout
    LABEL name      penanda posisi lompatan (pseudo-instruksi)

Bytecode disimpan sebagai list[tuple[str, ...]], mis.:

    [("PUSH", 1), ("PUSH", 2), ("ADD",), ("STORE", "x"),
     ("LOAD", "x"), ("PRINT",)]

Pseudo-instruksi LABEL menandai posisi lompatan; ia dievaluasi sebagai
no-op oleh interpreter, tetapi dipakai oleh pass resolusi label untuk
membangun pemetaan nama label ke indeks instruksi. Pemakaian LABEL
menjaga bytecode tetap dapat dibaca manusia dan menghindari dua pass
backpatching pada codegen.
"""

from enum import IntEnum


class Opcode(IntEnum):
    """Enumerasi opcode stack VM beserta pseudo-instruksi LABEL."""

    PUSH = 1
    POP = 2
    ADD = 3
    SUB = 4
    MUL = 5
    DIV = 6
    EQ = 7
    LT = 8
    GT = 9
    NOT = 10
    JUMP = 11
    JUMP_IF_FALSE = 12
    STORE = 13
    LOAD = 14
    PRINT = 15
    LABEL = 16  # pseudo-instruksi: penanda posisi lompatan


# Tabel dokumentasi: mnemonic, stack effect (perubahan kedalaman), semantik.
SPEC: dict[str, tuple[str, str, str]] = {
    "PUSH":          ("PUSH x",          "+1", "dorong nilai literal x ke puncak stack"),
    "POP":           ("POP",             "-1", "buang elemen puncak stack"),
    "ADD":           ("ADD",             "-1", "pop dua (a di bawah b), dorong a + b"),
    "SUB":           ("SUB",             "-1", "pop dua (a di bawah b), dorong a - b"),
    "MUL":           ("MUL",             "-1", "pop dua (a di bawah b), dorong a * b"),
    "DIV":           ("DIV",             "-1", "pop dua (a di bawah b), dorong a / b"),
    "EQ":            ("EQ",              "-1", "pop dua, dorong bool (a == b)"),
    "LT":            ("LT",              "-1", "pop dua, dorong bool (a < b)"),
    "GT":            ("GT",              "-1", "pop dua, dorong bool (a > b)"),
    "NOT":           ("NOT",             "0",  "pop satu, dorong bool negasinya"),
    "JUMP":          ("JUMP lbl",        "0",  "lompat ke label lbl"),
    "JUMP_IF_FALSE": ("JUMP_IF_FALSE lbl", "-1", "pop satu, lompat ke lbl bila falsy"),
    "STORE":         ("STORE name",      "-1", "pop satu, simpan ke env[name]"),
    "LOAD":          ("LOAD name",       "+1", "dorong env[name] ke puncak stack"),
    "PRINT":         ("PRINT",           "-1", "pop satu, cetak ke stdout"),
    "LABEL":         ("LABEL name",      "0",  "penanda posisi lompatan (pseudo)"),
}


def main() -> None:
    print("=== Set instruksi stack VM ===")
    print(f"{'opcode':<16} {'mnemonic':<20} {'stack':<6} semantik")
    print("-" * 76)
    for op in Opcode:
        mnemonic, stack, sem = SPEC[op.name]
        print(f"{op.name:<16} {mnemonic:<20} {stack:<6} {sem}")
    print()
    print("=== Konfigurasi awal VM ===")
    print("stack   : []")
    print("env     : {}")
    print("pc      : 0")
    print("instr   : list[tuple[str, ...]]")
    print(f"opcode  : {len(Opcode)} buah (PUSH .. LABEL)")


if __name__ == "__main__":
    main()

Program utama mencetak tabel set instruksi dan konfigurasi awal VM. Konfigurasi awal menyatakan bahwa stack dimulai kosong, env dimulai kosong, program counter pc dimulai pada indeks nol, dan instr disimpan sebagai list tuple. Keluaran berikut diperoleh dengan menjalankan python3 vm_spec.py.

text Keluaran 
=== Set instruksi stack VM ===
opcode           mnemonic             stack  semantik
----------------------------------------------------------------------------
PUSH             PUSH x               +1     dorong nilai literal x ke puncak stack
POP              POP                  -1     buang elemen puncak stack
ADD              ADD                  -1     pop dua (a di bawah b), dorong a + b
SUB              SUB                  -1     pop dua (a di bawah b), dorong a - b
MUL              MUL                  -1     pop dua (a di bawah b), dorong a * b
DIV              DIV                  -1     pop dua (a di bawah b), dorong a / b
EQ               EQ                   -1     pop dua, dorong bool (a == b)
LT               LT                   -1     pop dua, dorong bool (a < b)
GT               GT                   -1     pop dua, dorong bool (a > b)
NOT              NOT                  0      pop satu, dorong bool negasinya
JUMP             JUMP lbl             0      lompat ke label lbl
JUMP_IF_FALSE    JUMP_IF_FALSE lbl    -1     pop satu, lompat ke lbl bila falsy
STORE            STORE name           -1     pop satu, simpan ke env[name]
LOAD             LOAD name            +1     dorong env[name] ke puncak stack
PRINT            PRINT                -1     pop satu, cetak ke stdout
LABEL            LABEL name           0      penanda posisi lompatan (pseudo)

=== Konfigurasi awal VM ===
stack   : []
env     : {}
pc      : 0
instr   : list[tuple[str, ...]]
opcode  : 16 buah (PUSH .. LABEL)

Keluaran memperlihatkan dua kelompok informasi. Bagian pertama adalah tabel set instruksi yang menjadi kontrak codegen dan interpreter VM, sedangkan bagian kedua adalah konfigurasi awal yang menjadi titik mula eksekusi. Lima belas opcode fungsional ditambah satu pseudo-instruksi LABEL menjadi himpunan lengkap yang dipakai sepanjang modul ini. Codegen membangkitkan hanya instruksi dari himpunan ini, sedangkan interpreter VM hanya mengenali opcode dari himpunan yang sama, sehingga kontrak set instruksi menjadi sumber kebenaran bagi keduanya.

Ringkasan#

  • Codegen pada jalur ini menargetkan mesin stack karena urutan instruksi sama dengan urutan evaluasi pohon, sehingga pass alokasi register dapat ditunda.
  • Set instruksi mencakup PUSH, POP, ADD, SUB, MUL, DIV, EQ, LT, GT, NOT, JUMP, JUMP_IF_FALSE, STORE, LOAD, PRINT, ditambah pseudo-instruksi LABEL.
  • Konvensi a di bawah b pada aritmetika dan komparasi menetapkan urutan operand yang menjadi tanggung jawab codegen, bukan VM.
  • Bytecode disimpan sebagai list[tuple[str, ...]], dengan lompatan menyebut nama label alih-alih indeks numerik.

Referensi#