Full Toy Compiler

কেন এই প্রজেক্ট

এই মডিউলের আগের প্রজেক্টগুলো pipeline-এর টুকরা ছিল — Pratt parser, bytecode VM। এখন সবগুলো জোড়া দিয়ে native code বানানো: যে .s ফাইল আপনার compiler ছাপবে, gcc সেটা না বুঝেই assemble করবে, আর CPU সোজা চালাবে। এটা curriculum-এর compilers track-এর capstone — শেষ হলে “compiler” শব্দটা আর black box থাকে না।

আর এখানেই খেলার আসল স্তরগুলো একসাথে চাপা পড়ে: IR design-এর একটা ভুল decision কয়েক pass পরে optimization-এ ফাঁদ পাতে; stack-slot codegen-এ sub rsp, N ভুল হলে segfault; regalloc ভুল interference edge হলে program মাঝেমধ্যেই ভুল উত্তর দেয় — কোনো crash নেই। Silent wrong answer native compiler-এর সবচেয়ে ভয়ের নাম, আর test suite ছাড়া ওটা ধরা যায় না।

Architecture — pass by pass

source.toy
   │ lexer + parser          (Pratt parser প্রজেক্ট reuse)
   ▼
AST
   │ type checker            (HM-lite: int/bool, annotation-free)
   ▼
typed AST
   │ lowering                (three-address code)
   ▼
TAC functions ──► CFG ──► optimizations (const-fold, DCE)
   │
   ├─ naive path:  TAC → stack-slot assembly      (step ১)
   └─ tuned path:  TAC → regalloc → assembly      (step ৩)
   ▼
program.s ──► gcc ──► ./a.out ──► stdout == golden?

Bytecode VM-এর compiler pass-এর সাথে পার্থক্য: target এখন register machine — আর প্রতিটা value-র ঘর ঠিক করতে হবে আগে, emit করার আগেই।

Naive codegen — সব কিছু memory-তে

নিয়ম: প্রতিটা local variable একটা fixed slot [rbp - k]; expression evaluate করে সবসময় rax-এ ফেরত:

# a = b + c * d        (a:[rbp-8] b:[rbp-16] c:[rbp-24] d:[rbp-32])
mov  rax, [rbp-24]
imul rax, [rbp-32]
add  rax, [rbp-16]
mov  [rbp-8], rax

Function prologue/epilogue template:

fib:
    push rbp
    mov  rbp, rsp
    sub  rsp, 32              # nlocals * 8, 16-byte align মাথায় রেখে
    ...
    mov  rsp, rbp
    pop  rbp
    ret

Caller-saved registers নিয়ে naive version-এ চিন্তা নেই — কারণ কেউ register-এ কিছু রাখছেই না, call-এর আগে argument গুলো System V convention-এ (rdi, rsi, …) বসিয়ে দিলেই হলো।

Checkpoint: এই naive version-এই fibonacci চলা উচিত —

fun fib(n) {
  if (n < 2) { return n; }
  return fib(n - 1) + fib(n - 2);
}
print(fib(10));    /* 55 */

gcc-তে assemble করে run করে 55 দেখাই হলো প্রজেক্টের প্রথম বড় মাইলফলক — আপনার ভাষা এখন machine code।

Optimization ১ — constant folding + DCE

CFG বানান TAC instruction list থেকে (leaders: function entry, jump target, jump-এর পরের instruction):

def fold_binary(op, a, b):
    if isinstance(a, Const) and isinstance(b, Const):
        return Const(eval_op(op, a.value, b.value))
    return None

def dce_pass(fn):
    # mark: reachable blocks থেকে যে assignment-এর var কেউ পড়ে না
    changed = True
    while changed:
        used = collect_uses(fn)
        changed = remove_dead_stores(fn, used)     # fixpoint পর্যন্ত

DCE fixpoint loop দরকার — একটা store মুছলে তার operand-ও dead হয়ে যেতে পারে। Side-effecting operation (print, division by possibly-zero) মোটেও মুছবেন না — correctness-এর red line।

Optimization ₂ — graph coloring regalloc

Lesson-এর algorithm হুবহু: live ranges → interference graph → color with K = available registers:

def allocate(fn, k=6):                    # callee-saved pool
    ig = build_interference(fn)           # live-range overlap → edge
    coloring = color_graph(ig, k)         # simplify/select অথবা spill
    spills = [v for v in coloring if coloring[v] is SPILL]
    return rewrite(fn, coloring, spills)

Spill handling সৎ রাখুন: spilled variable stack slot-এ, load/store insert করে। Interference edge ভুল হলে দুই live value এক register-এ ঢুকে silent corruption — এজন্যই golden tests প্রতি step-এ চালান, শুধু শেষে না।

Naive বনাম regalloc version-এর instruction count তুলনা করুন (objdump -d line count) — improvement-এর সংখ্যা নিজের চোখে।

Emit, assemble, run

python toyc.py examples/fib.toy --emit-s -o fib.s
gcc fib.s runtime.o -o fib && ./fib

runtime.o — ছোট C shim: print_int, exit, (ঐচ্ছিক) heap। Compiler শুধু _print_int symbol call করবে; linking-and-relocation লেসনে দেখা symbol resolution এখানে হাতে-কলমে ঘটছে — আপনার .s-এ call _print_int relocation ছাড়া link fail করত।

Feature checklist

feature	test program	expected
variables	x = 5; y = x + 2; print(y)	7
if/else	sign check on -3	-1
while	sum 1..100	5050
function call	double(triple(4))	24
recursion	fib(20)	6765
shadowing/scoping	nested block same-name	inner wins

প্রতিটা case .toy file + expected output ফাইল — test runner diff করে। Regression protection-ই optimization pass-গুলো নিরাপদে যোগ করার একমাত্র উপায়।

চূড়ান্ত — end-to-end golden suite

Prime sieve (while + array-free logic দিয়ে trial division):

fun is_prime(n) {
  d = 2;
  while (d * d <= n) {
    if (n % d == 0) { return 0; }
    d = d + 1;
  }
  return 1;
}

n = 2;
while (n < 30) {
  if (is_prime(n)) { print(n); }
  n = n + 1;
}

Golden output: 2 3 5 7 11 13 17 19 23 29। Suite runner:

$ python run_tests.py
fib.toy .......... ok
sieve.toy ........ ok
features/if.toy .. ok
...
23 passed, 0 failed

Checkpoint: পুরো suite green — naive ও optimized দুই backend-এই। এটাই প্রজেক্ট completion-এর সংজ্ঞা।

নিজেকে চ্যালেঞ্জ করুন

1. SSA form — phi node সহ construction, তার উপর constant propagation
2. Common subexpression elimination — available expression analysis
3. Peephole pass — redundant mov chain মোছা emit-এর পরে
4. -O0/-O1/-O2 flag — আপনার pass pipeline-এর switch, benchmark table
5. Bytecode VM-কে second backend — একই frontend, দুই target

যা এখানে শিখলেন, পরে যেখানে লাগবে

এখানে	পরে
Multi-pass pipeline integration	Production toolchain — LLVM-এর pass manager একই চিন্তা
Interference-based allocation	JIT-এর linear scan পর্যন্ত allocation family
Golden-output testing	যেকোনো language/tooling project-এর safety net
ABI-conformant codegen	FFI, calling convention debugging, OS-level work