Taksonomi Optimasi

Pembedaan optimasi lokal, global, dan antarprosedur beserta contoh pass tiap kelas.

Daftar isi

Topik ini membahas taksonomi optimasi pada compiler, yaitu pembedaan pass optimasi berdasarkan cakupan aliran kontrol yang dilihatnya. Pembaca memperoleh berkas optimasi_kelas.py yang berisi tiga pass mini mewakili tiga kelas optimasi, yaitu constant folding dalam satu basic block sebagai pass lokal, propagasi salinan lintas block sebagai pass global, dan inlining stub sebagai pass antarprosedur. Setelah membaca topik ini, pembaca dapat mengelompokkan pass optimasi yang ditemui pada compiler nyata ke dalam salah satu dari tiga kelas, serta menjelaskan batas cakupan tiap kelas.

Tiga kelas optimasi#

Pass optimasi pada compiler dikelompokkan menurut cakupan aliran kontrol yang menjadi masukannya. Cakupan ini menentukan seberapa banyak konteks yang perlu dilihat pass sebelum mengambil keputusan, sekaligus menentukan biaya analisis yang dibayar. Tiga kelas yang dibahas pada topik ini adalah lokal, global, dan antarprosedur.

Pass lokal bekerja di dalam satu basic block, yaitu urutan instruksi lurus tanpa percabangan. Karena basic block tidak memiliki titik masuk selain awal dan tidak memiliki titik keluar selain akhir, pass lokal dapat mengabaikan aliran kontrol sepenuhnya dan memproses instruksi satu per satu dalam urutan penulisan. Constant folding dalam block adalah contoh pass lokal yang sudah diperkenalkan pada topik optimasi-dasar.

Pass global bekerja lintas basic block pada satu fungsi. Pass ini harus memperhatikan aliran kontrol antar block, yaitu block mana yang dapat menjadi penerus block lain, sehingga analisis aliran data perlu menelusuri graf aliran kontrol. Propagasi salinan, analisis liveness, dan alokasi register adalah contoh pass global yang dibahas pada topik ini dan topik liveness-dan-alokasi.

Pass antarprosedur bekerja lintas fungsi atau prosedur. Pass ini melihat badan caller dan callee sekaligus, sehingga keputusan optimasi pada satu fungsi memperhatikan dampaknya pada fungsi lain. Inlining adalah contoh pass antarprosedur yang paling sering disebut, karena callee disisipkan ke badan caller, sehingga batas antar fungsi hilang pada call site tersebut.

Tabel berikut membandingkan tiga kelas:

Kelas	Cakupan	Konteks yang dilihat	Contoh pass
Lokal	satu basic block	instruksi dalam block	constant folding, penyederhanaan aljabar
Global	satu fungsi	lintas basic block dan graf aliran kontrol	propagasi salinan, liveness, alokasi register
Antarprosedur	lintas fungsi	badan caller dan callee	inlining, kloning fungsi

Pass lokal: constant folding dalam basic block#

Pass lokal memproses satu basic block pada satu waktu. Karena setiap instruksi dapat dilihat secara mandiri, pass lokal paling sederhana ditulis dan paling cepat dijalankan. Pass fold_lokal pada berkas optimasi_kelas.py adalah contoh pass lokal yang melakukan constant folding dalam satu block. Instruksi aritmetika dengan dua operand literal diganti menjadi instruksi const yang operand tunggalnya adalah hasil perhitungan pada waktu kompilasi. Bila salah satu operand adalah variabel, instruksi tetap utuh karena nilainya belum diketahui pada waktu kompilasi.

Pass ini tidak melihat instruksi pada block lain. Bila block lain menghasilkan nilai yang dapat dipakai untuk menyederhanakan instruksi pada block ini, pass lokal tidak akan mengetahuinya. Keterbatasan itu menjadi alasan pass global dibutuhkan, yaitu ketika optimasi memerlukan informasi lintas block. Biaya yang dibayar pass lokal rendah karena analisis hanya melihat satu instruksi, sehingga pass ini layak diletakkan paling awal pada pipeline sebelum pass yang lebih mahal. Topik optimasi-dasar sudah memperlihatkan pass fold_lokal yang serupa. Perbedaan pada topik ini adalah pass diberi nama fold_lokal untuk menegaskan cakupannya yang hanya satu block.

