Topik ini membahas dua pass optimasi yang sering dijalankan berurutan pada compiler nyata, yaitu inlining yang menyisipkan badan callee ke call site caller, dan dead code elimination yang menghapus instruksi yang hasilnya tidak pernah dipakai. Pembaca memperoleh berkas dce_inline.py yang berisi kedua pass mini beserta runner yang menjalankan inlining lalu DCE pada IR contoh. Setelah membaca topik ini, pembaca dapat menjelaskan mengapa inlining kerap diikuti oleh DCE, bagaimana penghapusan satu instruksi mati dapat memicu penghapusan berantai, dan bagaimana liveness menjadi dasar keputusan DCE.
Inlining: menyisipkan badan callee#
Inlining mengganti instruksi call ke sebuah callee dengan badan callee itu sendiri. Tujuannya adalah menghilangkan overhead pemanggilan, yaitu pembuatan frame, transisi kontrol, dan pengembalian nilai, sekaligus membuka peluang optimasi baru pada badan caller. Setelah inlining, instruksi yang berasal dari callee dapat dianalisis bersama instruksi caller, sehingga constant folding, propagasi salinan, dan DCE dapat melihat lebih banyak konteks.
Pass inline pada berkas dce_inline.py mengganti setiap call site ke callee dengan badan callee yang variabelnya di-rename menggunakan akhiran unik per call site. Akhiran unik diperlukan sebab callee yang dipanggil dua kali akan menghasilkan dua instance badan callee, dan variabel lokal kedua instance tidak boleh bentrok. Temp akhir callee yang menghasilkan nilai balik dihubungkan ke temp balik caller dengan instruksi copy, sehingga pemakaian selanjutnya pada caller tetap melihat nilai balik callee. Pass inlining nyata memerlukan keputusan biaya-tambah yang lebih kompleks, termasuk perkiraan ukuran caller setelah inlining, frekuensi pemanggilan callee pada profil eksekusi, dan ketersediaan register pada call site.
Dead code elimination: menghapus instruksi mati#
Instruksi disebut mati bila hasilnya, yaitu temp pada dst, tidak pernah dipakai setelah instruksi itu. Keputusan ini didasarkan pada analisis liveness, yaitu live_out[i] yang menyatakan variabel hidup setelah instruksi i. Bila dst instruksi tidak ada di live_out[i], maka instruksi itu dapat dihapus tanpa mengubah semantik program, sebab nilainya akan dibuang begitu saja.
Penghapusan satu instruksi dapat memicu penghapusan berantai. Bila instruksi r = res__1 dihapus sebab r tidak dipakai, maka res__1 mungkin menjadi mati sebab pemakaian satu-satunya hilang. Oleh sebab itu, pass dce pada berkas dce_inline.py mengulang analisis liveness sampai tidak ada lagi instruksi yang dapat dihapus. Pada contoh di topik ini, penghapusan berantai menghapus seluruh rangkaian instruksi yang berasal dari callee, sebab temp akhir r tidak pernah dipakai caller. Pada compiler nyata, DCE juga menghapus instruksi yang efeknya tidak teramati, seperti pemanggilan fungsi murni yang hasilnya tidak dipakai. Identifikasi fungsi murni memerlukan analisis tambahan, sebab compiler harus memastikan fungsi itu tidak memiliki efek samping, misalnya menulis ke memori atau memanggil fungsi dengan efek samping.
Mengapa inlining diikuti DCE#
Inlining sering menghasilkan instruksi mati, terutama bila callee memiliki instruksi yang dipakai hanya untuk nilai baliknya, sedangkan caller tidak memakai nilai balik itu. Sebelum inlining, callee sebagai unit terpisah tidak dapat dihapus, sebab caller mungkin saja memakai nilai baliknya. Setelah inlining, callee menjadi bagian dari caller, sehingga liveness pada caller dapat melihat apakah hasil callee benar-benar dipakai atau tidak.
Pass antarprosedur seperti inlining membuka peluang pass global seperti DCE. Tanpa inlining, DCE hanya melihat satu fungsi pada satu waktu, sehingga callee yang hasilnya tidak dipakai tidak dapat dihapus secara aman. Dengan inlining, callee menjadi bagian caller, dan DCE dapat melihat seluruh pemakaian dalam satu fungsi. Pola ini umum pada compiler nyata, yaitu pass antarprosedur diikuti pass global untuk meraih peluang optimasi yang baru terbuka. Pola inlining-DCE berulang hingga tidak ada lagi callee yang layak di-inline, sehingga ukuran caller bertambah per iterasi namun setiap iterasi menghapus kode mati yang muncul dari iterasi sebelumnya.
Mempraktikkan kedua pass#
Berkas dce_inline.py berisi implementasi kedua pass beserta runner yang menjalankan inlining lalu DCE pada IR contoh. Kontrak IR diturunkan dari IRInstr pada topik mengapa-ir, dengan dua operator tambahan, yaitu call dan ret. Operator call merepresentasikan pemanggilan fungsi, sedangkan ret merepresentasikan pengembalian nilai. Runner mencetak IR caller sebelum optimasi, IR callee, IR caller setelah inlining, dan IR caller setelah DCE, sehingga transformasi kedua pass terlihat bertahap.
"""Pass inlining dan dead code elimination (DCE) pada IR tiga alamat.
Dua pass disediakan:
1. inline: mengganti setiap instruksi `call` ke sebuah callee dengan
badan callee yang sudah di-rename variabelnya. Hasil akhir callee
dihubungkan ke temp balik caller dengan instruksi copy.
2. dce: menghapus instruksi yang hasilnya (dst) tidak pernah dipakai
setelah instruksi itu. Pass ini mengulang analisis liveness sampai
tidak ada lagi instruksi yang dapat dihapus, sehingga penghapusan
satu instruksi dapat memicu penghapusan berantai.
Contoh pada main() memperlihatkan caller yang memanggil callee kecil
tetapi tidak memakai hasil pemanggilan. Setelah inlining, seluruh
rangkaian instruksi yang berasal dari callee menjadi kode mati karena
temp r tidak pernah dipakai. DCE menghapus rangkaian itu secara
berantai pada beberapa iterasi.
"""
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 inline(
caller: list[IRInstr], callee_name: str, callee: list[IRInstr]
) -> list[IRInstr]:
"""Sisipkan badan callee ke setiap call site ke callee_name.
Variabel callee di-rename dengan akhiran unik per call site agar
tidak bentrok dengan variabel caller. Instruksi terakhir callee
diasumsikan menghasilkan temp balik, yang dihubungkan ke temp dst
pada call site caller melalui 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 _liveness(instrs: list[IRInstr]) -> list[set[str]]:
"""Hitung live-out per instruksi pada block lurus (backward)."""
n = len(instrs)
live_in: list[set[str]] = [set() for _ in range(n)]
live_out: list[set[str]] = [set() for _ in range(n)]
changed = True
while changed:
changed = False
for i in range(n - 1, -1, -1):
instr = instrs[i]
u: set[str] = set()
d: set[str] = set()
for a in instr.args:
if not _is_literal(a):
u.add(a)
if instr.dst and instr.op != "ret":
d.add(instr.dst)
new_out = live_in[i + 1] if i + 1 < n else set()
new_in = u | (new_out - d)
if new_out != live_out[i] or new_in != live_in[i]:
live_out[i] = new_out
live_in[i] = new_in
changed = True
return live_out
def dce(instrs: list[IRInstr]) -> list[IRInstr]:
"""Hapus instruksi yang dst-nya tidak ada di live-out instruksi itu.
Iterasi sampai konvergen: penghapusan satu instruksi dapat
menyebabkan instruksi lain yang sebelumnya hidup menjadi mati
karena sumbernya sudah tidak dipakai. Instruksi ret selalu
dipertahankan karena ia adalah pemakaian, bukan definisi.
"""
while True:
live_out = _liveness(instrs)
new: list[IRInstr] = []
removed = False
for i, instr in enumerate(instrs):
if instr.op == "ret":
new.append(instr)
continue
if instr.dst and instr.dst not in live_out[i]:
removed = True
continue
new.append(instr)
instrs = new
if not removed:
return instrs
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 == "ret":
lines.append(f"ret {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:
# Caller memanggil tambah_dua dan menyimpan hasilnya di r, tetapi r
# tidak pernah dipakai setelah pemanggilan. Nilai balik fungsi
# diambil dari c = a + b. Setelah inlining, seluruh rangkaian yang
# berasal dari callee menjadi kode mati dan dihapus DCE.
caller = [
IRInstr("const", "a", ["1"]),
IRInstr("const", "b", ["2"]),
IRInstr("call", "r", ["tambah_dua"]),
IRInstr("+", "c", ["a", "b"]),
IRInstr("ret", "", ["c"]),
]
# Callee tambah_dua: k = 10 (dipakai di res), junk = 99 (mati),
# res = k + 2 (nilai balik).
callee = [
IRInstr("const", "k", ["10"]),
IRInstr("const", "junk", ["99"]),
IRInstr("+", "res", ["k", "2"]),
]
print("=== Caller sebelum optimasi ===")
print(format_ir(caller))
print()
print("=== Callee (tambah_dua) ===")
print(format_ir(callee))
print()
inlined = inline(caller, "tambah_dua", callee)
print("=== Caller setelah inlining ===")
print(format_ir(inlined))
print()
cleaned = dce(inlined)
print("=== Caller setelah inlining + DCE ===")
print(format_ir(cleaned))
if __name__ == "__main__":
main()Keluaran berikut diperoleh dengan menjalankan python3 dce_inline.py. Bagian pertama memperlihatkan caller sebelum optimasi, dengan instruksi r = call tambah_dua yang hasilnya tidak dipakai. Bagian kedua memperlihatkan callee tambah_dua yang memuat satu instruksi mati, yaitu junk = 99. Bagian ketiga memperlihatkan caller setelah inlining, di mana badan callee sudah disisipkan dengan akhiran __1. Bagian keempat memperlihatkan caller setelah DCE, di mana seluruh rangkaian yang berasal dari callee telah dihapus, termasuk junk__1 = 99, res__1 = k__1 + 2, k__1 = 10, dan r = res__1.
=== Caller sebelum optimasi ===
a = 1
b = 2
r = call tambah_dua
c = a + b
ret c
=== Callee (tambah_dua) ===
k = 10
junk = 99
res = k + 2
=== Caller setelah inlining ===
a = 1
b = 2
k__1 = 10
junk__1 = 99
res__1 = k__1 + 2
r = res__1
c = a + b
ret c
=== Caller setelah inlining + DCE ===
a = 1
b = 2
c = a + b
ret cKeluaran menunjukkan penghapusan berantai yang khas pada pasangan inlining dan DCE. Pada iterasi pertama, DCE melihat bahwa junk__1 = 99 mati sebab junk__1 tidak pernah dipakai. Pada iterasi kedua setelah junk__1 dihapus, DCE melihat bahwa r tidak dipakai, sehingga r = res__1 dihapus. Pada iterasi ketiga setelah r = res__1 dihapus, res__1 tidak lagi dipakai, sehingga res__1 = k__1 + 2 dihapus. Pada iterasi keempat setelah res__1 = k__1 + 2 dihapus, k__1 tidak lagi dipakai, sehingga k__1 = 10 dihapus. Hasil akhir adalah caller yang setara dengan sebelum pemanggilan, sebab callee tidak memberi dampak pada nilai balik fungsi.
Ringkasan#
- Inlining mengganti instruksi
calldengan badan callee yang sudah di-rename variabelnya per call site, lalu menghubungkan temp akhir callee ke temp balik caller dengan copy. - Dead code elimination menghapus instruksi yang
dst-nya tidak ada dilive_out[i], berdasarkan analisis liveness yang berjalan backward. - DCE diiterasi sampai konvergen sebab penghapusan satu instruksi dapat membuat instruksi lain menjadi mati, sehingga rangkaian penghapusan berantai dimungkinkan.
- Inlining diikuti DCE sebab inlining membuka peluang DCE pada callee yang hasilnya tidak dipakai caller. Tanpa inlining, callee sebagai unit terpisah tidak dapat dihapus.
Referensi#
- Inline expansion — Wikipedia — Penjelasan inlining sebagai pass antarprosedur, termasuk keputusan biaya-tambah per call site.
- Dead code elimination — Wikipedia — Definisi DCE dan keterkaitannya dengan analisis liveness.
- Live variable analysis — Wikipedia — Dasar liveness yang dipakai DCE untuk menentukan apakah instruksi mati.