KAL
Menu

Mesin Stack vs Mesin Register

Model mesin sasaran berbasis stack dan register beserta kompromi keduanya.

Daftar isi

Topik ini membahas dua model mesin sasaran yang menjadi tujuan akhir codegen, yaitu mesin berbasis stack dan mesin berbasis register. Pembaca memperoleh dua simulator mini, StackMachine dan RegisterMachine, yang masing-masing memiliki metode execute(instrs) untuk menjalankan deret instruksi pada ekspresi yang sama. Setelah membaca topik ini, pembaca dapat menjelaskan kompromi antara pendek dengan operand implisit (stack) dan pendek dengan operand eksplisit (register), serta memahami set instruksi stack VM yang menjadi sasaran codegen.

Dua model mesin sasaran#

Mesin stack menyimpan operand sementara pada sebuah tumpukan. Instruksi aritmetika tidak menyebut operand secara eksplisit. Instruksinya mengambil dua nilai dari puncak tumpukan, menghitung hasilnya, lalu mendorong hasil itu kembali. Instruksi ADD hanya terdiri atas opcode tanpa argumen, sehingga satu byte pada bytecode sudah cukup. Akibatnya, bytecode stack VM sangat ringkas, tetapi urutan instruksi harus benar agar puncak tumpukan selalu berisi nilai yang diharapkan instruksi berikutnya.

Mesin register menyimpan operand pada sekumpulan register bernama. Instruksi aritmetika menyebut register tujuan dan satu atau dua register sumber secara eksplisit, misalnya ADD r1 r1 r2. Instruksi menjadi lebih panjang karena opcode harus diikuti nama register, tetapi urutan pemakaian register fleksibel, dan satu instruksi dapat langsung menggabungkan dua register yang berbeda tanpa operasi salin. Sebagian besar mesin native modern, seperti x86-64 dan ARM, termasuk kategori ini.

Pilihan model menentukan bentuk codegen, ukuran kode, dan kompleksitas interpreter. Pada compiler yang menargetkan bytecode portabel, model stack dipakai karena ringkas dan tidak bergantung pada jumlah register fisik. Pada compiler yang menargetkan mesin native, model register dipakai karena sesuai dengan ISA sasaran dan memudahkan alokasi register nyata pada tahap akhir.

Perbandingan kedua model#

Tabel berikut merangkum perbedaan kedua model pada empat aspek yang berpengaruh pada codegen.

AspekMesin stackMesin register
OperandImplisit, diambil dari puncak tumpukanEksplisit, disebut pada instruksi
Ukuran instruksiKecil, sering satu opcodeLebih besar, opcode ditambah nama register
UrutanHarus sesuai urutan evaluasi pohonBebas, dapat memilih register mana pun
Contoh sasaranJVM bytecode, WebAssembly, stack VM proyek kursusx86-64, ARM, RISC-V

Kedua model tidak saling menggantikan pada tingkat desain compiler. Codegen ke mesin stack memerlukan urutan instruksi yang persis sama dengan urutan evaluasi pohon, sehingga implementasinya sederhana, yaitu kunjungi anak kiri, kunjungi anak kanan, lalu keluarkan opcode. Codegen ke mesin register memerlukan keputusan alokasi, yaitu register mana yang dipakai untuk tiap temp, sehingga pass alokasi register menjadi tahap tersendiri pada modul optimasi.

Pada jalur ini, codegen menargetkan stack VM. Set instruksi stack yang ditetapkan mencakup PUSH, POP, ADD, SUB, MUL, DIV, EQ, LT, GT, NOT, JUMP, JUMP_IF_FALSE, STORE, LOAD, dan PRINT. Set instruksi ini sengaja diperluas dari yang murni aritmetika agar satu mesin yang sama dapat menjalankan ekspresi, pernyataan let, percabangan, dan perulangan.

Simulasi kedua mesin pada ekspresi yang sama#

Untuk melihat kompromi kedua model secara langsung, ekspresi a + b * c diturunkan ke dua bentuk instruksi. Dengan asumsi a = 2, b = 3, dan c = 4, hasil yang diharapkan adalah 14 pada kedua mesin. Pada mesin stack, ekspresi tersebut menjadi enam instruksi yang masing-masing pendek. Pada mesin register, ekspresi tersebut menjadi enam instruksi pula, tetapi setiap instruksi membawa nama register eksplisit.