Pass global: propagasi salinan lintas block#

Pass global melacak informasi aliran data lintas basic block. Pass propagasi_salinan_global pada berkas optimasi_kelas.py adalah contoh pass global yang melacak salinan variabel antar block. Bila sebuah instruksi y = x muncul pada block B1 dan pemakaian y muncul pada block B2 yang menjadi penerus B1, pass ini mengganti pemakaian y dengan x, sehingga ketergantungan pada salinan dapat dihilangkan. Setelah propagasi, instruksi y = x sendiri menjadi kandidat dead code elimination, sebab y tidak lagi dipakai setelah pemakaiannya diganti.

Pada compiler nyata, pass ini memerlukan analisis aliran data yang menelusuri graf aliran kontrol. Setiap block memiliki himpunan salinan yang mencapai block itu dari predecessors, dan pass menghitung titik tetap ketika himpunan salinan tidak berubah lagi. Pada contoh sederhana di topik ini, asumsi rangkaian block lurus tanpa definisi ulang variabel yang disalin dipakai agar algoritma dapat dijelaskan tanpa menelusuri graf aliran kontrol penuh. Topik liveness-dan-alokasi membahas analisis aliran data yang melibatkan worklist secara lebih rinci, sebab liveness juga merupakan pass global yang melihat lintas block.

Pass antarprosedur: inlining stub#

Pass antarprosedur melihat lebih dari satu fungsi sekaligus. Pass inline_stub pada berkas optimasi_kelas.py adalah contoh pass antarprosedur yang menyisipkan badan callee ke call site caller. Variabel callee di-rename dengan akhiran unik per call site, sehingga variabel lokal callee tidak bentrok dengan variabel caller. Temp akhir callee yang menghasilkan nilai balik dihubungkan ke temp balik caller dengan instruksi copy.

Pada compiler nyata, keputusan inlining memperhatikan biaya dan tambahan per call site. Tubuh callee yang besar akan menambah ukuran caller, yang dapat memperlambat instruction cache. Sebaliknya, callee kecil yang sering dipanggil akan untung karena overhead pemanggilan hilang. Topik inlining-dan-kode-mati pada modul ini membahas inlining lebih dalam, termasuk penggabungan dengan dead code elimination yang menjadi pass berikutnya setelah inlining pada pipeline nyata. Pass antarprosedur lain yang sering disebut adalah kloning fungsi dan analisis konstanta antarprosedur, tetapi keduanya berada di luar cakupan modul ini. Pass antarprosedur umumnya lebih mahal daripada pass global sebab melibatkan lebih dari satu fungsi, sehingga pada compiler nyata, pass ini dijalankan pada tingkat optimasi yang lebih tinggi.

Mempraktikkan ketiga pass#

Berkas optimasi_kelas.py berisi implementasi ketiga pass beserta runner yang menjalankan masing-masing pada IR contoh dan mencetak hasil sebelum dan sesudah. Kontrak IR diturunkan langsung dari IRInstr pada topik mengapa-ir, dengan satu operator tambahan, yaitu call, yang ditambahkan pada modul ini untuk merepresentasikan pemanggilan fungsi. Pass fold_lokal, propagasi_salinan_global, dan inline_stub masing-masing berdiri sendiri dan dapat dipanggil terpisah, sehingga pembaca dapat melihat transformasi tiap kelas secara mandiri.

python optimasi_kelas.py

"""Taksonomi optimasi: tiga kelas pass pada IR tiga alamat.

Tiga pass mini disediakan untuk memperlihatkan perbedaan kelas optimasi:

1. fold_lokal: constant folding dalam satu basic block. Pass ini bersifat
   lokal karena hanya melihat instruksi di dalam satu block dan tidak
   bergantung pada block lain.

2. propagasi_salinan_global: mengganti pemakaian variabel yang merupakan
   alias dari variabel lain dengan aslinya. Pass ini bersifat global
   karena melacak salinan lintas block pada satu fungsi.

3. inline_stub: menandai call site ke sebuah callee dan menyisipkan
   badan callee yang sudah di-rename variabelnya. Pass ini bersifat
   antarprosedur karena melihat caller dan callee sekaligus.

Kontrak IR diturunkan dari IRInstr pada topik mengapa-ir, dengan satu
operator tambahan, yaitu "call", yang ditambahkan pada modul ini untuk
merepresentasikan pemanggilan fungsi.
"""
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}")


