Belajar LLVM - Control Flow, Phi Nodes & Functions di IR

#Pendahuluan

Setelah di episode 11 kita mengonversi AST ke IR dan menjalankannya via LLJIT, pada episode ini kita mendalami control flow — bagaimana LLVM IR merepresentasikan percabangan, perulangan, dan panggilan fungsi.

Control flow adalah salah satu aspek paling kritis dari IR: ia menentukan bagaimana program berpindah antar basic block, bagaimana nilai SSA di-merge saat control flow converge (phi nodes), dan bagaimana fungsi dipanggil. Tanpa pemahaman control flow, kalian tidak bisa menulis pass yang benar untuk loop optimization atau dead code elimination.

#Basic Block & Branching

Setiap basic block diakhiri oleh terminator instruction — instruksi yang secara eksplisit menentukan basic block berikutnya:

Terminator	Fungsi
`ret`	Kembalikan nilai dari fungsi
`br i1 %cond, label %then, label %else`	Conditional branch
`br label %target`	Unconditional branch
`switch i32 %val, label %default [i32 0, label %case0]`	Switch/case

If-else di LLVM IR

define i32 @max(i32 %a, i32 %b) {
entry:
  %cmp = icmp sgt i32 %a, %b
  br i1 %cmp, label %then, label %else
 
then:
  br label %merge
 
else:
  br label %merge
 
merge:
  %result = phi i32 [ %a, %then ], [ %b, %else ]
  ret i32 %result
}

#Phi Nodes: Merge Nilai SSA

Phi node adalah mekanisme untuk merge nilai dari paths yang berbeda. Karena SSA meminta setiap variabel hanya di-assign sekali, tetapi ada situasi di mana nilai yang berbeda dari dua path perlu disatukan — phi node menyelesaikan ini.

Phi node dalam if-else

merge:
  %result = phi i32 [ %a, %then ], [ %b, %else ]

Arti: "ambil nilai %a jika control datang dari block then, atau %b jika dari block else". Phi nodes selalu berada di awal basic block yang memiliki lebih dari satu predecessor.

#Loop dengan Phi Node

For loop di LLVM IR

define void @count_to_10() {
entry:
  br label %loop
 
loop:
  %i = phi i32 [ 0, %entry ], [ %i_next, %loop ]
  %cmp = icmp slt i32 %i, 10
  br i1 %cmp, label %body, label %exit
 
body:
  call void @putd(i32 %i)
  %i_next = add i32 %i, 1
  br label %loop
 
exit:
  ret void
}

%i = phi i32 [ 0, %entry ], [ %i_next, %loop ] mengambil nilai 0 saat pertama kali masuk loop, atau %i_next dari iterasi sebelumnya.

#Functions: Definisi & Pemanggilan

#Definisi Function

Definisi fungsi dengan argument attributes

define i32 @add(i32 %a, i32 %b) #0 {
entry:
  %result = add i32 %a, %b
  ret i32 %result
}
 
attributes #0 = { nounwind readnone }

#Pemanggilan Function

Call instruction

%sum = call i32 @add(i32 3, i32 4)

#Recursion

Fibonacci rekursif

define i32 @fib(i32 %n) {
entry:
  %cmp = icmp slt i32 %n, 2
  br i1 %cmp, label %base, label %recurse
 
base:
  ret i32 %n
 
recurse:
  %n_minus_1 = sub i32 %n, 1
  %n_minus_2 = sub i32 %n, 2
  %a = call i32 @fib(i32 %n_minus_1)
  %b = call i32 @fib(i32 %n_minus_2)
  %result = add i32 %a, %b
  ret i32 %result
}

#Tail Call Optimization

LLVM bisa mengoptimalkan recursion menjadi iterative loop jika memenuhi syarat tail call:

Tail call optimized

%result = tail call i32 @fib(i32 %n_minus_1)
ret i32 %result

Kata kunci tail memberitahu optimizer bahwa stack frame pemanggil tidak lagi dibutuhkan.

#Praktik: Implementasi If/Else & For pada Mini Language

Perluasan episode 11 — menambahkan codegen untuk if/else dan for:

codegen IfExprAST

Value *IfExprAST::codegen() {
    Value *CondV = Cond->codegen();
    if (!CondV) return nullptr;
 
    CondV = Builder->CreateFCmpOEQ(
        CondV, ConstantFP::get(*TheContext, APFloat(0.0)), "ifcond");
 
    Function *TheFunction = Builder->GetInsertBlock()->getParent();
    BasicBlock *ThenBB = BasicBlock::Create(*TheContext, "then", TheFunction);
    BasicBlock *ElseBB = BasicBlock::Create(*TheContext, "else");
    BasicBlock *MergeBB = BasicBlock::Create(*TheContext, "ifcont");
 
    Builder->CreateCondBr(CondV, ElseBB, ThenBB);
 
    // Then block
    Builder->SetInsertPoint(ThenBB);
    Value *ThenV = Then->codegen();
    if (!ThenV) return nullptr;
    Builder->CreateBr(MergeBB);
 
    // Else block
    TheFunction->getBasicBlockList().push_back(ElseBB);
    Builder->SetInsertPoint(ElseBB);
    Value *ElseV = Else->codegen();
    if (!ElseV) return nullptr;
    Builder->CreateBr(MergeBB);
 
    // Merge block
    TheFunction->getBasicBlockList().push_back(MergeBB);
    Builder->SetInsertPoint(MergeBB);
    PHINode *PN = Builder->CreatePHI(Type::getDoubleTy(*TheContext), 2, "iftmp");
    PN->addIncoming(ThenV, ThenBB);
    PN->addIncoming(ElseV, ElseBB);
    return PN;
}

Note

Perhatikan bagaimana codegen if/else membuat tiga basic block (then, else, merge), menempatkan branch conditional di entry, dan menggunakan PHINode di merge block untuk menggabungkan nilai dari kedua branch. Ini adalah pola dasar control flow yang akan kalian lihat di seluruh LLVM IR.

#Penutup

Inti yang harus dibawa pulang:

Setiap basic block diakhiri terminator: ret, br (conditional/unconditional), switch.
Phi node menggabungkan nilai dari multiple predecessors — kunci untuk control flow converge.
Fungsi didefinisikan dengan define, dipanggil dengan call, dan bisa recursive.
Tail call optimization: gunakan tail untuk mengizinkan LLVM mengoptimalkan recursion ke iterative.

Di episode 13 selanjutnya kita akan membahas integrasi optimasi & mutable variables — teknik alloca-bump untuk variabel mutable, memasang pipeline optimasi ke REPL, dan membandingkan IR sebelum/sesudah pipeline. Sampai jumpa di episode 13!