KAL
Menu

Mengapa IR

Kode tiga alamat dan pemisahan front end dari back end melalui representasi antara.

Daftar isi

Topik ini membahas alasan compiler memakai representasi antara (intermediate representation, IR), yaitu bentuk tengah antara pohon sintaks yang dihasilkan front end dan kode yang dibangkitkan back end. Pembaca memperoleh kontrak IR tiga alamat berupa dataclass IRInstr yang menjadi masukan modul codegen dan modul optimasi, serta pembangkit IRGen yang menerjemahkan AST ekspresi menjadi deret instruksi tiga alamat. Setelah membaca topik ini, pembaca dapat menjelaskan pemisahan front end dan back end, serta melacak bagaimana sebuah pohon ekspresi diturunkan menjadi deret instruksi yang linier.

Front end dan back end memerlukan batas bersama#

Compiler yang besar ditulis sebagai dua bagian yang berbatasan. Front end bertugas mengubah kode sumber menjadi pohon sintaks abstrak, melakukan analisis semantik, lalu menyerahkan hasilnya ke sebuah bentuk data yang netral. Back end menerima bentuk netral tersebut dan menerjemahkannya menjadi kode mesin sasaran, baik itu bytecode stack VM, kode register native, atau LLVM IR. Bentuk netral yang menjadi batas kedua bagian itulah yang disebut IR.

Alasan utama pemakaian IR adalah kombinatorika pasangan bahasa dan mesin sasaran. Tanpa IR, setiap bahasa memerlukan back end sendiri untuk setiap mesin sasaran. Bila ada lima bahasa dan empat mesin sasaran, dibutuhkan dua puluh pasang front end dan back end. Dengan IR, hanya lima front end menuju IR dan empat back end dari IR yang perlu dibangun, sehingga jumlah pasangan turun dari N dikali M menjadi N ditambah M. IR memang menambahkan satu tahap pada pipeline, tetapi penghematan implementasi jauh lebih besar daripada biaya tahap tambahan tersebut.

IR juga membuka pintu optimasi yang tidak bergantung pada sumber maupun sasaran. Karena IR berbentuk yang cukup dekat dengan mesin abstrak, pass optimasi dapat bekerja pada satu representasi untuk seluruh bahasa dan seluruh sasaran. Pass constant folding pada topik ini dan liveness analysis serta inlining pada modul optimasi semuanya didefinisikan terhadap IR yang sama. Front end dan back end tidak perlu tahu satu sama lain secara langsung. Keduanya hanya mengikat diri pada kontrak IR.

Kode tiga alamat sebagai IR klasik#

Bentuk IR yang paling mudah dipelajari adalah kode tiga alamat. Setiap instruksi berbentuk dst = a op b, di mana dst, a, dan b adalah tiga alamat (nama temp, nama variabel, atau literal), dan op adalah satu operator. Karena paling banyak dua operand per instruksi, ekspresi berlapis seperti a + b * c diturunkan menjadi dua instruksi:

text Contoh: ekspresi berlapis menjadi dua instruksi 
t1 = b * c
t2 = a + t1

Pemecahan ekspresi menjadi instruksi pendek memberi tiga manfaat. Pertama, setiap instruksi dapat dihitung, dipindah, atau disesuaikan satu per satu tanpa menyentuh yang lain, sehingga pass optimasi memiliki ruang kerja yang kecil dan dapat dianalisis secara lokal. Kedua, kode tiga alamat menyerupai instruksi mesin register dengan tiga operand, sehingga tahap codegen cukup memetakan setiap instruksi IR ke satu atau dua instruksi mesin. Ketiga, banyak buku teks compiler memakai kode tiga alamat sebagai notasi standar, sehingga pembaca dapat membaca literatur tanpa terjemahan.

Kontrak IR pada jalur ini ditetapkan sebagai dataclass IRInstr(op, dst, args). Field op menyimpan operator, yaitu +, -, *, atau / untuk aritmetika, const untuk literal tunggal, dan copy untuk alias antar temp. Field dst adalah temp tujuan, sedangkan args adalah daftar operand sebagai string, yaitu nama variabel, nama temp, atau repr literal numerik. Bentuk dataclass ini sengaja dipertahankan stabil karena dipakai ulang oleh modul codegen dan modul optimasi.

Membangun IR dari AST#

Pembangkitan IR dilakukan dengan menelusuri pohon ekspresi secara rekursif. Untuk setiap node Binary, kedua operand diturunkan lebih dahulu. Bila operand adalah literal, namanya adalah repr nilai. Bila operand adalah variabel, namanya adalah nama variabel itu sendiri. Bila operand adalah Binary lain, nama operand adalah temp baru yang dibuat oleh instruksi IR untuk Binary tersebut. Node Grouping ditembus langsung karena urutan evaluasi sudah ditentukan oleh struktur pohon, bukan oleh tanda kurung.

