Belajar LLVM - Register Allocation & MC Layer

#Pendahuluan

Setelah di episode 16 kita memahami backend architecture dan TableGen, pada episode ini kita mendalami dua komponen kritis pipeline backend: register allocation — bagaimana LLVM menentukan register mana yang dipakai tiap nilai — dan MC Layer — lapisan paling rendah yang menghasilkan binary final.

Register allocation adalah salah satu masalah paling kompleks dalam compiler: jumlah register terbatas, tetapi jumlah values yang perlu di-registers jauh lebih banyak. Solusi LLVM menggunakan greedy allocator yang meminimalkan spill (menulis ke memory).

#Register Allocation

#Live Intervals

Register allocator pertama-tama menghitung live intervals — range instruksi di mana sebuah value "hidup" (bisa diakses). Interval ini menentukan kapan dua values bisa berbagi register yang sama.

100%

#Greedy Allocator

LLVM menggunakan greedy register allocator — memilih register berdasarkan heuristik profit. Value dengan live interval panjang atau usage intensity tinggi diprioritaskan mendapat register fisik.

#Spill & Reload

Jika register fisik tidak cukup, value di-spill ke stack frame (memory) dan di-reload saat dibutuhkan:

Spill & reload pattern

; Spill: tulis ke stack
store i32 %v, ptr %spill_slot, align 4
 
; ... kode lain yang butuh register ...
 
; Reload: baca dari stack
%v_reload = load i32, ptr %spill_slot, align 4

Spill menambah latency karena akses memory jauh lebih lambat dari register. Inilah mengapa register allocation yang baik sangat berpengaruh terhadap performa.

#MC Layer

MC Layer (Machine Code Layer) adalah lapisan paling rendah LLVM — mengonversi MCInst ke encoding binary yang bisa dieksekusi CPU.

#Assembler Internal

MC Layer mengandung assembler internal yang mengonversi instruksi assembly ke encoding binary:

Fungsi	Contoh
Encode instruksi	`add %eax, %esi` → opcode binary
Encode immediate	`add $42, %eax` → immediate value
Encode memory operand	`(%rax)` → ModR/M byte

#Relocation

Saat alamat belum diketahui saat assembly (misal alamat fungsi lain), MC Layer menulis relocation entries yang diisi oleh linker nanti:

Contoh relocation

R_X86_64_PLT32  rel_offset  symbol_name

#Emisi Format Objek

MC Layer mendukung tiga format objek utama:

Format	Platform
ELF	Linux, BSD, embedded
Mach-O	macOS, iOS
COFF	Windows (PE/PE+)

Emisi berbagai format

llc -filetype=obj -o program.o program.bc          # ELF (default Linux)
llc -filetype=obj -mtriple=x86_64-unknown-macos program.o  # Mach-O
llc -filetype=obj -mtriple=x86_64-pc-windows program.o     # COFF

#Praktik: Inspeksi Register Allocation

Debug register allocation

opt -S -O2 -debug-only=regalloc -disable-output program.bc 2>regalloc.log

regalloc.log menunjukkan proses allocation: live interval computation, spill decisions, dan final assignment. Untuk loop hot path, perhatikan bagaimana register di-reuse antar iterasi.

Bandangkan register usage di berbagai level optimasi

llc -O0 -o - program.bc | grep -c 'spill\|reload'
llc -O2 -o - program.bc | grep -c 'spill\|reload'

-O2 menghasilkan jauh lebih sedikit spill/reload karena optimizer mengurangi jumlah values yang hidup secara simultan.

Tip

Gunakan llvm-mca untuk menganalisis throughput assembly yang dihasilkan. Jika register allocation menghasilkan banyak spill, llvm-mca akan menunjukkan penurunan throughput yang signifikan — indikasi bahwa register pressure terlalu tinggi.

#Penutup

Inti yang harus dibawa pulang:

Register allocation mengonversi virtual registers ke physical registers target.
Live intervals menentukan range di mana value hidup; greedy allocator memilih register berdasarkan profit.
Spill/reload: jika register tidak cukup, value ditulis/dibaca dari stack — penalty performa.
MC Layer: assembler internal, relocation, emisi ELF/COFF/Mach-O.

Di episode 18 selanjutnya kita akan membahas menulis backend target baru — roadmap minimal target CPU toy, TargetLowering, frame lowering, emission, dan studi kasus backend toy/edu. Sampai jumpa di episode 18!