Berkas machine_models.py berisi kedua simulator. Kedua kelas menerima env sebagai pemetaan nama variabel ke nilai, dan metode execute(instrs) menjalankan deret instruksi sambil mencetak state pada tiap langkah. Pencetakan state pada tiap langkah membuat kedua model dapat dibandingkan tanpa perlu menelusuri state mesin untuk mengetahui operand sebuah instruksi.

python machine_models.py 
"""Dua simulator mini: StackMachine dan RegisterMachine.

Kontrak set instruksi StackMachine (dipakai ulang oleh modul 5
codegen sebagai sasaran bytecode):

    PUSH x        dorong nilai literal atau variabel x
    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
    NOT           pop satu, dorong bool negasinya
    JUMP lbl      lompat ke label
    JUMP_IF_FALSE lbl  pop satu, lompat bila falsy
    STORE name    pop satu, simpan ke env[name]
    LOAD name     dorong env[name]
    PRINT         pop satu, cetak ke stdout

RegisterMachine memakai set instruksi terpisah dengan operand
eksplisit (LOAD r1 a, ADD r1 r1 r2). Set instruksi register tidak
dipakai sebagai sasaran codegen; keberadaannya di sini semata-mata
untuk membandingkan kedua model secara langsung pada ekspresi yang
sama.
"""


