Topik ini membahas analisis liveness dan konsep pewarnaan graf untuk alokasi register. Pembaca memperoleh berkas liveness.py yang berisi kelas IRLive untuk menghitung use/def per instruksi dan live-in/live-out dengan algoritma worklist, serta kelas InterferenceGraph yang membangun graf interferensi dan mewarnai variabel virtual ke k register fisik. Setelah membaca topik ini, pembaca dapat menjelaskan apa yang membuat sebuah variabel hidup pada satu titik program, mengapa dua variabel yang hidup bersamaan tidak boleh memakai register yang sama, dan bagaimana pewarnaan greedy memilih register bagi setiap variabel.
Liveness: variabel hidup pada satu titik program#
Variabel disebut hidup pada satu titik program bila nilainya mungkin dipakai pada instruksi setelah titik itu. Sebuah variabel yang didefinisikan tetapi tidak pernah dipakai setelahnya mati segera setelah definisi, sehingga instruksi yang mendefinisikannya dapat dihapus oleh dead code elimination. Sebaliknya, variabel yang dipakai pada instruksi yang lebih awal dari definisinya tidak valid pada program yang sudah benar secara semantik, sebab pemakaian harus didahului definisi.
Liveness didefinisikan per titik di antara instruksi. Untuk setiap instruksi i, live_in[i] adalah himpunan variabel hidup sebelum i dijalankan, dan live_out[i] adalah himpunan variabel hidup setelah i selesai. Hubungan keduanya ditetapkan oleh dua himpunan pada instruksi, yaitu use[i] sebagai variabel yang dipakai sebagai operand, dan def[i] sebagai variabel yang didefinisikan sebagai dst. Persamaan kunci adalah live_in[i] = use[i] ∪ (live_out[i] - def[i]), yaitu variabel hidup sebelum instruksi adalah yang dipakai instruksi itu, atau yang hidup setelahnya tetapi tidak didefinisikan di sini. Liveness menjadi dasar dua pass optimasi penting pada modul ini, yaitu dead code elimination yang memakai live_out untuk menentukan instruksi mati, dan alokasi register yang memakai live_out untuk menentukan interferensi antar variabel.
Use-def chain dan worklist backward#
Liveness dihitung dengan menelusuri instruksi dari akhir block ke awal, sebab live_out[i] bergantung pada live_in[i+1] sebagai penerus instruksi i. Pada basic block lurus tanpa percabangan, penerus instruksi i adalah i+1, kecuali instruksi terakhir yang tidak memiliki penerus sehingga live_out-nya kosong. Iterasi sekali dari akhir ke awal cukup untuk block lurus, tetapi pada graf aliran kontrol dengan percabangan dan perulangan, perlu iterasi sampai titik tetap tercapai.
Algoritma worklist adalah mekanisme yang umum dipakai untuk mencapai titik tetap. Worklist berisi instruksi yang live_in atau live_out-nya berubah, dan setiap kali worklist diproses, perubahan disebarkan ke predecessors. Pada kelas IRLive di berkas liveness.py, worklist diimplementasikan dengan sederhana, yaitu iterasi terus selama ada perubahan, sampai tidak ada lagi perubahan. Pada contoh IR dengan empat instruksi lurus, worklist selesai dalam dua iterasi, yaitu iterasi pertama menghitung dari akhir ke awal, dan iterasi kedua memverifikasi bahwa tidak ada perubahan lagi. Pada graf aliran kontrol dengan percabangan, predecessor setiap block perlu diperhatikan, sebab perubahan pada satu block dapat memengaruhi block lain yang menerima aliran darinya.
Graf interferensi#
Dua variabel interferensi bila keduanya hidup pada saat yang sama pada satu titik di block, sehingga keduanya tidak boleh menempati register yang sama. Aturan Chaitin menyatakan interferensi dengan tepat: pada instruksi yang mendefinisikan d, d interferensi dengan setiap variabel di live_out[i] selain dirinya sendiri. Sumber instruksi, yaitu operand yang dipakai, tidak otomatis interferensi dengan d, sebab operand dapat berbagi register dengan d bila operand mati pada instruksi itu. Aturan ini mengizinkan instruksi t3 = t1 + t2 memakai satu register untuk t3 sekaligus t1 bila t1 mati pada instruksi itu, sebab t1 dibaca lebih dahulu, lalu register yang sama dipakai untuk menulis t3.
Graf interferensi adalah representasi visual dari pasangan interferensi. Setiap variabel menjadi node, dan setiap pasangan yang interferensi menjadi sisi antar node. Pada contoh IR di liveness.py, variabel t1, t2, t3 saling interferensi pada saat t3 didefinisikan, sebab t1 dan t2 keduanya hidup setelah instruksi itu, keduanya dipakai pada t4 = t1 + t2. Hasilnya, graf mengandung segitiga antara t1, t2, dan t3, yang memaksa ketiganya memakai register berbeda. Pada compiler nyata, graf interferensi dapat memiliki ratusan node, sehingga penyimpanannya sebagai matriks menjadi mahal. Representasi adjacency set, yaitu daftar tetangga per node, lebih hemat memori dan tetap cepat untuk pengecekan keanggotaan.
Pewarnaan greedy dengan k warna#
Pewarnaan graf adalah pemberian warna pada node sehingga dua node yang berhubungan sisi tidak boleh memiliki warna sama. Pada alokasi register, warna merepresentasikan register fisik. Bila graf dapat diwarnai dengan k warna, maka k register fisik cukup untuk menampung seluruh variabel virtual tanpa spill ke memori.
Algoritma greedy pada InterferenceGraph mewarnai variabel dalam urutan definisi. Untuk setiap variabel, algoritma memilih warna terkecil yang tidak dipakai tetangganya. Bila tidak ada warna bebas dalam k warna, variabel ditandai sebagai perlu spill, yang pada compiler nyata berarti variabel disimpan di memori pada sebagian masa hidupnya. Algoritma greedy tidak selalu menghasilkan pewarnaan optimal, tetapi pada graf interferensi yang umum muncul dari program nyata, hasilnya mendekati optimal dengan biaya komputasi yang rendah. Algoritma yang lebih ketat seperti Chaitin-Briggs memakai heuristik penyederhanaan graf untuk menangani kasus sulit, tetapi kerangka dasarnya tetap sama, yaitu pewarnaan greedy pada graf interferensi.
Mempraktikkan keduanya#
Berkas liveness.py berisi implementasi kedua kelas beserta runner yang menjalankan analisis pada IR contoh dan mencetak liveness per instruksi, graf interferensi, dan hasil pewarnaan. Kontrak IR diturunkan langsung dari IRInstr pada topik mengapa-ir, tanpa operator tambahan, sebab liveness dan alokasi register tidak memerlukan operator baru. Empat variabel virtual pada contoh dirancang agar membentuk segitiga interferensi, sehingga tiga register fisik benar-benar diperlukan, bukan hanya cukup.
"""Analisis liveness dan pewarnaan graf untuk alokasi register.
Dua kelas disediakan:
1. IRLive: menghitung use/def per instruksi, lalu live-in/live-out
tiap instruksi pada satu basic block dengan algoritma worklist
yang berjalan dari akhir block ke awal.
2. InterferenceGraph: membangun graf interferensi dari liveness, lalu
mewarnai variabel virtual (temp yang muncul sebagai dst) ke k
register fisik dengan algoritma greedy.
Contoh IR yang dipakai pada main() memuat empat variabel virtual
(t1, t2, t3, t4) di mana t1, t2, t3 saling interferensi, sehingga
tiga warna (register fisik) diperlukan untuk mewarnai keempat variabel.
"""
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
class IRLive:
"""Analisis liveness pada satu basic block.
Asumsi: basic block berbentuk urutan instruksi lurus. live-out dari
instruksi terakhir adalah himpunan kosong (anggapan: nilai balik fungsi
sudah ditangani oleh instruksi return yang ditulis terpisah).
"""
def __init__(self, instrs: list[IRInstr]) -> None:
self.instrs = instrs
self.use: list[set[str]] = []
self.defs: list[set[str]] = []
self.live_in: list[set[str]] = []
self.live_out: list[set[str]] = []
self._compute_use_def()
self._worklist()
def _compute_use_def(self) -> None:
for i in self.instrs:
u: set[str] = set()
d: set[str] = set()
for a in i.args:
if not _is_literal(a):
u.add(a)
if i.dst and i.op not in ("ret",):
d.add(i.dst)
self.use.append(u)
self.defs.append(d)
def _worklist(self) -> None:
n = len(self.instrs)
self.live_in = [set() for _ in range(n)]
self.live_out = [set() for _ in range(n)]
changed = True
while changed:
changed = False
for i in range(n - 1, -1, -1):
# live_out[i] = union live_in[succ]; pada block lurus,
# succ = i+1 (atau kosong untuk instruksi terakhir).
if i + 1 < n:
new_out = set(self.live_in[i + 1])
else:
new_out: set[str] = set()
new_in = self.use[i] | (new_out - self.defs[i])
if new_out != self.live_out[i] or new_in != self.live_in[i]:
self.live_out[i] = new_out
self.live_in[i] = new_in
changed = True
def variables(self) -> list[str]:
"""Daftar variabel yang didefinisikan di block ini (urutan def)."""
seen: list[str] = []
for d in self.defs:
for v in d:
if v not in seen:
seen.append(v)
return seen
class InterferenceGraph:
"""Graf interferensi + pewarnaan greedy dengan k warna.
Dua variabel interferensi bila keduanya hidup pada saat yang sama
pada satu titik di block. Aturan Chaitin: pada instruksi yang
mendefinisikan d, d interferensi dengan setiap variabel di
live-out instruksi tersebut, kecuali d sendiri.
"""
def __init__(self, live: IRLive) -> None:
self.live = live
self.edges: dict[str, set[str]] = {}
for v in live.variables():
self.edges.setdefault(v, set())
self._build()
self.color: dict[str, int] = {}
def _build(self) -> None:
for i, instr in enumerate(self.live.instrs):
d_set = self.live.defs[i]
out = self.live.live_out[i]
for d in d_set:
for v in out:
if v != d and not _is_literal(v):
self.edges.setdefault(d, set()).add(v)
self.edges.setdefault(v, set()).add(d)
def color_with(self, k: int) -> dict[str, int]:
"""Warnai variabel dengan k warna (0..k-1) secara greedy.
Urutan: variabel yang didefinisikan lebih dahulu dicetak lebih
dahulu. Untuk setiap variabel, pilih warna terkecil yang tidak
dipakai tetangganya. Bila tidak ada warna yang bebas, variabel
tersebut ditandai -1 (perlu spill), yang pada compiler nyata
berarti variabel disimpan di memori.
"""
self.color = {}
for v in self.live.variables():
used = {self.color[n] for n in self.edges.get(v, set()) if n in self.color}
chosen = -1
for c in range(k):
if c not in used:
chosen = c
break
self.color[v] = chosen
return self.color
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:
# Empat variabel virtual: t1, t2, t3, t4.
# Pemakaian dirancang agar t1, t2, t3 saling interferensi pada saat
# t3 didefinisikan (t1 dan t2 keduanya hidup setelah instruksi itu).
instrs = [
IRInstr("+", "t1", ["a", "b"]),
IRInstr("+", "t2", ["c", "t1"]),
IRInstr("+", "t3", ["d", "t2"]),
IRInstr("+", "t4", ["t1", "t2"]),
]
print("=== IR contoh (4 variabel virtual) ===")
print(format_ir(instrs))
print()
live = IRLive(instrs)
print("=== Liveness per instruksi ===")
for i, instr in enumerate(instrs):
print(
f"{i}: live_in={sorted(live.live_in[i])} "
f"live_out={sorted(live.live_out[i])} "
f"defs={sorted(live.defs[i])} use={sorted(live.use[i])}"
)
print()
ig = InterferenceGraph(live)
print("=== Graf interferensi ===")
for v in sorted(ig.edges):
print(f"{v}: interferensi dengan {sorted(ig.edges[v])}")
print()
k = 3
color = ig.color_with(k)
print(f"=== Pewarnaan dengan {k} register fisik ===")
for v in sorted(color):
reg = color[v]
label = f"R{reg}" if reg >= 0 else "SPILL"
print(f"{v} -> {label}")
if __name__ == "__main__":
main()Keluaran berikut diperoleh dengan menjalankan python3 liveness.py. Bagian pertama memperlihatkan IR contoh dengan empat variabel virtual, yaitu t1, t2, t3, t4. Bagian kedua memperlihatkan liveness per instruksi, dengan live_in dan live_out di setiap titik. Bagian ketiga memperlihatkan graf interferensi, termasuk segitiga antara t1, t2, t3. Bagian keempat memperlihatkan pemetaan warna ke tiga register fisik, dengan t4 dapat berbagi R0 dengan t1 sebab keduanya tidak interferensi.
=== IR contoh (4 variabel virtual) ===
t1 = a + b
t2 = c + t1
t3 = d + t2
t4 = t1 + t2
=== Liveness per instruksi ===
0: live_in=['a', 'b', 'c', 'd'] live_out=['c', 'd', 't1'] defs=['t1'] use=['a', 'b']
1: live_in=['c', 'd', 't1'] live_out=['d', 't1', 't2'] defs=['t2'] use=['c', 't1']
2: live_in=['d', 't1', 't2'] live_out=['t1', 't2'] defs=['t3'] use=['d', 't2']
3: live_in=['t1', 't2'] live_out=[] defs=['t4'] use=['t1', 't2']
=== Graf interferensi ===
c: interferensi dengan ['t1']
d: interferensi dengan ['t1', 't2']
t1: interferensi dengan ['c', 'd', 't2', 't3']
t2: interferensi dengan ['d', 't1', 't3']
t3: interferensi dengan ['t1', 't2']
t4: interferensi dengan []
=== Pewarnaan dengan 3 register fisik ===
t1 -> R0
t2 -> R1
t3 -> R2
t4 -> R0Keluaran menunjukkan rantai sebab-akibat antara liveness, interferensi, dan pewarnaan. Instruksi t3 = d + t2 mempertahankan t1 dan t2 hidup setelah definisi t3, sebab keduanya dipakai pada instruksi t4 = t1 + t2. Akibatnya, t3 interferensi dengan t1 dan t2, dan ketiganya membentuk segitiga pada graf interferensi. Pewarnaan greedy dengan tiga warna memberi t1, t2, t3 warna berbeda, sedangkan t4 dapat memakai R0 kembali sebab t4 tidak interferensi dengan apa pun. Hasil akhir, empat variabel virtual ditampung pada tiga register fisik tanpa spill.
Ringkasan#
- Liveness menyatakan apakah variabel mungkin dipakai setelah satu titik. Persamaan kunci adalah
live_in[i] = use[i] ∪ (live_out[i] - def[i]). - Analisis liveness berjalan backward dari akhir block, dengan worklist sampai titik tetap. Pada block lurus tanpa percabangan, satu iterasi cukup.
- Dua variabel interferensi bila keduanya hidup pada saat yang sama. Aturan Chaitin menetapkan interferensi antara
def[i]danlive_out[i]. - Pewarnaan greedy memetakan variabel ke register fisik dengan memilih warna terkecil yang tidak dipakai tetangganya. Bila
kwarna tidak cukup, variabel ditandai perlu spill ke memori.
Referensi#
- Live variable analysis — Wikipedia
— Definisi liveness dan persamaan aliran data untuk
live_indanlive_out. - Chaitin’s algorithm — Wikipedia — Algoritma alokasi register berbasis pewarnaan graf, termasuk aturan interferensi Chaitin.
- Graph coloring — Wikipedia — Konsep pewarnaan graf, kompleksitasnya, dan algoritma greedy sebagai heuristik umum.