এই পর্বে যা শিখবেন
- একটি back end-এর প্রতিটি অংশ কোথা থেকে আসে, আর কোন অংশ এই পর্বে নতুন যোগ হয়
- Haat IR-এর প্রতিটি নির্দেশ (গাণিতিক, শাখা, call, return, print, global) কোন RISC-V ছাঁচে নামে
- একটি পুরো function, একটি while loop আর একটি recursive call-এর assembly লাইনে লাইনে পড়া, register আর stack-সহ
- Runtime library কী, কেন লাগে, আর শূন্য দিয়ে ভাগ, call-এর সীমা ও অপ্রস্তুত global-এর পরীক্ষা কীভাবে বসে
- একটি code generator সঠিক কি না, তা differential test, emulator আর সত্যিকারের compiler দিয়ে কীভাবে যাচাই করবেন
১ · Back end-এর শেষ ধাপ — IR থেকে চালানো যায় এমন program
মডিউল ১১ পর্যন্ত Haat program একটি intermediate representation-এ পৌঁছেছে: পর্ব ৬২-এর three-address code, basic block আর control flow graph. মডিউল ১২-এর প্রথম তিন পর্ব এর পরের তিনটি প্রশ্নের উত্তর দিয়েছে। পর্ব ৬৯: একটি হিসাবের গাছ কোন RISC-V নির্দেশে নামবে (instruction selection). পর্ব ৭০: কোন মান কোন register-এ থাকবে। পর্ব ৭১: একটি function call-এ argument, ফল আর stack কীভাবে চলবে। কিন্তু পর্ব ৬৯-এর selector শুধু leaf function নিতে পারত: call আর print এলেই সে থেমে যেত। এই পর্বে সব জোড়া লাগিয়ে একটি পূর্ণ compiler back end তৈরি হবে, যা bazar.haat থেকে এমন একটি ফাইল লেখে যা সত্যিকারের RISC-V যন্ত্রে চলতে পারে।
উপমা — হোটেলের অর্ডার স্লিপ থেকে রান্নাঘরের কাজের তালিকা: ওয়েটারের স্লিপে লেখা “দুই প্লেট খিচুড়ি, একটি ডিম ভাজা” (IR). কিন্তু রান্নাঘর চলে নিজের নিয়মে: সাতটি চুলা (scratch register t0–t6), প্রতিটি অর্ডারের জন্য তাকে একটি নির্দিষ্ট বাটি (stack slot), আর কিছু কাজ রাঁধুনি নিজে করেন না, ঘণ্টা বাজিয়ে ম্যানেজারকে ডাকেন, যেমন বিল ছাপানো বা গোলমাল হলে জানানো (runtime library). Code generator সেই মানুষ, যে স্লিপ পড়ে এই রান্নাঘরের জন্য ধাপে ধাপে কাজের তালিকা লেখে। তালিকা যত সরলই হোক, খাবারের স্বাদ (program-এর আউটপুট) স্লিপের সঙ্গে হুবহু মিলতে হবে।
পুরো পথটি নিচের ছবিতে। প্রতিটি ধাপের পাশে লেখা, কোডটি কোন পর্বের; শুধু সবুজ অংশ এই পর্বে নতুন।
ছবি ৭২.১ — Haat source থেকে চলমান RISC-V program
ওপর থেকে নিচে; ডানে কোন পর্বের কোড
haat_ir.py (৬২), haat_isel.py (৬৯), haat_abi.py (৭১)। সবুজ অংশটি এই পর্বের haat_rv.py. হলুদ অংশ সত্যিকারের tool: Zig 0.17.1-এর সঙ্গে আসা Clang 22.1.8. ডানের বাঁকা পথ: একই .s text ব্রাউজারের ছোট interpreter-ও চালায়, তাই পাতাতেই ফল মেলানো যায়।শুরুর আগে নকশার সিদ্ধান্তগুলো এক জায়গায়, কারণ এগুলোই ঠিক করে কোডটি কত সরল আর কত ধীর হবে:
| প্রশ্ন | এই পর্বের উত্তর | কেন |
|---|---|---|
| কোন Haat? | Int আর Bool, top-level function, if/while, call, recursion, global, print | Str আর closure-এর জন্য heap আর garbage collector লাগে (পর্ব ৭৫) |
| মান কোথায় থাকে? | প্রতিটি IR নামের একটি stack slot, পর্ব ৭১-এর frame_layout অনুযায়ী | প্রতিটি লাইন মিলিয়ে দেখা সহজ; পর্ব ৭০-এর allocator পরের উন্নতি |
| Target? | RV64IM: ৬৪-বিট integer নির্দেশ আর গুণ-ভাগ (M extension) | Haat-এর Int ৬৪-বিট; ছোট, পরিষ্কার নির্দেশমালা |
print আর error কে লেখে? | C-তে লেখা ছোট runtime, libc ছাড়া | Assembly-তে দশমিক সংখ্যা লেখার লুপ বারবার বানাতে হয় না |
| কোন runtime error রাখা হলো? | শূন্য দিয়ে ভাগ, ১,০০০ call-এর সীমা, অপ্রস্তুত global (সিদ্ধান্ত ১৮, ২৬) | Reference-এর আচরণের সব কটি; একটিও বাদ নয় |
৬৪-বিটের wrap (reference README-র সিদ্ধান্ত ১৩) বিনা খরচে আসে: RISC-V-এর add, sub, mul নিজেই ২৬৪-এর ভাগশেষে কাজ করে, যা ঠিক wrapping arithmetic. সবচেয়ে ছোট Int-কে −1 দিয়ে ভাগও আলাদা পরীক্ষা চায় না: RISC-V spec অনুযায়ী div তখন সেই ছোট সংখ্যাটিই দেয় আর rem দেয় 0, যা সিদ্ধান্ত ১৩-এর হুবহু (পর্ব ৬৯ এটি spec থেকে মিলিয়েছে)। বাকি থাকে শুধু শূন্য দিয়ে ভাগ, যেখানে RISC-V থামে না, ভুল একটি সংখ্যা দেয়।
২ · প্রতিটি IR নির্দেশের ছাঁচ
একটি code generation-এর কাজ আসলে একটি বড় টেবিল: IR-এর প্রতিটি ধরনের নির্দেশ কোন ছাঁচে (template) নামবে। পর্ব ৬৯-এর block_trees একটি block-কে statement-এর তালিকায় ভাঙে, আর একবার লেখা ও একবার পড়া temp-গুলোকে গাছের ভেতরে ঢুকিয়ে দেয় (পর্ব ৬৯-এর নিয়ম ৬৯.১)। তাই নিচের টেবিলের প্রথম সারি এক IR নির্দেশ নয়, একটি পুরো expression tree-এর জন্য।
| Statement | RISC-V ছাঁচ | কার কোড |
|---|---|---|
x = গাছ | ৬৯-এর tile, ফল sd দিয়ে x-এর slot-এ | ৬৯ (Selector.value) |
branch c B1 B2 | তুলনা আর লাফ এক নির্দেশে (blt, bge …); পরের block-এ নিচে গড়িয়ে পড়া | ৬৯ (Selector.branch) |
jump B1 | j .Lhaat_f_B1, যদি B1 ঠিক পরের block না হয় | এই পর্ব |
t = call f(a, b) | argument slot-এ, call-এর সীমা পরীক্ষা, call_seq, সীমা ফেরানো | এই পর্ব + ৭১ |
return a | মান a0-তে, তারপর epilogue | এই পর্ব + ৭১ |
print a | মান a0-তে, call haat_print_int বা haat_print_bool | এই পর্ব |
t = @x / @x = t | la দিয়ে ঠিকানা, flag পরীক্ষা, ld/sd | এই পর্ব |
a / b, a % b | beqz b, … তারপর div/rem; ভুলের পথে haat_div_zero | ৬৯ (stub), runtime এই পর্বের |
Bool কোনটি? IR-এ type নেই
একটি সমস্যা প্রথমেই সামনে আসে: print a-তে a যদি Bool হয়, ছাপতে হবে true/false, আর Int হলে সংখ্যা। কিন্তু পর্ব ৬২-এর IR-এ কোনো type লেখা নেই, আর যন্ত্রে Bool আর Int দুটিই একটি ৬৪-বিটের সংখ্যা (true = 1, false = 0). Type checker (পর্ব ৫২) জানত, কিন্তু সেই তথ্য IR পর্যন্ত আসেনি। এখানে একটি ছোট সমাধান: IR-এর ওপর Bool-এর তথ্য ছড়িয়ে দেওয়া, যতক্ষণ না নতুন কিছু যোগ হয় (একটি fixpoint, পর্ব ৬৪-এর মতো)। তুলনা, !, true/false ধ্রুবক, Bool-ফেরত function-এর call আর Bool parameter থেকে শুরু, তারপর copy ধরে ছড়ায়। আসল compiler এই সমস্যায় পড়ে না, কারণ তার IR-এ type থাকে (LLVM IR-এ i1 আর i64, পর্ব ৬৮)।
# haat_rv.py — পর্ব ৭২: Haat (Int/Bool) -> RV64IM assembly, পুরো program. Register: প্রতিটি IR নাম stack slot-এ (পর্ব ৭১)।
# পর্ব ৬২-এর haat_ir.py, ৬৯-এর haat_isel.py আর ৭১-এর haat_abi.py হুবহু ব্যবহার করে; এখানে যোগ: call, print, global,
# runtime error-এর পরীক্ষা আর পুরো function/program-এর assembly. Runtime (haat_print_int …) আলাদা, C-তে লেখা।
from haat_isel import *
from haat_abi import *
def bool_names(mod, program): # IR-এ type নেই: কোন নাম Bool, তা ছড়িয়ে বের করা
decl = {s.name: s for s in program.stmts if isinstance(s, FnDecl)}
key = lambda f, x: x if x[0] == "@" else f + "/" + x
B = {key(f, p) for f, d in decl.items() for p, q in zip(mod.funcs[f].params, d.params) if str(q.type) == "Bool"}
while True:
n = len(B)
for fn in mod.funcs.values():
for i in (i for b in fn.blocks.values() for i in b if i.dst):
if (i.kind == "const" and isinstance(i.sym, bool)) or (i.kind == "bin" and i.sym in INV) \
or (i.kind == "un" and i.sym == "!") or (i.kind == "copy" and key(fn.name, i.args[0]) in B) \
or (i.kind == "call" and str(decl[i.sym].ret) == "Bool"):
B.add(key(fn.name, i.dst))
if len(B) == n: return B, keyপর্ব ৬৯-এর Selector-কে বাড়ানো
পর্ব ৬৯-এর Selector class অপরিবর্তিত থাকে; এই পর্ব তার একটি subclass Gen বানায়, যা তিনটি জিনিস যোগ করে: global পড়া-লেখা, call, আর runtime error-এর “শেষের পথ”।
class Gen(Selector): # ৬৯-এর Selector, সঙ্গে global, call আর runtime-এর পরীক্ষা
def __init__(self, fr, globals_):
loc = {x: fr.home(x) for x in fr.slots} | {"@" + g: f"0({global_symbol(g)})" for g in globals_}
super().__init__(loc, prefix=symbol(fr.name)); self.fr, self.late = fr, []
def trap(self, kind, pos, name=None): # error-এর পথ: function-এর শেষে, কখনো ফেরে না
e = f".L{self.prefix}_{kind}{len(self.late) + 1}"; self.late.append((e, kind, pos, name)); return e
def ev(self, n, want=None): # @x পড়া: আগে "initialized" flag (সিদ্ধান্ত ১৮)
if n.op != "name" or n.val[0] != "@": return super().ev(n, want)
d = want or self.new(); a = self.new([d])
self.emit(f"la {a}, {global_symbol(n.val[1:])}"); self.emit(f"ld {d}, 8({a})")
self.emit(f"beqz {d}, {self.trap('ni', n.pos, n.val[1:])}"); self.emit(f"ld {d}, 0({a})")
self.release(a); return d
def store(self, g, tree, pos): # @x = মান; pos থাকলে assignment: x আগে initialized হতে হবে
r = self.ev(tree); a = self.new([r]); f = self.new([r, a])
self.emit(f"la {a}, {global_symbol(g)}")
if pos: self.emit(f"ld {f}, 8({a})"); self.emit(f"beqz {f}, {self.trap('ni', pos, g)}")
else: self.emit(f"li {f}, 1"); self.emit(f"sd {f}, 8({a})")
self.emit(f"sd {r}, 0({a})"); [self.release(x) for x in (r, a, f)]
def call(self, ins, kids): # ভাঁজ হওয়া argument আগে নিজের slot-এ, তারপর ৭১-এর call_seq
for x, k in zip(ins.args, kids):
if not (k.op == "name" and k.val == x): self.value(k, self.fr.home(x))
for s in ["la t0, haat_depth", "ld t1, 0(t0)", "li t2, 1000", f"bge t1, t2, {self.trap('so', ins.pos)}",
"addi t1, t1, 1", "sd t1, 0(t0)"]: self.emit(s) # ১,০০০ call-এর সীমা (সিদ্ধান্ত ২৬)
self.out += call_seq(self.fr, ins)
for s in ["la t0, haat_depth", "ld t1, 0(t0)", "addi t1, t1, -1", "sd t1, 0(t0)"]: self.emit(s)
def late_lines(self):
out = []
for e, kind, (line, col), name in self.late:
out += [f"{e}:", f" li a0, {line}", f" li a1, {col}"]
out += [f" la a2, .Lname_{name}", " call haat_not_init"] if kind == "ni" else [" call haat_stack_overflow"]
return out(১) প্রতিটি IR নাম পর্ব ৭১-এর slot-এ; একটি statement শেষ হলে কোনো scratch register (t0–t6) দরকারি মান ধরে রাখে না। (২) প্রতিটি global @x একটি ১৬ byte-এর symbol haat_g_x: প্রথম ৮ byte মান, পরের ৮ byte “initialized” flag. (৩) call-এর আগে haat_depth ১,০০০ বা বেশি হলে haat_stack_overflow(line, col), না হলে এক বাড়ে, ফেরার পরে এক কমে। (৪) প্রতিটি error-এর পথ function-এর শেষে একটি local label, যা a0 = line, a1 = col বসিয়ে runtime ডাকে আর কখনো ফেরে না।
নিয়মের (১) অংশটিই এই back end-কে সহজ রাখে। Call-এর পরে কোন register টিকে থাকে, তা নিয়ে ভাবতে হয় না (পর্ব ৭১-এর caller-saved আর callee-saved-এর প্রশ্ন), কারণ call পেরিয়ে কোনো মান register-এ থাকেই না। দামও স্পষ্ট: প্রায় প্রতিটি হিসাবের আগে ld আর পরে sd. call-এর ভেতরের প্রথম লুপটি লক্ষ করুন। পর্ব ৬৯-এর গাছ argument-এর হিসাব call-এর ভেতরে ভাঁজ করে আনে, কিন্তু পর্ব ৭১-এর call_seq argument পড়ে slot থেকে। তাই ভাঁজ হওয়া প্রতিটি argument আগে নিজের slot-এ লেখা হয়, তারপর call_seq হুবহু ব্যবহার হয়। দুটি পর্বের চুক্তি না ভেঙে জোড়া দেওয়ার দাম এক জোড়া sd/ld.
৩ · একটি পুরো function — price
বাকি অংশ একটি function-এর পুরো assembly লেখে: assembler directive (.globl, .type), prologue, প্রতিটি block-এর label আর statement, তারপর error-এর পথগুলো। একেবারে শেষে compile_rv সব function জোড়া দেয়, আর global থাকলে .data আর .rodata section যোগ করে।
def gen_function(fn, B, key, globals_): # একটি function: prologue, প্রতিটি block, error-এর পথ
fr = frame_layout(fn); S = Gen(fr, globals_); me = symbol(fn.name)
L = lambda b: f".L{me}_{b}"; names = list(fn.blocks)
S.out += [f".globl {me}", f".type {me}, @function"] + prologue(fr)
for n, b in enumerate(names):
fall = L(names[n + 1]) if n + 1 < len(names) else None
S.out.append(L(b) + ":"); ext = iter([i for i in fn.blocks[b] if i.kind in ("call", "print")])
for st in block_trees(fn, b):
if st[0] == "set" and st[1][0] == "@": S.store(st[1][1:], st[2], st[3])
elif st[0] == "set": S.value(st[2], fr.home(st[1]))
elif st[0] == "return": S.value(st[1], "a0"); S.out += epilogue(fr)
elif st[0] == "branch": S.branch(st[1], L(st[2]), L(st[3]), fall)
elif st[0] == "jump":
if L(st[1]) != fall: S.emit(f"j {L(st[1])}")
elif st[0] == "call": S.call(next(ext), st[3])
else: # print: মান a0-তে, type দেখে runtime-এর function
i = next(ext); S.value(st[1], "a0")
S.emit("call haat_print_" + ("bool" if key(fn.name, i.args[0]) in B else "int"))
return S.out + S.stub_lines() + S.late_lines()
def compile_rv(src): # Haat source -> একটি .s ফাইলের text
program = parse(src); mod = lower_program(program)
for fn in mod.funcs.values(): build_cfg(fn)
B, key = bool_names(mod, program); out = [".text"]
for fn in mod.funcs.values(): out += gen_function(fn, B, key, mod.globals)
if mod.globals: # প্রতিটি global ১৬ byte: মান, তারপর "initialized" flag
out += [".data", ".balign 8"]
for g in mod.globals: out += [f".globl {global_symbol(g)}", f"{global_symbol(g)}: .dword 0, 0"]
out += [".section .rodata"] + [f'.Lname_{g}: .asciz "{g}"' for g in mod.globals]
return "\n".join(out) + "\n"এবার চালিয়ে দেখুন। নিচের ব্লক bazar.haat-এর পুরো assembly তৈরি করে আর তার price অংশটি ছাপে।
# Haat -> RV64IM: bazar.haat-এর price function-এর পুরো assembly, haat_rv.py দিয়ে
from haat_rv import *
src = open("examples/bazar.haat", encoding="utf-8").read()
asm = compile_rv(src)
lines = asm.split("\n")
a, b = lines.index(".globl haat_price"), lines.index(".globl haat_delivery")
print("\n".join(lines[a:b]))
calls = [l.split()[1] for l in lines if l.startswith(" call")]
print("পুরো ফাইল:", len(lines) - 1, "লাইন ·", sum(l.endswith(":") for l in lines), "label")
print("call:", ", ".join(f"{c} ×{calls.count(c)}" for c in dict.fromkeys(calls)))আসল আউটপুট (ব্রাউজারের Python):
.globl haat_price
.type haat_price, @function
haat_price:
addi sp, sp, -80
sd ra, 72(sp)
sd s0, 64(sp)
addi s0, sp, 80
sd a0, -24(s0) # qty
sd a1, -32(s0) # unit
.Lhaat_price_B0:
ld t0, -24(s0)
ld t1, -32(s0)
mul t0, t0, t1
sd t0, -40(s0)
ld t0, -40(s0)
li t1, 1000
blt t0, t1, .Lhaat_price_B2
.Lhaat_price_B1:
ld t0, -40(s0)
ld t1, -40(s0)
li t2, 10
div t1, t1, t2
sub a0, t0, t1
ld ra, 72(sp)
ld s0, 64(sp)
addi sp, sp, 80
ret
.Lhaat_price_B2:
ld a0, -40(s0)
ld ra, 72(sp)
ld s0, 64(sp)
addi sp, sp, 80
ret
পুরো ফাইল: 158 লাইন · 16 label
call: haat_price ×2, haat_delivery ×1, haat_print_int ×3, haat_stack_overflow ×3
Prologue আর epilogue পর্ব ৭১-এর হুবহু: ৮০ byte-এর frame, ra আর পুরোনো s0 ওপরে, তারপর qty আর unit-এর slot. Block B0-তে p = qty * unit একটি গাছ: দুটি ld, একটি mul, ফল p-এর slot -40(s0)-এ। p >= 1000-এর শাখা পর্ব ৬৯-এর নিয়মে উল্টে গেছে: সত্য হলে যেতে হবে B1-এ, যা ঠিক পরের block, তাই কোড লেখে “মিথ্যা হলে B2-তে লাফ” (blt), আর সত্য হলে নিচে গড়িয়ে পড়ে। B1-এ p - p / 10 পুরো একটি গাছ; ভাজক ধ্রুবক 10, শূন্য নয়, তাই beqz নেই। p দুবার ld হয়েছে, কারণ গাছের দুই পাতায় একই নাম; register allocator থাকলে একবারেই হতো। পুরো ফাইলে ৯টি call: তিনটি Haat function, তিনটি print, আর তিনটি haat_stack_overflow, প্রতিটি call-এর জন্য একটি করে error-এর পথ, যা স্বাভাবিক চলায় কখনো চলে না।
এখন সেই কোড চলতে দেখুন। নিচের মানগুলো ব্রাউজারের interpreter rv_run.py-এর আসল run থেকে, যেখানে haat_main-এ ঢোকার সময় sp = 0x7FF00000.
1addi sp, sp, -802sd ra, 72(sp)3sd s0, 64(sp)4addi s0, sp, 805sd a0, -24(s0) # qty6sd a1, -32(s0) # unit7ld t0, -24(s0)8ld t1, -32(s0)9mul t0, t0, t110sd t0, -40(s0) # p11ld t0, -40(s0)12li t1, 100013blt t0, t1, …_B214ld t0, -40(s0)15ld t1, -40(s0)16li t2, 1017div t1, t1, t218sub a0, t0, t119ld ra, 72(sp)20ld s0, 64(sp)21addi sp, sp, 8022ret
| sp | |
| s0 | |
| t0 · t1 · t2 | |
| a0 · a1 | |
| slot |
- জায়গা নেওয়া।
call haat_price-এর পরে প্রথম নির্দেশ:sp৮০ কমে0x7FEFFF10.a0= 2,a1= 520:mainargument দুটি register-এ রেখে ডেকেছে। - Frame record আর frame pointer.
raআরmain-এরs0stack-এ গেল; নতুনs0=sp + 80=0x7FEFFF60, ঢোকার মুহূর্তেরsp. এখন থেকে প্রতিটি slots0-সাপেক্ষ। - Parameter slot-এ।
qty= 2 গেল-24(s0)-এ,unit= 520 গেল-32(s0)-এ। এই back end-এ register-argument সঙ্গে সঙ্গেই slot-এ নামে। - প্রথম গাছ:
qty * unit. দুটিld, একটিmul:t0= 1040, ফল গেলp-এর slot-40(s0)-এ।t1-এ 520 পড়ে থাকে, কিন্তু চুক্তি অনুযায়ী statement-এর পরে কেউ সেটি পড়বে না। - শাখা।
pআবারldহলো (আগের লাইনেইsdহয়েছিল; অনুশীলন ১ এটিই সরায়),t1= 1000. 1040 < 1000 মিথ্যা, তাইbltলাফ দেয় না: কোড নিচে গড়িয়ে B1-এ ঢোকে। - দ্বিতীয় গাছ:
p / 10.pদুবারldহলো, গাছের দুই পাতার জন্য দুটি register.div-এর ফলt1= 104; ভাজক ধ্রুবক বলে শূন্যের পরীক্ষা নেই। - ফল।
sub a0, t0, t1: 1040 − 104 = 936, সরাসরি ফেরত-registera0-তে। গাছের মূলreturn-এর, তাই selector গন্তব্য হিসেবেa0পেয়েছে, কোনো slot নয়। - Epilogue.
raআরs0ফিরল (s0আবার0x7FF00000),spআগের0x7FEFFF60,ret. সব মিলেprice-এর ভেতরে ২২টি নির্দেশ চলল; IR-এ ছিল ৯টি নির্দেশ।
৪ · if আর while — label, শাখা আর নিচে গড়িয়ে পড়া
Assembly-তে if বা while নেই, আছে শুধু label আর লাফ (Computer Architecture পর্ব ২৯-এ hardware-এর দিক থেকে দেখেছেন)। Haat IR আগেই এই কাজের বড় অংশ করে রেখেছে: প্রতিটি basic block একটি label, আর প্রতিটি block শেষ হয় jump, branch বা return দিয়ে। Back end-এর কাজ তিনটি: প্রতিটি block-এর জন্য একটি অনন্য label লেখা, branch-কে একটি compare-and-branch নির্দেশে নামানো, আর যে লাফ ঠিক পরের block-এ যায় তা বাদ দেওয়া।
Label-এর নাম .Lhaat_main_B1-এর মতো। .L দিয়ে শুরু হলে assembler সেটিকে local label ধরে: object file-এর symbol table-এ যায় না, তাই দুটি function-এর B1 কখনো সংঘাতে পড়ে না, আর linker-এর তালিকাও ছোট থাকে। (পর্ব ৬৯-এর select_function entry block B0-এর label লিখত না; এখানে প্রতিটি block-এর label লেখা হয়, কারণ যে function while দিয়ে শুরু হয়, তার loop-এর লাফ B0-তেই ফেরে।)
bazar.haat-এর loop while total < 5000 { … }. IR আর তৈরি assembly পাশাপাশি:
B1: .Lhaat_main_B1:
t8 = const 5000 ld t0, -88(s0) # total
t9 = total < t8 li t1, 5000
branch t9 B2 B3 bge t0, t1, .Lhaat_main_B3
B2: .Lhaat_main_B2:
t10 = const 1250 ld t0, -88(s0)
total = total + t10 addi t0, t0, 1250
t11 = const 1 sd t0, -88(s0)
rounds = rounds + t11 ld t0, -96(s0) # rounds
jump B1 addi t0, t0, 1
sd t0, -96(s0)
j .Lhaat_main_B1
B3: .Lhaat_main_B3:
print total ld a0, -88(s0)
t12 = const 1 call haat_print_int
t13 = rounds - t12 ld t0, -96(s0)
print t13 addi a0, t0, -1
call haat_print_int
তিনটি জিনিস চোখে পড়ার মতো। (ক) branch t9 B2 B3-এ সত্য হলে B2, যা ঠিক পরের block; তাই কোড শর্তটি উল্টে লেখে: total >= 5000 হলে B3-এ লাফ (bge), নইলে নিচে গড়িয়ে B2. (খ) t10 = const 1250 আলাদা নির্দেশ হয়নি: ধ্রুবকটি ১২ বিটের মধ্যে, তাই পর্ব ৬৯-এর addi tile সেটিকে নির্দেশের ভেতরেই বসিয়েছে। 5000 ১২ বিটে আঁটে না (সীমা −2048 থেকে 2047), তাই li t1, 5000 আলাদা, যা Clang দুটি আসল নির্দেশে (lui + addi) বদলায়। (গ) B2-এর শেষে j লাগে, কারণ B1 পরের block নয়, আগের: এটিই loop-এর ফেরার পথ (back edge).
1sd zero, -88(s0) # total2sd zero, -96(s0) # rounds3.Lhaat_main_B1:4 ld t0, -88(s0)5 li t1, 50006 bge t0, t1, …_B37.Lhaat_main_B2:8 ld t0, -88(s0)9 addi t0, t0, 125010 sd t0, -88(s0)11 ld t0, -96(s0)12 addi t0, t0, 113 sd t0, -96(s0)14 j .Lhaat_main_B115.Lhaat_main_B3:16 ld a0, -88(s0)17 call haat_print_int18 ld t0, -96(s0)19 addi a0, t0, -120 call haat_print_int
| total | |
| rounds | |
| t0 · t1 | |
| পরীক্ষা |
- Loop-এর আগে।
var total = 0;আরvar rounds = 0;: ধ্রুবক শূন্যের জন্য register লাগে না, RISC-V-এরzeroregister সরাসরি slot-এ লেখা হলো। তারপর B0 শেষ, আর B1 ঠিক পরের block, তাই কোনোjনেই। - প্রথম পরীক্ষা।
t0= total = 0,t1= 5000. 0 ≥ 5000? না, তাইbgeলাফ দেয় না, কোড নিচে B2-তে গড়িয়ে পড়ে। - প্রথম চক্র।
total= 1250,rounds= 1; শেষ লাইনেt0-তে 1 পড়ে থাকে।j .Lhaat_main_B1: পেছনের দিকে লাফ, back edge. - দ্বিতীয় আর তৃতীয় চক্র। পরীক্ষায় 1250 আর 2500, দুবারই 5000-এর কম; body আরও দুবার চলে। এখন
total= 3750,rounds= 3. - চতুর্থ চক্র। চতুর্থ পরীক্ষায় 3750 < 5000, body আবার:
total= 5000,rounds= 4. - পঞ্চম পরীক্ষা। 5000 ≥ 5000, এবার
bgeলাফ দেয় B3-এ। মোট: B1 চলেছে ৫ বার (৫ × ৩ = ১৫টি নির্দেশ), B2 চলেছে ৪ বার (৪ × ৭ = ২৮টি)। - Loop-এর পরে।
print(total)ছাপে 5000.rounds - 1-এর গাছে ধ্রুবক −1 সরাসরিaddi-তে বসেছে, আর গন্তব্যa0, কারণ মানটি সরাসরিprint-এ যাবে: ছাপা হয় 3.
if/else-এর গঠনও একই: delivery-তে total >= 1000 মিথ্যা হলে blt লাফ দেয় else-এর block-এ, আর দুই শাখাই নিজের return-এ শেষ হয়, তাই কোনো “শেষে মিলিত হওয়ার” block-ই নেই। && আর || আলাদা কিছু চায় না: পর্ব ৬২-এর lowering এগুলোকে আগেই শাখায় ভেঙে রেখেছে, তাই back end শুধু আরও কিছু block আর label দেখে।
৫ · Call, recursion আর ১,০০০ call-এর সীমা
একটি Haat call-এর পুরো ক্রম, caller-এর দিক থেকে: (১) গাছে ভাঁজ হওয়া argument নিজের slot-এ, (২) haat_depth পরীক্ষা আর এক বাড়ানো, (৩) পর্ব ৭১-এর call_seq: slot থেকে a0–a7, ৯ম argument থেকে stack-এ, call haat_f, ফল a0 থেকে নিজের slot-এ, (৪) haat_depth এক কমানো। Callee-র দিকে পর্ব ৭১-এর prologue আর epilogue. Activation record-এর ধারণা পর্ব ৩০-এর; এখানে সেটি আসল ঠিকানায় দেখা যাক। Program:
fn fact(n: Int) -> Int {
if n <= 1 { return 1; }
return n * fact(n - 1);
}
print(fact(3));
নিচের মানগুলো সত্যিকারের run থেকে: Clang-এর বানানো ELF, Unicorn-এ চালানো, প্রতিটি haat_fact-এ ঢোকা আর ফেরার মুহূর্তে register পড়ে (তাই ঠিকানাগুলো আগের stepper-এর browser-interpreter-এর থেকে আলাদা)।
1call haat_fact # main, a0 = 32addi sp, sp, -803sd ra, 72(sp); sd s0, 64(sp)4addi s0, sp, 805sd a0, -24(s0) # n6blt t1, t0, …_B2 # 1 < n?7li a0, 1 # B18… n − 1, depth + 1 # B29call haat_fact10sd a0, -72(s0)11… depth − 112mul a0, t0, t1 # n × ফল13ld ra, 72(sp); ld s0, 64(sp)14addi sp, sp, 80; ret15call haat_print_int # main
| sp | |
| s0 | |
| a0 | |
| depth | |
| frame |
mainডাকে।haat_depth0 থেকে 1 (সীমা ১,০০০-এর অনেক নিচে),a0= 3. ঢোকার মুহূর্তেsp=0x7FEFFFC0, ১৬-এর গুণিতক;ra=0x100186C,main-এর ফেরার ঠিকানা।fact(3). Prologue-এর পরেsp=0x7FEFFF70,s0=0x7FEFFFC0;n= 3 গেল0x7FEFFFA8-এ। 1 < 3, তাই B2:n - 1= 2 slot-এ, depth 2,call haat_fact; এবারra=0x100191C,haat_fact-এর নিজের ভেতরের ঠিকানা।fact(2). আরেকটি ৮০ byte-এর frame:sp=0x7FEFFF20,s0=0x7FEFFF70, অর্থাৎ ঠিক আগের frame-এরsp. একই কোড, ভিন্ন frame: recursion-এর পুরো রহস্য এটুকুই। Depth 3, ডাকfact(1).fact(1)আর প্রথম ফেরা। Frame0x7FEFFED0থেকে0x7FEFFF20. 1 < 1 মিথ্যা, তাইbltলাফ দেয় না, B1:a0= 1. Epiloguera,s0আরspফিরিয়ে দেয়fact(2)-এর মানে।fact(2)-এ ফিরে। ফল 1 গেল-72(s0)-এ, depth 3 থেকে 2.nআর ফল slot থেকে উঠেmul:a0= 2 × 1 = 2.nহারায়নি, কারণ সেটি register-এ নয়, নিজের frame-এর slot-এ ছিল।fact(3)-এ ফিরে। Depth 1,a0= 3 × 2 = 6; epilogue-এর পরেspআবার0x7FEFFFC0, ঢোকার মুহূর্তের মান। তিনটি frame-ই ছেড়ে দেওয়া হয়েছে।mainছাপে। Depth 0,haat_print_int(6)লেখে6. গভীরতম মুহূর্তে stack-এ ছিলmain-এর ৪৮ আর তিনটি ৮০ byte-এর frame.
১,০০০ call-এর সীমা কেন caller-এ
Reference বলে, ১,০০০টি call চলাকালীন আরেকটি call হলে stack overflow, আর অবস্থান callee-র নামের শুরু (সিদ্ধান্ত ২৪, ২৬)। সেই অবস্থান জানে শুধু caller, তাই পরীক্ষাটি call-এর ঠিক আগে বসে। Caller প্রথমে সব argument হিসাব করে, তারপর সীমা পরীক্ষা করে: reference-এর ক্রমও তাই, ফলে argument-এ শূন্য দিয়ে ভাগ আর সীমা পেরোনো একসাথে হলে একই error আগে আসে। haat_depth একটি সাধারণ global, runtime-এর C ফাইলে রাখা। আসল stack-এর দিক থেকে এই সীমা নিরাপদ: পর্ব ৭১ মেপেছে, ৩,০০০টি এলোমেলো program-এর ৯,০০১টি function-এর সবচেয়ে বড় frame ১,৯৮৪ byte, তাই ১,০০০ গভীরতায় সর্বোচ্চ প্রায় ২ MB, যা Linux-এর সাধারণ ৮ MB stack-এর অনেক নিচে।
এই back end কতটা ধীর, তা মাপা যায়। একই fact(20), একবার Haat থেকে এই back end দিয়ে, একবার C থেকে Clang দিয়ে (C-তে volatile argument, যাতে Clang আগেই উত্তরটি হিসাব করে না ফেলে); Unicorn-এ চালিয়ে শুধু program-এর নিজের নির্দেশ গোনা, runtime-এর ২৪৮টি বাদ দিয়ে (সত্যিকারের run, এক যন্ত্রে, উদাহরণ হিসেবে):
| কোড | চলা নির্দেশ | কী ঘটেছে |
|---|---|---|
| Haat → এই back end | ৬৮৯ | প্রতিটি মান slot-এ, প্রতিটি call-এ সীমার পরীক্ষা |
C → Clang -O0 | ৪৬৮ | Clang-ও প্রতিটি variable slot-এ রাখে, কিন্তু সীমার পরীক্ষা নেই |
C → Clang -O2 | ৯০ | Recursion নিজেই loop হয়ে গেছে, call মাত্র একটি |
শেষ সারিটি সবচেয়ে শিক্ষণীয়। n * fact(n - 1) tail call নয় (গুণ বাকি থাকে), তবুও Clang -O2 এটিকে একটি গুণফল জমানোর loop-এ বদলেছে (সত্যিকারের আউটপুট, directive বাদ):
~/rvgen $ python -m ziglang cc -target riscv64-linux-musl -mcpu=generic_rv64+m \
-mno-relax -O2 -S -g0 -fno-sanitize=undefined fact.c
fact:
addi sp, sp, -16
sd ra, 8(sp)
sd s0, 0(sp)
addi s0, sp, 16
li a2, 2
bge a0, a2, .LBB0_2
li a0, 1
j .LBB0_4
.LBB0_2:
mv a1, a0
li a0, 1
.LBB0_3:
mv a3, a1
addi a1, a1, -1
mul a0, a3, a0
bltu a2, a3, .LBB0_3
.LBB0_4:
ld ra, 8(sp)
ld s0, 0(sp)
addi sp, sp, 16
ret
এটি একটি পরিচিত রূপান্তরের ফল: LLVM-এর tail-call elimination pass গুণের মতো associative কাজের জন্য একটি “জমা” (accumulator) variable তৈরি করে recursion-কে loop-এ নামাতে পারে (পর্ব ৩২)। Haat-এর ক্ষেত্রে এটি করা যেত না বিনা চিন্তায়: Haat-এ ১,০০০ call-এর সীমা আচরণের অংশ, তাই fact(2000) reference-এ stack overflow দেয়, আর loop-এ বদলালে দিত না। কোনো optimization যদি দৃশ্যমান আচরণ বদলায়, তবে সেটি সেই ভাষার জন্য বৈধ নয়; C-তে recursion-এর কোনো সীমা ভাষার নিয়মে নেই, তাই Clang-এর জন্য বৈধ। লক্ষ করুন, Zig-এর সঙ্গে আসা Clang এই target-এ -O2-তেও frame pointer রাখে (s0).
৬ · Runtime, global আর runtime error
Compiler-এর লেখা কোড একা চলে না। সংখ্যা ছাপানো, error বার্তা লেখা, program শেষ করা: এসব কাজ প্রতিটি program-এর একই, তাই একবার লিখে রাখা হয় একটি runtime library-তে। বড় ভাষার runtime বিশাল (garbage collector, thread, exception), Haat-এর এই অংশের runtime ৩৮ লাইনের একটি C ফাইল। এটি freestanding C: libc নেই, printf নেই; operating system-এর সঙ্গে কথা হয় সরাসরি দুটি system call দিয়ে। RISC-V Linux-এ system call-এর নম্বর a7-এ, argument a0–a2-এ, তারপর ecall নির্দেশ (OS পর্ব ০৮-এ process আর kernel-এর সম্পর্ক)।
// haat_rt.c — Haat-এর ছোট runtime (পর্ব ৭২), freestanding C: libc নেই, Linux-এর দুটি system call (write, exit_group).
typedef long i64;
i64 haat_depth; // এখন কয়টি Haat call চলছে (সীমা ১,০০০)
void haat_main(void);
static i64 sys3(i64 n, i64 x, i64 y, i64 z) { // RISC-V Linux: নম্বর a7-এ, argument a0..a2-এ, তারপর ecall
register i64 a7 __asm__("a7") = n, a0 __asm__("a0") = x, a1 __asm__("a1") = y, a2 __asm__("a2") = z;
__asm__ volatile("ecall" : "+r"(a0) : "r"(a7), "r"(a1), "r"(a2) : "memory");
return a0;
}
static char *num(char *end, i64 v) { // দশমিক লেখা, ডান থেকে বাঁয়ে; INT_MIN-ও ঠিক (unsigned-এ উল্টানো)
unsigned long u = v < 0 ? 0UL - (unsigned long)v : (unsigned long)v;
do { *--end = (char)('0' + u % 10); u /= 10; } while (u);
if (v < 0) *--end = '-';
return end;
}
void haat_print_int(i64 v) { char b[24], *p = num(b + 23, v); b[23] = '\n'; sys3(64, 1, (i64)p, b + 24 - p); }
// …
}
void haat_div_zero(i64 line, i64 col) { fail(line, col, "division by zero", "", ""); }
void haat_stack_overflow(i64 line, i64 col) { fail(line, col, "stack overflow", "", ""); }
void haat_not_init(i64 line, i64 col, const char *name) { fail(line, col, "'", name, "' is not initialized yet"); }
void _start(void) { haat_main(); sys3(94, 0, 0, 0); for (;;) {} }বাদ দেওয়া অংশে fail: line:col: runtime error: … বার্তাটি একটি buffer-এ জোড়া দিয়ে stderr-এ (fd 2) লেখে, তারপর exit_group(1). Reference-ও error stderr-এ লেখে, আর আগে ছাপা আউটপুট থেকে যায় (সিদ্ধান্ত ২৬)। num সবচেয়ে ছোট Int-কে আগে unsigned-এ নিয়ে উল্টায়, কারণ C-তে signed -v সেখানে undefined behavior (C কোর্সের পর্ব ৪৮)। _start হলো program-এর entry point: libc না থাকায় startup code-ও নিজের, যা haat_main ডেকে exit_group(0) করে।
পর্ব ৭৪-এর প্রস্তাবের সঙ্গে মিল আর একটি পার্থক্য: পর্ব ৭৪-এর অংশ ৭ প্রস্তাব করেছিল: runtime C-তে, নাম haat_print_int আর haat_div_zero(line, col), Haat-এর নামে haat_ উপসর্গ, top-level কোড haat_main-এ, আর global-এর পাশে “initialized” flag. এই পর্ব সবগুলো হুবহু মেনেছে (আর পর্ব ৭১-এর symbol/global_symbol-ও এই নামই দেয়)। পার্থক্য একটি: সেখানে haat_main-কে libc-র main ডাকত (_start → libc → main); এখানে libc নেই, runtime-এর নিজের _start সরাসরি haat_main ডাকে। কারণ: libc-র startup অনেক system call আর auxiliary vector চায়, যা emulator-এ বানাতে হতো; দুটি system call-এর runtime যেকোনো RISC-V Linux-এও চলবে, emulator-এও।
Global আর “not initialized yet”
Haat-এ top-level function শুরু থেকেই দেখা যায় (সিদ্ধান্ত ১৭), তাই একটি function তার ব্যবহার করা global-এর let চলার আগেই ডাকা হতে পারে, আর তখন reference বলে 'k' is not initialized yet (সিদ্ধান্ত ১৮)। যন্ত্রে মেমরির ঘর সবসময়ই কোনো না কোনো মান ধরে, তাই “এখনো লেখা হয়নি” আলাদা করে মনে রাখতে হয়: haat_g_k-এর পরের ৮ byte একটি flag. let/var (IR-এ @k = t, অবস্থান ছাড়া) flag-এ 1 লেখে; পড়া (t = @k) আর function-এর ভেতরের assignment (@k = t, অবস্থান-সহ) আগে flag দেখে। তৈরি কোড, fn bump() { k = k + 1; }-এর জন্য:
haat_bump: ...
la t1, haat_g_k .data
ld t0, 8(t1) .globl haat_g_k
beqz t0, .Lhaat_bump_ni1 haat_g_k: .dword 0, 0
ld t0, 0(t1) .section .rodata
addi t0, t0, 1 .Lname_k: .asciz "k"
la t1, haat_g_k
ld t2, 8(t1) .Lhaat_bump_ni1:
beqz t2, .Lhaat_bump_ni2 li a0, 2
sd t0, 0(t1) li a1, 17
la a2, .Lname_k
call haat_not_init
la একটি pseudo-instruction: assembler এটিকে auipc + addi-তে বদলায়, ঠিকানাটি বসায় linker (পর্ব ৭৪-এর relocation). মান আগে হিসাব হয়, তারপর লেখার আগে flag দেখা হয়: reference-এর ক্রমও তাই। দুটি পরীক্ষা পরপর একই flag পড়ে; একটি চতুর optimizer দ্বিতীয়টি সরাতে পারত, কারণ মাঝে কেউ flag বদলায় না।
সব জোড়া লাগার পরে ELF-এর symbol table (সত্যিকারের run, pyelftools 0.33 দিয়ে পড়া, bazar.elf):
~/rvgen $ python -m ziglang cc -target riscv64-linux-musl -mcpu=generic_rv64+m \
-mno-relax -O2 -ffreestanding -fno-builtin -fno-sanitize=undefined \
-c haat_rt.c -o haat_rt.o
~/rvgen $ python -m ziglang cc -target riscv64-linux-musl -mcpu=generic_rv64+m \
-mno-relax -nostdlib -static -o bazar.elf bazar.s haat_rt.o
entry 0x10017fc ET_EXEC EM_RISCV .text 1820 byte .bss 8 byte
0x100136c 164 FUNC GLOBAL haat_print_int
0x1001410 88 FUNC GLOBAL haat_print_bool
0x1001468 44 FUNC GLOBAL haat_div_zero
0x10017a4 44 FUNC GLOBAL haat_stack_overflow
0x10017d0 44 FUNC GLOBAL haat_not_init
0x10017fc 48 FUNC GLOBAL _start
0x100182c 0 FUNC GLOBAL haat_main
0x1002a88 8 OBJECT GLOBAL haat_depth
0x10019d4 0 FUNC GLOBAL haat_price
0x1001a40 0 FUNC GLOBAL haat_delivery
Entry point _start-এর ঠিকানা। Runtime-এর function-গুলোর আকার আছে (C compiler .size লেখে), Haat-এর function-গুলোর আকার 0, কারণ haat_rv.py .size লেখে না; চলায় এতে কিছু আসে যায় না, তবে debugger-এর জন্য লেখা উচিত। .text-এর ১,৮২০ byte-এর মধ্যে runtime ১,২১৬ আর Haat-এর কোড ৬০৪ byte, অর্থাৎ ১৫১টি ৪ byte-এর নির্দেশ। -mno-relax linker-কে নির্দেশ ছোট করতে দেয় না, তাই assembly-র প্রতিটি লাইন ELF-এ চেনা যায়।
৭ · চালিয়ে প্রমাণ — Clang, Unicorn আর ব্রাউজার
একটি code generator-এর ভুল প্রায়ই চুপচাপ: assembler কোনো আপত্তি করে না, program চলে, শুধু একটি সংখ্যা ভুল। তাই বিশ্বাসের একমাত্র ভিত্তি চালিয়ে দেখা। লেখকের lab-এ (Windows, CPython 3.14.4) তিন স্তরে:
- Differential test: পর্ব ৬২-এর
haat_genদিয়ে seed 0 থেকে 2999-এর ৩,০০০টি এলোমেলো program, আর reference-এর ১৩টি উদাহরণ। প্রতিটিhaat_rv.pyদিয়ে.s, Clang 22.1.8 দিয়ে ELF, PyPI-রunicorn2.1.4-এ চালানো (emulator; Python binding BSD, ভেতরের engine QEMU-ভিত্তিক বলে GPLv2; শুধু lab-এ ব্যবহার); আউটপুট (stdout, তারপর stderr) মেলানো reference-এরpython -B haat.py run-এর সঙ্গে। ফল: ৩,০০৩টি program অক্ষরে অক্ষরে এক, অমিল ০। এর ৩২৫টি শূন্য দিয়ে ভাগে থামে, বার্তা আরline:col-সহ। বাদ গেছে ১০টি উদাহরণ: ৫টিতে Str, একটিতে closure, একটিতে nested function, আর ৩টি ইচ্ছাকৃত static error-এর program, যা reference চালায়ই না (এই pipeline-এ type checker নেই)। এলোমেলো program-গুলোর একটিও বাদ যায়নি। - হাতে লেখা প্রান্তের program: ৯টি, প্রতিটি একটি নিয়ম ধরতে: global পড়া আর assignment-এর আগে initialized না হওয়া, ১,০০০-এর সীমা ঠিক সীমানায় (
d(999)চলে,d(1000)-এstack overflow), অসীম recursion, সবচেয়ে ছোট Int-এর/ -1আর% -1, Bool parameter আর ফল, দশ argument-এর call, variable ভাজকে শূন্য। ৯টিই reference-এর সঙ্গে এক। - প্রতিটি call-এ ABI পরীক্ষা: ৩০০টি এলোমেলো program আর ৩টি উদাহরণে, প্রতিটি function-এ ঢোকার মুহূর্তে
sp % 16 == 0, আর ফেরার মুহূর্তেsp,s0–s11আগের মানে। ২৬,৬৬০টি ঢোকা (runtime-এর function-সহ), নিয়ম-ভঙ্গ ০, সবচেয়ে গভীর ২২।
Emulator আর ব্রাউজারের interpreter আলাদা জিনিস গোনে, সেটিও মনে রাখার মতো। পর্ব ৬৯-এর rv_text.py শুধু register-এর কাজ জানত, memory আর call জানত না। এই পর্বের rv_run.py তার ALU আর শাখার টেবিল হুবহু নেয়, আর যোগ করে ৮ byte-এর memory (ld/sd), la, call/ret আর runtime-এর পাঁচটি function-এর Python রূপ। এটি assembly-র লাইন গোনে: call বা la এক লাইন, যদিও যন্ত্রে দুটি নির্দেশ। bazar.haat-এ ব্রাউজার গোনে ১৭১, Unicorn গোনে Haat-কোডের ১৮৮টি আসল নির্দেশ (আর runtime-এর ১৮৩টি)।
# তৈরি assembly ব্রাউজারেই চালানো (rv_run.py), আর পর্ব ৬২-এর IR interpreter-এর সঙ্গে মেলানো
from haat_rv import *
from rv_run import run_program
progs = {
"bazar": open("examples/bazar.haat", encoding="utf-8").read(),
"fact": "fn fact(n: Int) -> Int {\n if n <= 1 { return 1; }\n return n * fact(n - 1);\n}\nprint(fact(20));\n",
"mutual": open("examples/mutual.haat", encoding="utf-8").read(),
"early": "print(f());\nlet k = 5;\nfn f() -> Int { return k + 1; }\n",
"deep": "fn down(n: Int) -> Int { return down(n + 1); }\nprint(down(0));\n",
"share": "fn share(t: Int, n: Int) -> Int { return t / n; }\nprint(share(1000, 4));\nprint(share(1000, 0));\n",
}
for name, src in progs.items():
out, steps = run_program(compile_rv(src))
same = out == run_lines(compile_ir(src))
print(f"{name:7} {steps:6} নির্দেশ · IR-এর সঙ্গে {'এক' if same else 'আলাদা!'} · {' | '.join(out)}")আসল আউটপুট (ব্রাউজারের Python):
bazar 171 নির্দেশ · IR-এর সঙ্গে এক · 996 | 5000 | 3
fact 628 নির্দেশ · IR-এর সঙ্গে এক · 2432902008176640000
mutual 656 নির্দেশ · IR-এর সঙ্গে এক · true | true | false
early 22 নির্দেশ · IR-এর সঙ্গে এক · 3:24: runtime error: 'k' is not initialized yet
deep 16012 নির্দেশ · IR-এর সঙ্গে এক · 1:33: runtime error: stack overflow
share 62 নির্দেশ · IR-এর সঙ্গে এক · 250 | 1:44: runtime error: division by zero
ছয়টি program-এর সবকটিতে তৈরি assembly-র আউটপুট পর্ব ৬২-এর IR interpreter-এর (যা নিজে reference-এর সঙ্গে মেলানো) হুবহু। early-তে f চলেছে let k-এর আগে, তাই flag 0, আর error ঠিক k-এর অবস্থানে (3:24). deep-এ ১,০০০টি call পর্যন্ত চলে ১,০০১তম call-এ থামে; ১৬,০১২টি লাইনের প্রায় সবই call-এর সীমা গোনার কাজ, যা এই back end-এর একটি দৃশ্যমান খরচ। share-এ প্রথম print 250 ছাপার পরে দ্বিতীয় call-এ ভাগের আগে beqz ধরেছে শূন্য, আর বার্তার অবস্থান /-এর (সিদ্ধান্ত ২৪)।
এবার ব্রাউজারেই একটি ছোট differential test: পর্ব ৬২-এর ৯টি উদাহরণ (ভারী recursion.haat বাদ, সেটি lab-এ চালানো) আর প্রথম ১০০টি এলোমেলো program, ফল মেলানো reference-এর জমা রাখা আউটপুটের সঙ্গে।
# Differential test ব্রাউজারে: Haat -> assembly -> rv_run, বনাম reference-এর আউটপুট (.out আর random_ref.txt)
import hashlib
from haat_rv import *
from rv_run import run_program
from haat_gen import gen_program
digest = lambda lines: hashlib.sha256("\n".join(lines).encode()).hexdigest()[:10]
ref = open("random_ref.txt").read().split()
same = diff = 0; skipped = {}
cases = [(n, open(f"examples/{n}.haat", encoding="utf-8").read(),
digest(open(f"examples/{n}.out", encoding="utf-8").read().split("\n")[:-1]))
for n in ("bazar", "mutual", "shadowing", "shortcircuit", "strings", "loops", "err_divzero", "counter", "nested")]
cases += [(f"seed{s}", gen_program(s), ref[s]) for s in range(100)]
for name, src, want in cases:
try: asm = compile_rv(src)
except Unsupported as e: skipped[name] = str(e).split(": ")[-1]; continue
out, steps = run_program(asm)
if digest(out) == want: same += 1
else: diff += 1; print("আলাদা:", name)
print(f"এক: {same} · আলাদা: {diff} · বাদ: {len(skipped)}")
for name, why in skipped.items(): print(f" বাদ {name}: {why}")আসল আউটপুট (ব্রাউজারের Python):
এক: 102 · আলাদা: 0 · বাদ: 7
বাদ shadowing: Str values are not selected here
বাদ shortcircuit: Str values are not selected here
বাদ strings: Str values are not selected here
বাদ loops: Str values are not selected here
বাদ err_divzero: Str values are not selected here
বাদ counter: closures and function values are not in Haat IR v1
বাদ nested: nested functions are not in Haat IR v1
যা চালানো গেছে, তার একটিতেও অমিল নেই। বাদের তালিকাটিও একটি ফল: এই back end কী পারে না, তা সে চুপচাপ ভুল কোড লিখে নয়, স্পষ্ট Unsupported দিয়ে জানায়। Str-এর পাঁচটি উদাহরণ থেমেছে পর্ব ৬৯-এর block_trees-এ, আর closure ও nested function থেমেছে আরও আগে, পর্ব ৬২-এর lowering-এ। ভুল কোড লেখার চেয়ে “পারি না” বলা সবসময় ভালো।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
if (a < b) x = 1; else x = 2;-এর assembly লিখুন। তুলনা উল্টে লাফ:bge a, b, ELSE, then-অংশ,j END,ELSE:else-অংশ,END:.- Recursive function-এর প্রতিটি call-এ কী নতুন হয়? শুধু frame (activation record): নতুন
ra, parameter আর local; কোড একটিই। - Code generator-এর তিনটি মূল কাজ? Instruction selection, register allocation, আর নির্দেশের ক্রম ঠিক করা (instruction scheduling); সঙ্গে frame আর call-এর ক্রম।
- Runtime library কেন লাগে? প্রতিটি program-এ একই কাজ (I/O, error, memory, startup) একবার লিখে link করা হয়, compiler প্রতিবার লেখে না।
- শূন্য দিয়ে ভাগে RISC-V কী করে? থামে না:
divদেয় −1 (সব বিট 1),remদেয় ভাজ্য; তাই ভাষাকে নিজে পরীক্ষা বসাতে হয়।
৮ · কী বাদ, কী বাকি — আর আসল compiler-এর back end
নিচের JavaScript ব্লক দুটি fact-এর static নির্দেশ ধরন অনুযায়ী গোনে: এই back end-এর haat_fact আর অংশ ৫-এর Clang -O2-এর fact. দুটি listing ব্লকের ভেতরে লেখা, সত্যিকারের আউটপুট থেকে কপি করা।
// দুটি RISC-V listing-এর নির্দেশ ধরন অনুযায়ী গোনা: এই back end-এর haat_fact বনাম Clang -O2-এর fact
const haat = `addi sp,sp,-80;sd ra,72(sp);sd s0,64(sp);addi s0,sp,80;sd a0,-24(s0);ld t0,-24(s0);li t1,1;
blt t1,t0,B2;li a0,1;ld ra,72(sp);ld s0,64(sp);addi sp,sp,80;ret;ld t0,-24(s0);addi t0,t0,-1;sd t0,-64(s0);
la t0,haat_depth;ld t1,0(t0);li t2,1000;bge t1,t2,so1;addi t1,t1,1;sd t1,0(t0);ld a0,-64(s0);call haat_fact;
sd a0,-72(s0);la t0,haat_depth;ld t1,0(t0);addi t1,t1,-1;sd t1,0(t0);ld t0,-24(s0);ld t1,-72(s0);mul a0,t0,t1;
ld ra,72(sp);ld s0,64(sp);addi sp,sp,80;ret;li a0,3;li a1,16;call haat_stack_overflow`;
const clang = `addi sp,sp,-16;sd ra,8(sp);sd s0,0(sp);addi s0,sp,16;li a2,2;bge a0,a2,L2;li a0,1;j L4;
mv a1,a0;li a0,1;mv a3,a1;addi a1,a1,-1;mul a0,a3,a0;bltu a2,a3,L3;ld ra,8(sp);ld s0,0(sp);addi sp,sp,16;ret`;
const KIND = { ld: "memory", sd: "memory", la: "ঠিকানা/ধ্রুবক", li: "ঠিকানা/ধ্রুবক", mv: "ঠিকানা/ধ্রুবক",
call: "call/ret", ret: "call/ret", j: "শাখা", blt: "শাখা", bge: "শাখা", bltu: "শাখা" };
function count(text) {
const c = {}; const ins = text.replace(/\n/g, "").split(";");
for (const s of ins) { const op = s.split(" ")[0]; const k = KIND[op] || "হিসাব (ALU)"; c[k] = (c[k] || 0) + 1; }
return [ins.length, c];
}
const [nh, ch] = count(haat), [nc, cc] = count(clang);
console.log("ধরন".padEnd(16) + "haat_fact Clang -O2");
for (const k of ["memory", "হিসাব (ALU)", "শাখা", "ঠিকানা/ধ্রুবক", "call/ret"])
console.log(k.padEnd(16) + String(ch[k] || 0).padStart(9) + String(cc[k] || 0).padStart(11));
console.log("মোট".padEnd(16) + String(nh).padStart(9) + String(nc).padStart(11));
const where = r => haat.replace(/\n/g, "").split(";").filter(s => /^(ld|sd) /.test(s) && s.endsWith(r)).length;
console.log(`haat_fact-এর memory: slot ${where("(s0)")}টি, haat_depth ${where("(t0)")}টি, frame record ${where("(sp)")}টি`);আসল আউটপুট:
ধরন haat_fact Clang -O2
memory 18 4
হিসাব (ALU) 8 5
শাখা 2 3
ঠিকানা/ধ্রুবক 7 5
call/ret 4 1
মোট 39 18
haat_fact-এর memory: slot 8টি, haat_depth 4টি, frame record 6টি
পার্থক্যের বড় অংশ memory-তে: এই back end-এর ৩৯টি নির্দেশের ১৮টি ld/sd (৮টি slot, ৪টি haat_depth, ৬টি frame record, কারণ দুটি return-এর দুটি epilogue), Clang-এর শুধু frame record-এর চারটি। এটিই register allocation-এর কাজ (পর্ব ৭০), আর পর্ব ৭০-এর allocate Haat IR-এর নামগুলোকে register-এ বসাতে পারে; এই পর্বে সেটি ইচ্ছা করে ব্যবহার করা হয়নি, যাতে frame আর call-এর প্রতিটি লাইন পর্ব ৭১-এর চুক্তির সঙ্গে সরাসরি মেলানো যায়। বাকি পার্থক্য সীমা-পরীক্ষার (la, li, bge আর error-এর পথ), যা Clang-এর নেই কারণ C-র নেই।
এই back end যা জানে না, তার তালিকা পরের পর্বগুলোর মানচিত্রও:
- Str: একটি string-এর আকার আগে জানা যায় না, জোড়া দিলে নতুন string তৈরি হয়, তাই heap আর garbage collection লাগে (পর্ব ২১, পর্ব ৭৫)।
- Closure আর nested function: ধরা variable-এর cell heap-এ রাখতে হয় (পর্ব ৫৭, পর্ব ১৭); Haat IR v1 নিজেই এগুলো বাদ রাখে।
- Register allocation আর optimization: পর্ব ৭০-এর allocator আর পর্ব ৬৫-এর optimizer এই pipeline-এর আগে বসালে কোড অনেক ছোট হতো; প্রতিটি নতুন pass-এর পরে একই differential test আবার চালাতে হবে।
- অন্য target: একই IR থেকে WebAssembly, যেখানে register নেই, structured control flow আছে (পর্ব ৭৩)। ক্যাপস্টোন পর্ব ৮১ (Haat-এর পূর্ণ compiler) এই পর্বের
compile_rvআবার ব্যবহার করবে।
আরও গভীরে: আসল compiler-এর back end একই ধাপগুলো অনেক বেশি স্তরে করে। LLVM-এ IR প্রথমে SelectionDAG বা GlobalISel দিয়ে target-এর MachineInstr-এ নামে, তারপর register allocation, তারপর prologue/epilogue বসানোর আলাদা pass (PrologEpilogInserter), শেষে MC স্তর assembly বা সরাসরি object file লেখে; target-এর নির্দেশ আর calling convention-এর বড় অংশ TableGen বর্ণনা থেকে তৈরি হয়। GCC-তে GIMPLE থেকে RTL, আর RTL-এর ওপর একই ধরনের কাজ। এই পর্বের ছোট back end আর সেগুলোর মূল পার্থক্য স্তরে নয়, পরিমাণে: হাজারো pattern, scheduling, আর বহু বছরের ভুল-ধরা পরীক্ষা।
৯ · AI-এর যুগে code generation
AI assistant-কে “এই function-এর RISC-V assembly লেখো” বললে উত্তর সাধারণত দেখতে বিশ্বাসযোগ্য। কিন্তু অংশ ৭-এর মূল শিক্ষা মনে রাখুন: code generator-এর ভুল চুপচাপ থাকে। যে assembly assemble হয় আর একটি উদাহরণে ঠিক উত্তর দেয়, সেটিও অন্য ইনপুটে ভুল হতে পারে।
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
শাখার operand-এর ক্রম উল্টে ফেলা (n <= 1-এর জন্য blt t0, t1) | সীমানার মানে চালানো: fact(0), fact(1), fact(2); অনুশীলন ২ দেখুন |
RISC-V-এর div শূন্যে trap করে বলে ধরে নেওয়া, বা x86-এর নিয়ম RISC-V-তে চাপানো | RISC-V spec-এর M extension অংশ পড়া; শূন্য ভাজকে emulator-এ চালানো |
Call-এর পরে caller-saved register (t0, a1) টিকে আছে ধরে নেওয়া | পর্ব ৭১-এর নিয়ম; call-এর পরে সেই register পড়া প্রতিটি লাইন খোঁজা |
| “Optimization”-এ ভাষার আচরণ বদলানো: সীমা-পরীক্ষা বা শূন্যের পরীক্ষা সরিয়ে দেওয়া | Reference-এর error-ওয়ালা program-এ differential test; ১,০০০-এর সীমানায় পরীক্ষা |
| বানানো pseudo-instruction বা flag, বা ভুল version-এর Clang-এর আউটপুট দেখানো | সত্যিকারের assembler-এ assemble করা; --version লিখে রাখা |
AI-কে কাজে লাগাতে আগে চুক্তি আর যাচাইয়ের পথ বলে দিন:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১“প্রতিটি মান stack-এ” নীতির back end ধীর। তবুও compiler লেখার প্রথম ধাপে, আর আসল compiler-এর -O0-তে, কেন এই নীতিই বেছে নেওয়া হয়?
প্রথম কারণ সঠিকতা। একটি back end-এ সবচেয়ে কঠিন ভুলগুলো আসে দুটি জায়গা থেকে: কোন মান কোন register-এ আছে, আর একটি call সেই register নষ্ট করল কি না। প্রতিটি মান নিজের slot-এ থাকলে দুটি প্রশ্নই উধাও: statement শেষ হলেই সব register “খালি”, call-এর পরে কোনো register-এর ওপর ভরসা নেই। এই পর্বের নিয়ম ৭২.১ ঠিক এটুকুই বলে, আর তার ফলে Haat back end-এর পুরো কোড ৮২ লাইনে আঁটে, আর ৩,০০৩টি program-এ একটিও অমিল নেই। এটি কাকতালীয় নয়: যত কম অবস্থা মনে রাখতে হয়, ভুলের জায়গা তত কম।
দ্বিতীয় কারণ debugging. Clang আর GCC -O0-তে প্রতিটি variable-কে নিজের ঠিকানায় রাখে, যাতে debugger যেকোনো লাইনে থেমে variable-এর মান দেখাতে আর বদলাতে পারে। Register-এ রাখা মান লাইনে লাইনে জায়গা বদলায়, কখনো হারিয়েও যায় (“optimized out”). অংশ ৫-এর মাপে Clang -O0-এর fact(20) ৪৬৮টি নির্দেশ, Haat-এর এই back end ৬৮৯টি: দুটিই একই নীতির, পার্থক্য প্রধানত Haat-এর সীমা-পরীক্ষায়।
তৃতীয় কারণ পরিমাপের ভিত্তি। একটি সরল, ধীর কিন্তু নিশ্চিতভাবে সঠিক back end থাকলে প্রতিটি উন্নতি (register allocation, peephole, constant folding) তার সঙ্গে তুলনা করে মাপা যায়: গতি কত বাড়ল, আর আউটপুট এখনো এক কি না। Compiler গবেষণায় এই ধরনের “reference” back end বা interpreter প্রায় সবসময় রাখা হয়। এই কোর্সেও তাই: reference interpreter → IR interpreter → এই back end, প্রতিটি আগেরটির সঙ্গে মেলানো।
দাম অবশ্য বাস্তব। Clang -O2-এর ৯০টি নির্দেশের তুলনায় ৬৮৯ প্রায় আট গুণ, আর memory-র প্রতিটি ছোঁয়া cache-এর ওপর চাপ ফেলে (Computer Architecture-এর memory hierarchy). তাই কোনো আসল compiler এখানে থামে না; কিন্তু প্রায় সবাই এখান থেকেই শুরু করে।
মূল উপলব্ধি: প্রথম back end-এর লক্ষ্য গতি নয়, প্রমাণযোগ্য সঠিকতা; সেই ভিত্তির ওপর প্রতিটি optimization মাপা আর যাচাই করা যায়।
প্র ০২RISC-V শূন্য দিয়ে ভাগে থামে না, x86-64 থামে (exception), আর WebAssembly trap করে। এই পছন্দগুলো কেন আলাদা, আর একটি ভাষা কেন hardware-এর ওপর নির্ভর না করে নিজেই পরীক্ষা বসায়?
RISC-V-এর নির্দেশমালার নথি (M extension) নিজেই কারণ বলে: শূন্য দিয়ে ভাগে trap না রেখে একটি নির্দিষ্ট ফল দেওয়া হয়েছে (ভাগফলের সব বিট 1, ভাগশেষ = ভাজ্য)। নথির যুক্তি মোটামুটি এই: trap রাখলে এটিই হতো মূল নির্দেশমালার একমাত্র গাণিতিক trap, আর ভাষার implementation-কে execution environment-এর trap handler নিয়ে কাজ করতে হতো; যে ভাষার তাৎক্ষণিক error দরকার, সে প্রতিটি ভাগে একটি শাখা-নির্দেশ যোগ করতে পারে, যা প্রায় সবসময় একই দিকে যায় বলে খরচ সামান্য। Haat-এর back end শাখাটি ভাগের আগে বসায়। x86-এ idiv শূন্যে বা ছোট সংখ্যার overflow-এ divide error exception তোলে, যা operating system signal হিসেবে program-এ পাঠায় (Linux-এ SIGFPE). WebAssembly-তে i64.div_s শূন্যে আর সবচেয়ে ছোট সংখ্যাকে −1 দিয়ে ভাগে trap করে (পর্ব ৭৩ এটি সত্যিকারের run-এ দেখিয়েছে)।
তিনটি আচরণের কোনোটিই Haat-এর নিয়মের সঙ্গে হুবহু মেলে না। Haat চায় একটি নির্দিষ্ট বার্তা, /-এর অবস্থান, আগে ছাপা আউটপুট রেখে program শেষ; আর সবচেয়ে ছোট Int-কে −1 দিয়ে ভাগে কোনো error নয়, wrap (সিদ্ধান্ত ১৩)। x86-এর exception বা Wasm-এর trap ধরে সেই বার্তায় বদলানো যেত, কিন্তু তখন অবস্থান জানতে আলাদা টেবিল লাগত, আর সবচেয়ে ছোট Int-এর ক্ষেত্রে ভুলভাবে error হতো। নিজে পরীক্ষা বসানো সরল আর সব target-এ এক রকম: RISC-V-এ শুধু শূন্যের পরীক্ষা, Wasm-এ শূন্য আর −1 দুটিই।
C আরেকটি পথ নিয়েছে: শূন্য দিয়ে ভাগ undefined behavior, অর্থাৎ ভাষা কিছুই নিশ্চিত করে না, যাতে compiler যেকোনো hardware-এ সবচেয়ে সস্তা নির্দেশটি দিতে পারে। এর দাম নিরাপত্তায়: compiler ধরে নিতে পারে যে ভাজক কখনো শূন্য নয়, আর সেই ধারণার ওপর অন্য কোড সরিয়ে দিতে পারে (C কোর্সের পর্ব ৪৮)। Java (ArithmeticException), Python (ZeroDivisionError) আর Rust (debug ও release দুই রূপেই panic) নিজেদের নিয়ম লিখেছে, আর তাদের compiler বা VM প্রতিটি target-এ সেই নিয়ম পূরণের কোড বসায়।
Haat-এর back end তাই একটি সাধারণ নীতির উদাহরণ: ভাষার semantics হলো চুক্তি, hardware শুধু উপাদান। Compiler-এর কাজ hardware-এর যেকোনো আচরণ থেকে ভাষার চুক্তিটি তৈরি করা; কোথাও বিনা খরচে মেলে (wrap, সবচেয়ে ছোট Int-এর ভাগ), কোথাও একটি শাখা লাগে (শূন্য)।
মূল উপলব্ধি: ভাষার নিয়ম ঠিক করে কী ঘটবে, hardware ঠিক করে কত খরচে; যেখানে দুটি মেলে না, সেখানে compiler পরীক্ষা বসায়।
প্র ০৩এই পর্বের runtime C-তে লেখা, কিন্তু অন্য ভাষার runtime নানা ভাষায়: Go-র runtime Go-তে, Java-র HotSpot C++-এ, CPython C-তে। একটি ভাষার runtime কোন ভাষায় লিখবেন, তা ঠিক করে কী?
Runtime-এর কাজ এমন সব কিছু, যা compiler-এর লেখা কোড নিজে করতে পারে না বা করা উচিত নয়: operating system-এর সঙ্গে কথা বলা (I/O, memory চাওয়া, thread), ভাষার নিয়ম ভাঙলে কী করতে হবে (error, exception, panic), আর বড় যন্ত্রপাতি (garbage collector, scheduler, JIT). এসব লিখতে এমন একটি ভাষা লাগে যা machine-এর কাছাকাছি যেতে পারে, অথচ যার নিজের runtime ছোট বা নেই। তাই ঐতিহাসিকভাবে C সবচেয়ে সাধারণ পছন্দ: CPython, Ruby-র প্রধান implementation আর অনেক Lisp ও ML-ধাঁচের ভাষার runtime-এর বড় অংশ C-তে।
এই পর্বের runtime আরও এক ধাপ নিচে গেছে: freestanding C, libc ছাড়া। কারণ libc নিজেই একটি runtime, যার startup অনেক কিছু চায় (auxiliary vector, thread-local storage, stdio-র buffer); emulator-এ সেগুলো বানানো Haat শেখার কাজ নয়। দুটি system call আর একটি _start দিয়ে program সম্পূর্ণ, আর ELF-টি যেকোনো RISC-V Linux-এ চলার কথা (এই lab-এ শুধু Unicorn-এ চালানো হয়েছে, আসল যন্ত্রে নয়)। Rust-এর no_std আর C-র freestanding implementation-এর ধারণা একই: ভাষার একটি অংশ, যা libc বা operating system ছাড়াও চলে, যেমন kernel বা microcontroller-এ।
অন্য পথ হলো ভাষাকে নিজের runtime নিজে লিখতে সক্ষম করা। Go-র runtime মূলত Go-তে, কিছু assembly-সহ; garbage collector আর scheduler নিজেই Go কোড, তবে বিশেষ নিয়মে compile হয় (যেমন যে কোড heap-এ কিছু চাইতে পারবে না)। এতে একটি ভাষাতেই সব থাকে, কিন্তু “runtime-এর runtime” নিয়ে সতর্ক থাকতে হয়। Java-র HotSpot JVM C++-এ লেখা; GraalVM-এর মতো প্রকল্প Java-তে Java VM লেখার চেষ্টা করেছে। Haat-এর ক্ষেত্রেও একদিন haat_print_int Haat-এ লেখা যেত, যদি Haat-এ memory আর system call ছোঁয়ার উপায় থাকত; এখন নেই।
সিদ্ধান্তের মাপকাঠি তাই কয়েকটি: runtime-কে যে কাজ করতে হবে তা ভাষাটি প্রকাশ করতে পারে কি না, runtime নিজে কোন runtime-এর ওপর নির্ভর করবে, আর ABI-র মিল: compiler-এর লেখা কোড আর runtime একই calling convention মানতে হবে (পর্ব ৭১), যা এই পর্বে Clang আর haat_rv.py দুজনেই psABI মেনে নিশ্চিত করেছে।
মূল উপলব্ধি: Runtime-এর ভাষা বেছে নেওয়া হয় machine-এর কাছাকাছি যাওয়ার ক্ষমতা আর নিজের নির্ভরতা কম রাখার জন্য; যে ভাষাতেই লেখা হোক, সংযোগটি ABI.
প্র ০৪একটি compiler-এর back end সঠিক, তা কীভাবে জানবেন? Differential testing, এলোমেলো program আর formal verification-এর ভূমিকা তুলনা করুন।
এই পর্বের প্রমাণ differential testing: একই program দুটি স্বাধীন implementation-এ চালিয়ে আউটপুট মেলানো। এখানে একদিকে reference-এর tree-walking interpreter, অন্যদিকে IR → assembly → Clang → emulator. দুটির মধ্যে প্রায় কোনো কোড ভাগ করা নেই (parser ছাড়া), তাই দুটি একই ভুল একই জায়গায় করার সম্ভাবনা কম। এলোমেলো program এর শক্তি বাড়ায়, কারণ মানুষ যেসব সমন্বয় ভাবে না (ঋণাত্মক ভাজক, শূন্য দিয়ে ভাগ, তিন স্তরের loop-এর ভেতরে call) generator সেগুলো তৈরি করে। এখানে ৩,০০০টির ৩২৫টি শূন্য দিয়ে ভাগে থেমেছে, যা হাতে লেখা পরীক্ষায় এত বেশি আসত না।
এই পদ্ধতির বড় উদাহরণ Csmith (Yang, Chen, Eide আর Regehr, PLDI ২০১১): এলোমেলো কিন্তু undefined behavior-মুক্ত C program তৈরি করে GCC আর LLVM-এর আউটপুট মেলানো, যা শত শত compiler bug খুঁজে দিয়েছে। পরে আরও কৌশল এসেছে, যেমন একই program-এর এমন রূপান্তর যা আচরণ বদলায় না (Equivalence Modulo Inputs, ২০১৪ সালের দিকে), যাতে একটি compiler-কে নিজের সঙ্গেই মেলানো যায়। Fuzzing-এর সাধারণ ধারণা Software Testing কোর্সের পর্ব ৬০-এ।
কিন্তু পরীক্ষা শুধু ভুলের উপস্থিতি দেখায়, অনুপস্থিতি নয়। ৩,০০৩টি মিল মানে এই generator যে ধরনের program বানায়, সেখানে ভুল পাওয়া যায়নি; generator যদি কখনো ৮টির বেশি argument বা খুব গভীর গাছ না বানায়, সেই পথ অপরীক্ষিত থাকে। এজন্যই এই পর্বে আলাদা করে হাতে লেখা প্রান্তের program (দশ argument, সীমার ঠিক সীমানা) আর ABI পরীক্ষা চালানো হয়েছে।
সম্পূর্ণ নিশ্চয়তার পথ formal verification: CompCert (Xavier Leroy আর সহকর্মীরা, ২০০৬ সালের দিক থেকে) একটি C compiler, যার প্রতিটি pass Coq-এ প্রমাণ করা যে source-এর অর্থ রাখে (পর্ব ৪৪)। Csmith-এর গবেষকেরা জানিয়েছিলেন, CompCert-এর প্রমাণিত অংশে তাঁরা কোনো ভুল পাননি, ভুল পেয়েছিলেন শুধু অপ্রমাণিত অংশে। মাঝামাঝি একটি পথ translation validation: প্রতিটি compile-এর পরে আলাদা একটি পরীক্ষক দেখে যে এই নির্দিষ্ট input-output জোড়া সমতুল্য। বাস্তবে বড় compiler তিনটিই মেশায়: বিশাল test suite, fuzzing, আর ছোট গুরুত্বপূর্ণ অংশে প্রমাণ।
মূল উপলব্ধি: Differential test আর এলোমেলো program ভুল খোঁজার সবচেয়ে সস্তা আর কার্যকর পথ, কিন্তু সঠিকতার প্রমাণ নয়; প্রমাণ চাইলে formal verification লাগে।
প্র ০৫অংশ ৫-এ Clang -O2 recursive fact-কে loop বানিয়েছে। Haat-এর back end একই কাজ করলে কোন নিয়ম ভাঙত? একটি optimization বৈধ কি না, তা কে ঠিক করে?
একটি optimization বৈধ, যদি সেটি program-এর দৃশ্যমান আচরণ না বদলায়, আর দৃশ্যমান কী, তা ঠিক করে ভাষার semantics. C-তে দৃশ্যমান আচরণ মোটামুটি I/O আর volatile-এর ব্যবহার; একটি function কতবার নিজেকে ডাকল, stack কত গভীর হলো, তা C-র নিয়মে দৃশ্যমান নয়। তাই Clang n * fact(n - 1)-কে গুণফল জমানোর loop-এ বদলাতে পারে: গুণ associative, আর ২৬৪-এর ভাগশেষে করা unsigned বা wrap-এর গুণও associative, তাই ক্রম বদলালেও ফল একই। (C-র signed overflow undefined, তাই সেখানে compiler আরও স্বাধীন।)
Haat-এ দৃশ্যমান আচরণের তালিকা বড়। সিদ্ধান্ত ২৬ বলে, ১,০০০টির বেশি nested call-এ stack overflow, আর সেই বার্তা stderr-এ যায়, অবস্থানসহ। fact(2000) তাই reference-এ একটি error; loop-এ বদলালে সেটি একটি সংখ্যা ছাপত (wrap হওয়া গুণফল)। আউটপুট আলাদা, অতএব রূপান্তরটি Haat-এর জন্য অবৈধ, যদিও একই কোড C-তে বৈধ। এখানে Haat-এর নকশাকারী একটি সিদ্ধান্তের মুখে: call-এর সীমাকে ভাষার চুক্তির অংশ রাখবেন, নাকি “implementation-এর সীমা” বলে ছাড় দেবেন? অনেক ভাষা দ্বিতীয় পথ নেয়: Python-এ recursion limit বদলানো যায় আর এটি CPython-এর নিয়ম; Scheme (R7RS-এর মতো মানদণ্ড) উল্টো দিকে proper tail call বাধ্যতামূলক করে, যাতে tail-position-এর call stack না বাড়ায়।
Compiler-এর লেখকের জন্য এর অর্থ: প্রতিটি optimization-এর আগে প্রশ্ন করতে হবে, এটি কোন সমতা রক্ষা করে। পর্ব ৬৫-এর optimizer ঠিক এজন্যই ভাগকে “essential” ধরেছিল: যে ভাগ শূন্যে error দিতে পারে, তা ফল অব্যবহৃত হলেও মোছা যায় না। একই যুক্তিতে এই back end-এর সীমা-পরীক্ষাও কোনো optimizer সরাতে পারবে না, যদি না সে প্রমাণ করে যে গভীরতা কখনো ১,০০০ ছোঁবে না।
ভাষা-নকশার দিক থেকে শিক্ষাটি গুরুত্বপূর্ণ। যত বেশি আচরণ দৃশ্যমান, তত কম optimization সম্ভব; যত কম নিশ্চয়তা, তত বেশি স্বাধীনতা কিন্তু তত বেশি বিস্ময় (C-র undefined behavior). Haat নিরাপদ দিক বেছেছে, Java-র মতো: সব নির্দিষ্ট, optimization সীমিত, কিন্তু program সব যন্ত্রে এক আচরণ করে।
মূল উপলব্ধি: Optimization-এর বৈধতা ঠিক করে ভাষার semantics, compiler নয়; একই রূপান্তর এক ভাষায় বৈধ আর আরেক ভাষায় ভুল।
অনুশীলন
প্রথমে নিজে হিসাব করুন বা লিখুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর সত্যিকারের run দিয়ে যাচাই করা।
-
নকশা ও বাস্তবায়ন — একটি peephole pass: এই back end প্রায়ই পরপর দুটি লাইন লেখে:
sd t0, -40(s0)আর ঠিক পরেld t0, -40(s0). দ্বিতীয় লাইনটি মুছে ফেলার একটি ছোট pass লিখুন, যাcompile_rv-এর আউটপুট text নেয়। কখন মোছা নিরাপদ, আর কখন নয়? তারপর ভাবুন,bazar.haat-এ কতগুলো লাইন যাবে।def peep(asm): # sd r, X(s0) ঠিক পরে ld r, X(s0) -> ld বাদ out = [] for l in asm.split("\n"): p = out[-1].split() if out else [] q = l.split() if p and q and p[0] == "sd" and q[0] == "ld" and p[1:] == q[1:]: continue out.append(l) return "\n".join(out)নিরাপদ কারণ:
sd-এর পরে register আর memory-তে একই মান, আর দুটি লাইন একেবারে পাশাপাশি। মাঝে একটি label থাকলে (.L…:) মোছা যেত না, কারণ অন্য কোনো শাখা সরাসরি সেই label-এ এসেld-এর ওপর নির্ভর করতে পারে; এই pass label-কেও একটি লাইন ধরে, তাই সেখানে মেলে না। Register বা offset আলাদা হলেও মোছে না। সত্যিকারের ফল:bazar.haat-এ শুধু একটি লাইন যায় (price-এর B0-তেp-এর ফেরত পড়া), তাই চলা লাইন ১৭১ থেকে ১৬৯ (priceদুবার ডাকা হয়)। ২০০টি এলোমেলো program-এ চলা লাইন ৯৯,৬২১ থেকে ৯৮,৩৯৬ (প্রায় ১.২%), আর ২০০টিরই আউটপুট reference-এর সঙ্গে এক। লাভ ছোট, কারণ আসল খরচ এক statement থেকে আরেক statement-এ মান slot দিয়ে পাঠানোয়, যা সরাতে register allocation লাগে। -
ভুল খুঁজুন — উল্টো শাখা: একজন হাতে
fact-এর code generator লিখেছেন।if n <= 1 { return 1; }-এর জন্য তাঁর কোডld t0, -24(s0)(n),li t1, 1, তারপরblt t0, t1, .Lhaat_fact_B2(B2 = recursion-এর block, B1 =return 1, ঠিক পরে)।print(fact(3)); print(fact(0));কী ছাপবে? ঠিক নির্দেশটি কী?শর্ত সত্য হলে (
n <= 1) যেতে হবে B1-এ, যা নিচে; তাই লাফ হবে উল্টো শর্তে,n > 1অর্থাৎ1 < nহলে:blt t1, t0, .Lhaat_fact_B2, যা এই পর্বের আসল আউটপুট। ভুল কোড লাফ দেয়n < 1হলে।fact(3)-এ 3 < 1 মিথ্যা, তাই সরাসরি B1: ফল1(৬ নয়)।fact(0)-এ 0 < 1 সত্য, recursion-এ যায়fact(-1),fact(-2)… কখনো থামে না, যতক্ষণ না সীমা ধরে। ভুল assemblyrv_run.py-এ চালানো সত্যিকারের আউটপুট:1 3:14: runtime error: stack overflowশিক্ষা দুটি। প্রথমত, একটি উদাহরণ (
fact(3)) ভুলটি দেখায়, কিন্তু এমন ভুলও হয় যা শুধু সীমানায় ধরা পড়ে, তাইn= 0, 1, 2 তিনটিই পরীক্ষা করা দরকার। দ্বিতীয়ত, ১,০০০-এর সীমা এখানে নিরাপত্তার জাল: সীমা না থাকলে program stack-এর সীমা পেরিয়ে অন্য memory নষ্ট করত বা segmentation fault হতো। -
হিসাব — একটি ছোট function-এর পুরো কোড:
fn half(x: Int) -> Int { return x / 2; }. এর frame কত byte, কোন নামের slot কোথায়? ভাগের জন্য পর্ব ৬৯-এর selector কোন tile বাছবে:li+div, নাকি shift-এর চার নির্দেশ?beqzথাকবে কি?half(-7)কত?IR নাম তিনটি:
x,t1(const 2),t2(ভাগফল), তাই ১৬ + ৩ × ৮ = ৪০, ১৬-এর গুণিতকে ৪৮ byte;x→ −24,t1→ −32,t2→ −40 (শেষ দুটি ভাঁজ হয়ে গাছে ঢোকে, slot অব্যবহৃত থাকে)। Maximal munch আগে বড় pattern দেখে;divkআরdivp2দুটিরই pattern “ভাগ, ডানে ধ্রুবক”, আকার সমান, তাই কম নির্দেশেরটি জেতে:li+div(২টি) বনাম shift-এর ৪টি। ভাজক শূন্য-নয় ধ্রুবক, তাইbeqzনেই। সত্যিকারের আউটপুট:haat_half: addi sp, sp, -48 sd ra, 40(sp) sd s0, 32(sp) addi s0, sp, 48 sd a0, -24(s0) # x .Lhaat_half_B0: ld t0, -24(s0) li t1, 2 div a0, t0, t1 ld ra, 40(sp) ld s0, 32(sp) addi sp, sp, 48 rethalf(-7)=-3(শূন্যের দিকে কাটা, C-র মতো) আরhalf(7)=3; দুটিই ব্রাউজারের interpreter-এ চালানো। লক্ষ করুন, শুধু নির্দেশের সংখ্যা দিয়ে মাপলেdivজেতে, কিন্তু আসল CPU-তেdivঅনেক ধীর; পর্ব ৬৯-এরLATENCYমডেলে DP tiler উল্টো সিদ্ধান্ত নিত। -
আউটপুট অনুমান — কোন পরীক্ষা আগে? নিচের program কী ছাপবে, কোন runtime function ডাকা হবে, আর error-এর অবস্থান কী?
print(total());var rate = 5;fn total() -> Int { return 100 / rate; }
আর প্রথম দুটি লাইনের ক্রম উল্টেvar rate = 0;লিখলে?প্রথম program-এ
totalডাকা হয়var rateচলার আগে।100 / rate-এর গাছে প্রথমে বাঁ দিক (ধ্রুবক), তারপরrateপড়া:haat_g_rate-এর flag 0, তাইhaat_not_init, ভাগ পর্যন্ত পৌঁছায়ই না। অবস্থানrateনামের: লাইন ৩, কলাম ৩৪।rv_run.pyআর পর্ব ৬২-এর IR interpreter, দুটিরই সত্যিকারের আউটপুট:3:34: runtime error: 'rate' is not initialized yetদ্বিতীয় রূপে (
var rate = 0;আগে, তারপরfn total, তারপরprint(total());) flag 1, মান 0, তাই ভাগের আগেরbeqzধরে শূন্য, আরhaat_div_zero; অবস্থান/-এর:2:32: runtime error: division by zero. দুই ক্ষেত্রেই কিছু ছাপা হয় না, কারণprint-এর argument-এর হিসাবেই program থামে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমHaat source থেকে চলমান RISC-V program পর্যন্ত ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Parse আর lowering: Haat IR-এর রৈখিক কোড
build_cfg: basic block আর CFGblock_trees: প্রতিটি block-এর statement আর expression tree- Tile বাছাই, frame, call আর runtime-পরীক্ষাসহ
.sফাইল লেখা - Assembler আর linker: runtime-এর object file-সহ ELF
- Emulator বা RISC-V যন্ত্রে চালিয়ে reference-এর সঙ্গে মেলানো
RV64IM-এ div t0, t1, t2 চলার সময় t2 = 0 হলে কী ঘটে?
- CPU একটি exception তোলে, program থামে
t0= −1, কোনো trap নেইt0= 0, কোনো trap নেই- ফল undefined, যেকোনো কিছু হতে পারে
একটি back end branch t9 B2 B3 নামাচ্ছে, যেখানে t9 = total < t8 আর B2 ঠিক পরের block. সবচেয়ে ছোট সঠিক কোড কোনটি (t0 = total, t1 = t8)?
blt t0, t1, B2blt t0, t1, B2তারপরj B3bge t0, t1, B3bge t1, t0, B3
Stack slot-ভিত্তিক একটি back end-এ (প্রতিটি IR নাম নিজের slot-এ, statement-এর পরে কোনো register-এ মান থাকে না) একটি function call-এর পরে caller কেন কোনো scratch register বাঁচানোর কোড লেখে না?
- কারণ call পেরিয়ে কোনো মান register-এ রাখা হয় না, সব slot-এ
- কারণ callee সব t register নিজেই বাঁচিয়ে রাখে
- কারণ
callনির্দেশ নিজেই register stack-এ রাখে - কারণ RISC-V-এ প্রতিটি function নিজের আলাদা register পায়
Haat-এর একটি top-level var k = 1;, যা একটি function পড়ে, যন্ত্রে ১৬ byte-এর একটি symbol haat_g_k. দ্বিতীয় ৮ byte কেন লাগে?
- Int ৬৪ বিটের বেশি জায়গা নেয় বলে
- RISC-V-এ global-কে ১৬ byte-এ সাজাতে হয় বলে
- Global-এর নাম রাখার জন্য
- “এখনো initialized হয়নি” চিনতে একটি flag রাখতে
একই Haat program ব্রাউজারের assembly-text interpreter-এ ১৭১টি লাইন চলে, কিন্তু Clang-এর বানানো ELF Unicorn-এ চালালে Haat-এর অংশে ১৮৮টি নির্দেশ গোনা হয়। সবচেয়ে সম্ভাব্য কারণ কী?
- Clang assembly-টি আরও optimize করেছে
call,laআর বড় ধ্রুবকেরliযন্ত্রে দুটি করে নির্দেশ- Unicorn কিছু নির্দেশ দুবার চালায়
- Runtime-এর নির্দেশও ১৮৮-এর মধ্যে ধরা
Haat-এ ১,০০০-এর বেশি nested call হলে stack overflow error দিতে হয়। একটি optimizer return n * f(n - 1);-এর মতো recursion-কে loop-এ বদলাতে চায় (C-র জন্য Clang -O2 যা করে)। Haat-এর জন্য এটি কেমন?
- সবসময় বৈধ, কারণ program দ্রুত হয়
- অবৈধ, কারণ গুণের ক্রম বদলালে ফল বদলায়
- অবৈধ, যদি না প্রমাণ করা যায় যে গভীরতা কখনো ১,০০০ ছোঁবে না
- বৈধ, কারণ এটি tail call
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Back end = জোড়া: IR (৬২) → গাছ আর tile (৬৯) → frame আর call (৭১) → এই পর্বের call, print, global আর runtime-পরীক্ষা → Clang-এর assembler আর linker.
- সরলতার চুক্তি: প্রতিটি IR নাম নিজের slot-এ, statement-এর পরে কোনো register দরকারি মান রাখে না; তাই call-এর আশেপাশে register নিয়ে ভাবতে হয় না, দাম অনেক
ld/sd. - Control flow: প্রতিটি block একটি local label; শাখা এক compare-and-branch নির্দেশ, পরের block-এ যেতে হলে শর্ত উল্টে নিচে গড়িয়ে পড়া; loop-এর ফেরা একটি
j. - ভাষার নিয়ম কোডে: অজানা ভাজকের আগে
beqz, call-এর আগে ১,০০০-এর সীমা, global-এর পাশে initialized flag; বার্তা লেখে C-তে লেখা ছোট runtime, libc ছাড়া। - বিশ্বাস চালিয়ে: ৩,০০৩টি program Clang আর Unicorn-এ reference-এর সঙ্গে হুবহু এক, প্রতিটি call-এ ABI পরীক্ষা; সঠিক আউটপুট একটি উদাহরণে প্রমাণ নয়, অনেক এলোমেলো program-এ সাক্ষ্য।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৭৩ · WebAssembly targetপরবর্তী পর্বএকই IR থেকে stack machine-এর কোড।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ৭০ · Register allocationএই কোর্সেএই back end-এর slot-গুলো register-এ তোলার পথ।
- Computer Architecture পর্ব ২৬ · RISC-V-এর নির্দেশপাশের ট্র্যাকএই পর্বের প্রতিটি নির্দেশের hardware-এর অর্থ।
- Computer Architecture পর্ব ৩০ · Procedure আর stackপাশের ট্র্যাকjal, jalr আর stack frame, hardware-এর চোখে।
- Computer Architecture পর্ব ৩১ · C থেকে assemblyপাশের ট্র্যাকসত্যিকারের compiler-এর আউটপুট পড়ার অভ্যাস।