# ----- 1. Optimasi lokal: constant folding dalam satu basic block -----
def fold_lokal(block: list[IRInstr]) -> list[IRInstr]:
    """Ganti instruksi aritmetika dengan dua operand literal menjadi const.

    Pass ini lokal: hanya melihat satu instruksi pada satu waktu dan tidak
    memerlukan konteks block lain. Bila operand adalah variabel, instruksi
    tetap utuh karena nilainya belum diketahui pada waktu kompilasi.
    """
    out: list[IRInstr] = []
    for i in block:
        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


# ----- 2. Optimasi global: propagasi salinan lintas basic block -----
def propagasi_salinan_global(
    blocks: dict[str, list[IRInstr]],
) -> dict[str, list[IRInstr]]:
    """Ganti pemakaian variabel yang merupakan alias dari variabel lain.

    Asumsi penyederhanaan: program berbentuk rangkaian block lurus tanpa
    definisi ulang variabel yang disalin, sehingga rantai salinan tunggal
    dapat dilacak dengan satu kali iterasi. Pada compiler nyata, pass ini
    memerlukan analisis aliran data yang menelusuri predecessors dan
    successors pada graf aliran kontrol.
    """
    alias: dict[str, str] = {}
    result: dict[str, list[IRInstr]] = {}
    for name, instrs in blocks.items():
        new_block: list[IRInstr] = []
        for i in instrs:
            new_args = [alias.get(a, a) if not _is_literal(a) else a for a in i.args]
            new_block.append(IRInstr(i.op, i.dst, new_args))
            if i.op == "copy" and not _is_literal(i.args[0]):
                alias[i.dst] = alias.get(i.args[0], i.args[0])
        result[name] = new_block
    return result


# ----- 3. Optimasi antarprosedur: inlining stub -----
def inline_stub(
    caller: list[IRInstr], callee_name: str, callee: list[IRInstr]
) -> list[IRInstr]:
    """Sisipkan badan callee ke call site, dengan rename variabel unik.

    Setiap call site ke callee_name diganti dengan badan callee yang
    variabelnya di-rename dengan akhiran unik per call site, sehingga
    variabel lokal callee tidak bentrok dengan variabel caller. Temp
    akhir callee (instruksi terakhir yang menghasilkan dst) dihubungkan
    ke temp balik caller dengan instruksi copy.
    """
    out: list[IRInstr] = []
    suffix = 0
    for i in caller:
        if i.op == "call" and i.args and i.args[0] == callee_name:
            suffix += 1
            ret_name: str | None = None
            for c in callee:
                renamed_dst = f"{c.dst}__{suffix}"
                renamed_args = [
                    a if _is_literal(a) else f"{a}__{suffix}" for a in c.args
                ]
                out.append(IRInstr(c.op, renamed_dst, renamed_args))
                ret_name = renamed_dst
            if ret_name is not None:
                out.append(IRInstr(op="copy", dst=i.dst, args=[ret_name]))
        else:
            out.append(i)
    return out


