KAL
Menu

Optimasi Dasar

Constant folding dan penyederhanaan aljabar sebagai pass pertama pada IR.

Daftar isi

Topik ini membahas pass optimasi pertama pada IR tiga alamat, yaitu constant folding dan penyederhanaan aljabar. Pembaca memperoleh berkas const_fold.py yang berisi kedua pass tersebut beserta runner yang menjalankan IR untuk ekspresi (2 + 3) * x + 0. Setelah membaca topik ini, pembaca dapat menjelaskan bagaimana instruksi yang operandnya literal dapat dihitung pada waktu kompilasi, serta bagaimana identitas aritmetika menyederhanakan instruksi tanpa mengubah hasilnya.

Pass optimasi pada IR#

Pass optimasi adalah fungsi yang menerima daftar instruksi IR dan mengembalikan daftar instruksi IR yang ekuivalen secara semantik, tetapi lebih ringkas atau lebih cepat. Pada modul ini, dua pass diterapkan berurutan pada IR yang sudah dibangkitkan dari AST. Kedua pass bersifat lokal, yaitu hanya melihat satu instruksi pada satu waktu tanpa menelusuri pemakaian temp antar instruksi. Sifat lokal inilah yang membuat pass pertama mudah dipahami dan menjadi fondasi pass yang lebih global pada modul optimasi.

Pass pertama disebut constant folding. Bila kedua operand sebuah instruksi aritmetika adalah literal numerik, hasil perhitungannya dapat dihitung pada waktu kompilasi. Instruksi t1 = 2 + 3 misalnya, dapat diganti dengan t1 = 5 tanpa menunggu program dijalankan. Pass kedua disebut penyederhanaan aljabar, yang memanfaatkan identitas aritmetika seperti x + 0 = x dan x * 1 = x untuk mengganti instruksi dengan copy atau const yang lebih murah.

Kontrak yang dipakai oleh kedua pass diturunkan langsung dari IRInstr pada topik mengapa-ir. Setelah constant folding, instruksi yang dua operandnya literal diganti menjadi IRInstr(op="const", dst=..., args=[repr(hasil)]). Setelah penyederhanaan aljabar, instruksi x + 0 diganti menjadi IRInstr(op="copy", dst=..., args=["x"]), dan x * 0 diganti menjadi IRInstr(op="const", dst=..., args=["0"]). Operator const dan copy menjadi penanda bahwa instruksi sudah disederhanakan.

Constant folding#

Constant folding bekerja dengan mendeteksi operand literal. Karena args pada IRInstr adalah daftar string, deteksi dilakukan dengan mencoba mengonversi string ke int atau float. Bila konversi berhasil untuk kedua operand, keduanya adalah literal numerik, dan hasil perhitungan dapat dihitung dengan operator yang sesuai. Instruksi t1 = 2 + 3 diganti menjadi t1 = const 5, yang ditampilkan sebagai t1 = 5.

Pass ini berhati-hati pada pembagian. Pada bahasa mini v1, pembagian yang habis pada int menghasilkan int, sedangkan pembagian yang tidak habis atau salah satu operand float menghasilkan float. Aturan itu diterapkan di helper _fold dengan pemeriksaan tipe operand, sehingga 6 / 3 di-fold menjadi 2, sedangkan 7 / 2 di-fold menjadi 3.5. Tanpa aturan ini, pass dapat mengubah tipe hasil dan menyebabkan back end menghasilkan kode yang salah.

Constant folding hanya menyederhanakan instruksi yang kedua operandnya berupa literal. Instruksi seperti t2 = t1 * x tetap utuh karena x adalah variabel runtime yang nilainya belum diketahui. Pass ini dengan demikian tidak mengubah semantik, melainkan memajukan perhitungan yang sebenarnya sudah dapat diselesaikan tanpa menjalankan program.

Penyederhanaan aljabar#

Penyederhanaan aljabar memanfaatkan identitas yang berlaku untuk sembarang nilai. Tiga pola yang ditangani pada topik ini adalah x + 0, x * 1, dan x * 0. Untuk x + 0, instruksi t3 = t2 + 0 diganti menjadi t3 = copy t2, yang ditampilkan sebagai t3 = t2. Untuk x * 1, instruksi diganti menjadi copy operand yang bukan 1. Untuk x * 0, instruksi diganti menjadi t = const 0, yaitu hasilnya selalu nol terlepas dari nilai x.

Pass ini hanya mengganti instruksi yang cocok dengan pola, dan tidak menghapus instruksi yang lain. Instruksi t3 = t2 yang dihasilkan tetap mengikat t3 ke t2, sehingga pemakai t3 di tempat lain masih valid. Penghapusan instruksi mati, yaitu instruksi yang hasilnya tidak pernah dipakai, ditangani oleh pass terpisah pada modul optimasi. Topik ini sengaja hanya melakukan penggantian agar pembaca melihat batas antara pass lokal dan pass global.

Mempraktikkan kedua pass#

Fungsi optimize menjalankan kedua pass berurutan, yaitu const_fold lebih dahulu, baru algebraic. Urutan itu dipilih agar constant folding menggantikan instruksi yang dapat dihitung, sehingga penyederhanaan aljabar dapat melihat lebih banyak pola. Sebagai contoh, instruksi t1 = 2 + 3 diubah menjadi t1 = 5 oleh constant folding, lalu bila ada instruksi t2 = t1 * 1, aljabar akan menggantinya dengan t2 = t1. Kedua pass saling melengkapi, dan keduanya dikemas bersama helper pada berkas const_fold.py, beserta runner yang menyusun IR contoh serta mencetak hasil sebelum dan sesudah optimasi.