Berkas three_address.py berisi pembangkit tersebut. Kelas IRGen menyimpan daftar instruksi dan penghitung temp. Setiap pemanggilan gen_expr mengembalikan nama operand yang dipakai oleh pemanggilnya, sehingga rekursi menyambungkan instruksi induk dengan instruksi anak.

python three_address.py 
"""Pembangun IR tiga alamat dari AST ekspresi bahasa mini v1.

Kontrak IR (dipakai ulang oleh modul 5 codegen dan modul 7 optimasi):

    @dataclass
    class IRInstr:
        op: str           # "+", "-", "*", "/" untuk aritmetika;
                          # "const" untuk literal tunggal; "copy" untuk alias
        dst: str          # nama temp tujuan, mis. "t1"
        args: list[str]   # operand: nama variabel atau repr literal

Literal direpr sebagai string nilainya (mis. "1", "2.5"); variabel
direpr sebagai namanya. Temp baru dibuat untuk tiap Binary sehingga
paling banyak dua operand per instruksi, yang merupakan inti kode tiga
alamat. Grouping ditembus langsung ke inner-nya karena urutan evaluasi
sudah ditentukan oleh struktur pohon, bukan oleh tanda kurung.
"""
from dataclasses import dataclass, field
from typing import Any


# ----- AST (kanonis dari topik desain-ast, salinan ringkas) -----
@dataclass
class Expr:
    """Akar hierarki ekspresi."""


@dataclass
class Binary(Expr):
    left: Expr
    op: str
    right: Expr


@dataclass
class Literal(Expr):
    value: Any


@dataclass
class Variable(Expr):
    name: str


@dataclass
class Grouping(Expr):
    expression: Expr


# ----- IR -----
@dataclass
class IRInstr:
    op: str
    dst: str
    args: list[str] = field(default_factory=list)


class IRGen:
    """Pembangun IR tiga alamat dari ekspresi."""

    def __init__(self) -> None:
        self.instrs: list[IRInstr] = []
        self._n = 0

    def _new_temp(self) -> str:
        self._n += 1
        return f"t{self._n}"

    def gen_expr(self, e: Expr) -> str:
        """Kembalikan nama operand: repr literal, nama variabel, atau temp."""
        if isinstance(e, Literal):
            return repr(e.value)
        if isinstance(e, Variable):
            return e.name
        if isinstance(e, Grouping):
            return self.gen_expr(e.expression)
        if isinstance(e, Binary):
            left = self.gen_expr(e.left)
            right = self.gen_expr(e.right)
            dst = self._new_temp()
            self.instrs.append(IRInstr(op=e.op, dst=dst, args=[left, right]))
            return dst
        raise TypeError(f"node tidak didukung: {type(e).__name__}")


def format_ir(instrs: list[IRInstr]) -> str:
    """Cetak IR sebagai baris `dst = a op b` (atau `dst = a` untuk const/copy)."""
    lines: list[str] = []
    for i in instrs:
        if i.op in ("const", "copy"):
            lines.append(f"{i.dst} = {i.args[0]}")
        else:
            lines.append(f"{i.dst} = {i.args[0]} {i.op} {i.args[1]}")
    return "\n".join(lines)


def main() -> None:
    # AST untuk ekspresi (1 + 2) * 3.
    ast = Binary(
        left=Grouping(
            expression=Binary(left=Literal(1), op="+", right=Literal(2)),
        ),
        op="*",
        right=Literal(3),
    )
    gen = IRGen()
    root = gen.gen_expr(ast)
    print(f"akar (operand akhir): {root}")
    print(format_ir(gen.instrs))


if __name__ == "__main__":
    main()

Program utama membangun AST untuk ekspresi (1 + 2) * 3 dan mencetak IR yang dibangkitkan. Operand akhir disimpan dalam t2 karena pohonnya memiliki dua Binary, sehingga dua temp dibuat. Keluaran berikut diperoleh dengan menjalankan python3 three_address.py.

text Keluaran 
akar (operand akhir): t2
t1 = 1 + 2
t2 = t1 * 3

Keluaran menunjukkan transformasi yang khas. Pohon Binary('*', Binary('+', 1, 2), 3) diturunkan menjadi dua baris lurus. Subekspresi (1 + 2) dievaluasi lebih dahulu sebagai t1 = 1 + 2, lalu hasilnya t1 dipakai sebagai operand kiri pada t2 = t1 * 3. Struktur pohon hilang dan digantikan oleh deret instruksi yang linier, yang merupakan bentuk yang diharapkan back end.

Ringkasan#

  • IR adalah batas bersama antara front end dan back end, yang mengubah pasangan N dikali M menjadi N ditambah M.
  • Kode tiga alamat adalah IR klasik berbentuk dst = a op b yang paling banyak memuat dua operand per instruksi.
  • Kontrak IR pada jalur ini ditetapkan sebagai IRInstr(op, dst, args), dengan op aritmetika, const, atau copy.
  • Pembangkitan IR dilakukan dengan menelusuri AST rekursif. Setiap Binary menjadi satu instruksi yang menghasilkan temp baru.

Referensi#