def format_ir(instrs: list[IRInstr]) -> str:
    lines: list[str] = []
    for i in instrs:
        if i.op == "call":
            lines.append(f"{i.dst} = call {i.args[0]}")
        elif 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:
    # --- 1. Lokal: satu basic block ---
    block_b1 = [
        IRInstr("+", "t1", ["2", "3"]),
        IRInstr("*", "t2", ["t1", "4"]),
        IRInstr("+", "t3", ["t2", "x"]),
    ]
    print("=== 1. Lokal: constant folding dalam basic block B1 ===")
    print("sebelum:")
    print(format_ir(block_b1))
    print("sesudah fold_lokal:")
    print(format_ir(fold_lokal(block_b1)))
    print()

    # --- 2. Global: dua basic block dengan salinan lintas block ---
    blocks = {
        "B1": [
            IRInstr("const", "x", ["10"]),
            IRInstr("copy", "y", ["x"]),
        ],
        "B2": [
            IRInstr("+", "z", ["y", "1"]),
            IRInstr("*", "w", ["y", "z"]),
        ],
    }
    print("=== 2. Global: propagasi salinan lintas basic block ===")
    for name, instrs in blocks.items():
        print(f"{name} sebelum:")
        print(format_ir(instrs))
    out_blocks = propagasi_salinan_global(blocks)
    for name, instrs in out_blocks.items():
        print(f"{name} sesudah propagasi:")
        print(format_ir(instrs))
    print()

    # --- 3. Antarprosedur: inlining stub ---
    caller = [
        IRInstr("const", "a", ["5"]),
        IRInstr("call", "r", ["tambah_satu"]),
        IRInstr("+", "s", ["a", "r"]),
    ]
    callee = [
        IRInstr("const", "k", ["1"]),
        IRInstr("+", "res", ["k", "1"]),
    ]
    print("=== 3. Antarprosedur: inlining stub ===")
    print("caller sebelum:")
    print(format_ir(caller))
    print("callee (tambah_satu):")
    print(format_ir(callee))
    print("caller sesudah inline_stub:")
    print(format_ir(inline_stub(caller, "tambah_satu", callee)))


if __name__ == "__main__":
    main()

Keluaran berikut diperoleh dengan menjalankan python3 optimasi_kelas.py. Bagian pertama memperlihatkan constant folding lokal yang menyederhanakan t1 = 2 + 3 menjadi t1 = 5. Bagian kedua memperlihatkan propagasi salinan global yang mengganti pemakaian y dengan x pada block B2, padahal salinan itu didefinisikan pada block B1. Bagian ketiga memperlihatkan inlining stub yang mengganti r = call tambah_satu dengan badan callee yang sudah di-rename, lalu menghubungkan temp akhir callee ke r dengan copy.

text Keluaran

=== 1. Lokal: constant folding dalam basic block B1 ===
sebelum:
t1 = 2 + 3
t2 = t1 * 4
t3 = t2 + x
sesudah fold_lokal:
t1 = 5
t2 = t1 * 4
t3 = t2 + x

=== 2. Global: propagasi salinan lintas basic block ===
B1 sebelum:
x = 10
y = x
B2 sebelum:
z = y + 1
w = y * z
B1 sesudah propagasi:
x = 10
y = x
B2 sesudah propagasi:
z = x + 1
w = x * z

=== 3. Antarprosedur: inlining stub ===
caller sebelum:
a = 5
r = call tambah_satu
s = a + r
callee (tambah_satu):
k = 1
res = k + 1
caller sesudah inline_stub:
a = 5
k__1 = 1
res__1 = k__1 + 1
r = res__1
s = a + r

Keluaran menunjukkan transformasi tipikal tiap kelas. Pass lokal hanya melihat instruksi pada satu block, sehingga t1 = 2 + 3 diubah menjadi t1 = 5 tanpa memperhatikan instruksi pada block lain. Pass global melihat lintas block, sehingga y pada block B2 diganti dengan x yang berasal dari block B1. Pass antarprosedur melihat badan callee, sehingga r = call tambah_satu diganti dengan k__1 = 1, res__1 = k__1 + 1, dan r = res__1, yang merupakan badan callee yang sudah di-rename variabelnya.

Ringkasan#

Optimasi compiler dikelompokkan menjadi tiga kelas berdasarkan cakupan aliran kontrol: lokal pada satu basic block, global pada satu fungsi, dan antarprosedur pada lintas fungsi.
Pass lokal hanya melihat instruksi dalam satu block, sehingga paling sederhana dan paling cepat. Constant folding dalam block adalah contoh pass lokal.
Pass global melacak informasi aliran data lintas block pada satu fungsi. Propagasi salinan adalah contoh pass global yang melihat pemakaian variabel antar block.
Pass antarprosedur melihat badan caller dan callee sekaligus. Inlining adalah contoh pass antarprosedur yang menghilangkan batas antar fungsi pada call site.

Referensi#

Basic block — Wikipedia — Definisi basic block dan propertinya yang dipakai pass lokal.
Compiler optimization — Wikipedia — Daftar teknik optimasi yang umum dikelompokkan berdasarkan cakupan aliran kontrol.
Interprocedural optimization — Wikipedia — Penjelasan optimasi antarprosedur, termasuk inlining sebagai pass klasik.