class StackMachine:
    """Mesin sasaran berbasis stack."""

    def __init__(self, env: dict[str, int | float] | None = None) -> None:
        self.env = dict(env or {})

    def _value(self, tok: str) -> int | float:
        if tok in self.env:
            return self.env[tok]
        if tok.lstrip("-").isdigit():
            return int(tok)
        return float(tok)

    def execute(self, instrs: list[str]) -> int | float | None:
        stack: list = []
        printed: list[str] = []
        for line in instrs:
            tok = line.split()
            op = tok[0]
            if op == "PUSH":
                stack.append(self._value(tok[1]))
            elif op == "POP":
                stack.pop()
            elif op in ("ADD", "SUB", "MUL", "DIV"):
                b = stack.pop()
                a = stack.pop()
                if op == "ADD":
                    stack.append(a + b)
                elif op == "SUB":
                    stack.append(a - b)
                elif op == "MUL":
                    stack.append(a * b)
                else:  # DIV
                    if isinstance(a, int) and isinstance(b, int) and a % b == 0:
                        stack.append(a // b)
                    else:
                        stack.append(a / b)
            elif op in ("EQ", "LT", "GT"):
                b = stack.pop()
                a = stack.pop()
                if op == "EQ":
                    stack.append(a == b)
                elif op == "LT":
                    stack.append(a < b)
                else:
                    stack.append(a > b)
            elif op == "NOT":
                a = stack.pop()
                stack.append(not a)
            elif op == "STORE":
                self.env[tok[1]] = stack.pop()
            elif op == "LOAD":
                stack.append(self.env[tok[1]])
            elif op == "PRINT":
                printed.append(str(stack.pop()))
            else:
                raise ValueError(f"opcode tak dikenal: {op}")
            print(f"{line:24s} | stack={stack}")
        for p in printed:
            print(f"= {p}")
        return stack[-1] if stack else None


class RegisterMachine:
    """Mesin sasaran berbasis register."""

    def __init__(self, env: dict[str, int | float] | None = None) -> None:
        self.env = dict(env or {})

    def _value(self, tok: str, regs: dict[str, int | float]) -> int | float:
        if tok in regs:
            return regs[tok]
        if tok in self.env:
            return self.env[tok]
        if tok.lstrip("-").isdigit():
            return int(tok)
        return float(tok)

    def execute(self, instrs: list[str]) -> int | float | None:
        regs: dict[str, int | float] = {}
        printed: list[str] = []
        for line in instrs:
            tok = line.split()
            op = tok[0]
            if op == "LOAD":
                regs[tok[1]] = self._value(tok[2], regs)
            elif op in ("ADD", "SUB", "MUL", "DIV"):
                dst = tok[1]
                a = self._value(tok[2], regs)
                b = self._value(tok[3], regs)
                if op == "ADD":
                    regs[dst] = a + b
                elif op == "SUB":
                    regs[dst] = a - b
                elif op == "MUL":
                    regs[dst] = a * b
                else:  # DIV
                    if isinstance(a, int) and isinstance(b, int) and a % b == 0:
                        regs[dst] = a // b
                    else:
                        regs[dst] = a / b
            elif op == "PRINT":
                printed.append(str(self._value(tok[1], regs)))
            else:
                raise ValueError(f"opcode tak dikenal: {op}")
            print(f"{line:24s} | regs={regs}")
        for p in printed:
            print(f"= {p}")
        return regs.get("r1")


def main() -> None:
    env = {"a": 2, "b": 3, "c": 4}

    # Ekspresi a + b * c pada mesin stack: 2 + (3 * 4) = 14.
    stack_code = [
        "PUSH a",
        "PUSH b",
        "PUSH c",
        "MUL",
        "ADD",
        "PRINT",
    ]
    # Ekspresi yang sama pada mesin register.
    reg_code = [
        "LOAD r1 a",
        "LOAD r2 b",
        "LOAD r3 c",
        "MUL r2 r2 r3",
        "ADD r1 r1 r2",
        "PRINT r1",
    ]

    print("=== StackMachine ===")
    StackMachine(env).execute(stack_code)
    print()
    print("=== RegisterMachine ===")
    RegisterMachine(env).execute(reg_code)


if __name__ == "__main__":
    main()

Program utama memilih env = {a: 2, b: 3, c: 4} agar hasil mudah dihitung ulang, yaitu 2 + 3 * 4 = 14. Pada mesin stack, operand a, b, dan c didorong berturut-turut, lalu MUL menggabungkan dua puncak menjadi 12, dan ADD menggabungkan 2 dengan 12 menjadi 14. Pada mesin register, LOAD mengisi tiga register, MUL r2 r2 r3 menyimpan 12 kembali ke r2, lalu ADD r1 r1 r2 menyimpan 14 ke r1. Kedua mesin berakhir dengan PRINT yang mencetak hasil akhir. Keluaran berikut diperoleh dengan menjalankan python3 machine_models.py.

text Keluaran 
=== StackMachine ===
PUSH a                   | stack=[2]
PUSH b                   | stack=[2, 3]
PUSH c                   | stack=[2, 3, 4]
MUL                      | stack=[2, 12]
ADD                      | stack=[14]
PRINT                    | stack=[]
= 14

=== RegisterMachine ===
LOAD r1 a                | regs={'r1': 2}
LOAD r2 b                | regs={'r1': 2, 'r2': 3}
LOAD r3 c                | regs={'r1': 2, 'r2': 3, 'r3': 4}
MUL r2 r2 r3             | regs={'r1': 2, 'r2': 12, 'r3': 4}
ADD r1 r1 r2             | regs={'r1': 14, 'r2': 12, 'r3': 4}
PRINT r1                 | regs={'r1': 14, 'r2': 12, 'r3': 4}
= 14

Keluaran menunjukkan perbedaan yang khas. Pada mesin stack, panjang instruksi tetap pendek, tetapi tumpukan harus dilacak untuk memahami arti ADD. Pada mesin register, instruksi lebih panjang karena menyebut register, tetapi pemakaian tiap register dapat dibaca langsung dari baris itu tanpa menelusuri state sebelumnya. Kedua mesin menghasilkan 14, yang membuktikan bahwa model stack dan model register setara secara semantik pada ekspresi yang sama.

Ringkasan#

  • Mesin stack menyimpan operand pada tumpukan, dengan instruksi pendek dan urutan yang mengikuti evaluasi pohon.
  • Mesin register menyimpan operand pada register bernama, dengan instruksi yang menyebut register secara eksplisit.
  • Codegen ke mesin stack sederhana karena urutan instruksi sama dengan urutan evaluasi, sedangkan codegen ke mesin register memerlukan alokasi register.
  • Set instruksi stack VM yang menjadi sasaran codegen mencakup PUSH, POP, ADD, SUB, MUL, DIV, EQ, LT, GT, NOT, JUMP, JUMP_IF_FALSE, STORE, LOAD, dan PRINT.

Referensi#