python const_fold.py 
"""Pass optimasi dasar pada IR tiga alamat.

Dua pass diterapkan berurutan:

1. Constant folding: instruksi aritmetika dengan dua operand literal
   diganti menjadi instruksi const yang operand tunggalnya adalah
   hasil perhitungan pada waktu kompilasi.
2. Penyederhanaan aljabar: pola yang diketahui identitas aritmetika
   disederhanakan, yaitu x + 0 -> x, x * 1 -> x, dan x * 0 -> 0.

Pass ini tidak menghapus instruksi mati. Penghapusan instruksi yang
hasilnya tidak terpakai ditangani oleh pass kode mati di modul 7
optimasi; pass di sini hanya menimpa instruksi yang dapat disederhanakan
secara lokal tanpa melihat seluruh program.
"""
from dataclasses import dataclass, field


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


def _is_int(s: str) -> bool:
    return s.lstrip("-").isdigit()


def _to_num(s: str) -> int | float:
    return int(s) if _is_int(s) else float(s)


def _is_literal(s: str) -> bool:
    try:
        _to_num(s)
        return True
    except ValueError:
        return False


def _fold(op: str, a: int | float, b: int | float) -> int | float:
    if op == "+":
        return a + b
    if op == "-":
        return a - b
    if op == "*":
        return a * b
    if op == "/":
        if isinstance(a, int) and isinstance(b, int) and a % b == 0:
            return a // b
        return a / b
    raise ValueError(f"operator tidak didukung: {op}")


def const_fold(instrs: list[IRInstr]) -> list[IRInstr]:
    out: list[IRInstr] = []
    for i in instrs:
        if (
            i.op in ("+", "-", "*", "/")
            and len(i.args) == 2
            and _is_literal(i.args[0])
            and _is_literal(i.args[1])
        ):
            a = _to_num(i.args[0])
            b = _to_num(i.args[1])
            out.append(IRInstr(op="const", dst=i.dst, args=[repr(_fold(i.op, a, b))]))
        else:
            out.append(i)
    return out


def algebraic(instrs: list[IRInstr]) -> list[IRInstr]:
    out: list[IRInstr] = []
    for i in instrs:
        if i.op in ("+", "-", "*", "/") and len(i.args) == 2:
            a, b = i.args
            if i.op == "+" and (a == "0" or b == "0"):
                out.append(IRInstr(op="copy", dst=i.dst, args=[b if a == "0" else a]))
            elif i.op == "*" and (a == "1" or b == "1"):
                out.append(IRInstr(op="copy", dst=i.dst, args=[b if a == "1" else a]))
            elif i.op == "*" and (a == "0" or b == "0"):
                out.append(IRInstr(op="const", dst=i.dst, args=["0"]))
            else:
                out.append(i)
        else:
            out.append(i)
    return out


def optimize(instrs: list[IRInstr]) -> list[IRInstr]:
    return algebraic(const_fold(instrs))


def format_ir(instrs: list[IRInstr]) -> str:
    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:
    # IR untuk (2 + 3) * x + 0, dengan x variabel runtime.
    before = [
        IRInstr("+", "t1", ["2", "3"]),
        IRInstr("*", "t2", ["t1", "x"]),
        IRInstr("+", "t3", ["t2", "0"]),
    ]
    after = optimize(before)
    print("=== IR sebelum optimasi ===")
    print(format_ir(before))
    print()
    print("=== IR setelah optimasi ===")
    print(format_ir(after))


if __name__ == "__main__":
    main()

Program utama menyusun IR untuk ekspresi (2 + 3) * x + 0, dengan x sebagai variabel runtime. Tiga instruksi tersebut adalah t1 = 2 + 3, t2 = t1 * x, dan t3 = t2 + 0. Setelah optimize dijalankan, keluaran yang diharapkan menyederhanakan dua dari tiga instruksi, sementara satu instruksi tetap utuh karena x tidak diketahui nilainya. Keluaran berikut diperoleh dengan menjalankan python3 const_fold.py.

text Keluaran 
=== IR sebelum optimasi ===
t1 = 2 + 3
t2 = t1 * x
t3 = t2 + 0

=== IR setelah optimasi ===
t1 = 5
t2 = t1 * x
t3 = t2

Keluaran menunjukkan transformasi yang dihasilkan kedua pass. Pada baris pertama, t1 = 2 + 3 di-fold menjadi t1 = 5 karena kedua operand adalah literal. Pada baris ketiga, t3 = t2 + 0 disederhanakan menjadi t3 = t2 karena x + 0 = x. Baris kedua, t2 = t1 * x, tetap utuh karena x bukan literal dan bukan salah satu dari identitas aljabar yang ditangani. Hasilnya, IR setelah optimasi memiliki dua instruksi yang lebih ringkas dari sebelumnya, tetapi tetap merepresentasikan ekspresi (2 + 3) * x + 0 secara semantik.

Ringkasan#

  • Constant folding mengganti instruksi yang kedua operandnya literal menjadi instruksi const dengan hasil perhitungan pada waktu kompilasi.
  • Penyederhanaan aljabar memanfaatkan identitas x + 0, x * 1, dan x * 0 untuk mengganti instruksi dengan copy atau const.
  • Kedua pass bersifat lokal, yaitu hanya melihat satu instruksi pada satu waktu, tanpa menelusuri pemakaian temp antar instruksi.
  • Penghapusan instruksi mati tidak ditangani di sini. Pass tersebut menjadi bagian modul optimasi yang memerlukan analisis aliran data.

Referensi#