সরাসরি পর্বে যান
পর্ব ৭২ · ৮৬-এর মধ্যে · মডিউল ১২

Haat থেকে RISC-V assembly — একটি সম্পূর্ণ back end

From Haat to RISC-V Assembly — A Complete Compiler Back End

Taught in Bangla, this lesson joins Haat IR, instruction selection and the calling convention into a complete back end that emits RV64IM assembly for any Haat program over Int and Bool, keeping every IR name in its own stack slot. It shows a template per IR instruction, labels and branches for if and while, calls and recursion with the 1000-call limit, globals with initialisation checks and a small C runtime using two Linux system calls, then assembles with real Clang and runs in Unicorn and the browser.

এই পর্বে যা শিখবেন

  • একটি 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 থেকে RISC-V: back end-এর পুরো পথ bazar.haat (source) parse · lower · build_cfg Haat IR, CFG block_trees · Selector গাছ থেকে নির্দেশ frame_layout · prologue epilogue · call_seq Gen: call, print, global runtime error → bazar.s Clang: assemble + link + haat_rt.o (C runtime) ELF executable Unicorn / RISC-V Linux 996 · 5000 · 3 পর্ব ৬২পর্ব ৬৯পর্ব ৭১ এই পর্বসত্যিকারেরtool ব্রাউজারে: rv_run.py
ছবি ৭২.১ — নীল অংশগুলো আগের পর্বের ফাইল, হুবহু কপি: 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, printStr আর 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-এর জন্য।

StatementRISC-V ছাঁচকার কোড
x = গাছ৬৯-এর tile, ফল sd দিয়ে x-এর slot-এ৬৯ (Selector.value)
branch c B1 B2তুলনা আর লাফ এক নির্দেশে (blt, bge …); পরের block-এ নিচে গড়িয়ে পড়া৬৯ (Selector.branch)
jump B1j .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 = tla দিয়ে ঠিকানা, flag পরীক্ষা, ld/sdএই পর্ব
a / b, a % bbeqz 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
নিয়ম ৭২.১ — Haat back end v1-এর চুক্তি

(১) প্রতিটি 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
Register আর slot
sp
s0
t0 · t1 · t2
a0 · a1
slot
  1. জায়গা নেওয়া। call haat_price-এর পরে প্রথম নির্দেশ: sp ৮০ কমে 0x7FEFFF10. a0 = 2, a1 = 520: main argument দুটি register-এ রেখে ডেকেছে।
  2. Frame record আর frame pointer. ra আর main-এর s0 stack-এ গেল; নতুন s0 = sp + 80 = 0x7FEFFF60, ঢোকার মুহূর্তের sp. এখন থেকে প্রতিটি slot s0-সাপেক্ষ।
  3. Parameter slot-এ। qty = 2 গেল -24(s0)-এ, unit = 520 গেল -32(s0)-এ। এই back end-এ register-argument সঙ্গে সঙ্গেই slot-এ নামে।
  4. প্রথম গাছ: qty * unit. দুটি ld, একটি mul: t0 = 1040, ফল গেল p-এর slot -40(s0)-এ। t1-এ 520 পড়ে থাকে, কিন্তু চুক্তি অনুযায়ী statement-এর পরে কেউ সেটি পড়বে না।
  5. শাখা। p আবার ld হলো (আগের লাইনেই sd হয়েছিল; অনুশীলন ১ এটিই সরায়), t1 = 1000. 1040 < 1000 মিথ্যা, তাই blt লাফ দেয় না: কোড নিচে গড়িয়ে B1-এ ঢোকে।
  6. দ্বিতীয় গাছ: p / 10. p দুবার ld হলো, গাছের দুই পাতার জন্য দুটি register. div-এর ফল t1 = 104; ভাজক ধ্রুবক বলে শূন্যের পরীক্ষা নেই।
  7. ফল। sub a0, t0, t1: 1040 − 104 = 936, সরাসরি ফেরত-register a0-তে। গাছের মূল return-এর, তাই selector গন্তব্য হিসেবে a0 পেয়েছে, কোনো slot নয়।
  8. 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
Slot আর register
total
rounds
t0 · t1
পরীক্ষা
  1. Loop-এর আগে। var total = 0; আর var rounds = 0;: ধ্রুবক শূন্যের জন্য register লাগে না, RISC-V-এর zero register সরাসরি slot-এ লেখা হলো। তারপর B0 শেষ, আর B1 ঠিক পরের block, তাই কোনো j নেই।
  2. প্রথম পরীক্ষা। t0 = total = 0, t1 = 5000. 0 ≥ 5000? না, তাই bge লাফ দেয় না, কোড নিচে B2-তে গড়িয়ে পড়ে।
  3. প্রথম চক্র। total = 1250, rounds = 1; শেষ লাইনে t0-তে 1 পড়ে থাকে। j .Lhaat_main_B1: পেছনের দিকে লাফ, back edge.
  4. দ্বিতীয় আর তৃতীয় চক্র। পরীক্ষায় 1250 আর 2500, দুবারই 5000-এর কম; body আরও দুবার চলে। এখন total = 3750, rounds = 3.
  5. চতুর্থ চক্র। চতুর্থ পরীক্ষায় 3750 < 5000, body আবার: total = 5000, rounds = 4.
  6. পঞ্চম পরীক্ষা। 5000 ≥ 5000, এবার bge লাফ দেয় B3-এ। মোট: B1 চলেছে ৫ বার (৫ × ৩ = ১৫টি নির্দেশ), B2 চলেছে ৪ বার (৪ × ৭ = ২৮টি)।
  7. 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
Register আর stack
sp
s0
a0
depth
frame
  1. main ডাকে। haat_depth 0 থেকে 1 (সীমা ১,০০০-এর অনেক নিচে), a0 = 3. ঢোকার মুহূর্তে sp = 0x7FEFFFC0, ১৬-এর গুণিতক; ra = 0x100186C, main-এর ফেরার ঠিকানা।
  2. 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-এর নিজের ভেতরের ঠিকানা।
  3. fact(2). আরেকটি ৮০ byte-এর frame: sp = 0x7FEFFF20, s0 = 0x7FEFFF70, অর্থাৎ ঠিক আগের frame-এর sp. একই কোড, ভিন্ন frame: recursion-এর পুরো রহস্য এটুকুই। Depth 3, ডাক fact(1).
  4. fact(1) আর প্রথম ফেরা। Frame 0x7FEFFED0 থেকে 0x7FEFFF20. 1 < 1 মিথ্যা, তাই blt লাফ দেয় না, B1: a0 = 1. Epilogue ra, s0 আর sp ফিরিয়ে দেয় fact(2)-এর মানে।
  5. fact(2)-এ ফিরে। ফল 1 গেল -72(s0)-এ, depth 3 থেকে 2. n আর ফল slot থেকে উঠে mul: a0 = 2 × 1 = 2. n হারায়নি, কারণ সেটি register-এ নয়, নিজের frame-এর slot-এ ছিল।
  6. fact(3)-এ ফিরে। Depth 1, a0 = 3 × 2 = 6; epilogue-এর পরে sp আবার 0x7FEFFFC0, ঢোকার মুহূর্তের মান। তিনটি frame-ই ছেড়ে দেওয়া হয়েছে।
  7. 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) তিন স্তরে:

  1. Differential test: পর্ব ৬২-এর haat_gen দিয়ে seed 0 থেকে 2999-এর ৩,০০০টি এলোমেলো program, আর reference-এর ১৩টি উদাহরণ। প্রতিটি haat_rv.py দিয়ে .s, Clang 22.1.8 দিয়ে ELF, PyPI-র unicorn 2.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-গুলোর একটিও বাদ যায়নি।
  2. হাতে লেখা প্রান্তের program: ৯টি, প্রতিটি একটি নিয়ম ধরতে: global পড়া আর assignment-এর আগে initialized না হওয়া, ১,০০০-এর সীমা ঠিক সীমানায় (d(999) চলে, d(1000)-এ stack overflow), অসীম recursion, সবচেয়ে ছোট Int-এর / -1 আর % -1, Bool parameter আর ফল, দশ argument-এর call, variable ভাজকে শূন্য। ৯টিই reference-এর সঙ্গে এক।
  3. প্রতিটি 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-কে কাজে লাগাতে আগে চুক্তি আর যাচাইয়ের পথ বলে দিন:

আমি একটি ছোট শিক্ষামূলক ভাষার (Haat) RV64IM back end লিখছি, Linux-এর RISC-V psABI মেনে। প্রতিটি IR নাম stack slot-এ থাকে (s0-সাপেক্ষ), t0–t6 শুধু একটি statement-এর ভেতরে। ১. নিচের IR-এর জন্য assembly দাও, প্রতিটি block-এর label-সহ। শাখার শর্ত উল্টালে কেন উল্টালে, তা লাইনের পাশে মন্তব্যে বলো। ২. ভাগের আগে ভাজক শূন্য কি না পরীক্ষা করবে; RISC-V-এর div শূন্যে কী দেয়, তা spec-এর কোন অংশে আছে বলো। নিশ্চিত না হলে অনুমান কোরো না। ৩. আমার কোড যাচাইয়ের জন্য পাঁচটি সীমানার ইনপুট প্রস্তাব করো (শূন্য, ঋণাত্মক, সবচেয়ে ছোট Int, সীমার ঠিক আগে-পরে), আর প্রতিটির প্রত্যাশিত আউটপুট reference interpreter দিয়ে মেলাতে বলো। ৪. কোনো optimization প্রস্তাব করলে বলো, সেটি ভাষার দৃশ্যমান আচরণ (error, তার অবস্থান, call-এর সীমা) বদলায় কি না।

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 দিয়ে যাচাই করা।

  1. নকশা ও বাস্তবায়ন — একটি 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 লাগে।

  2. ভুল খুঁজুন — উল্টো শাখা: একজন হাতে 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) … কখনো থামে না, যতক্ষণ না সীমা ধরে। ভুল assembly rv_run.py-এ চালানো সত্যিকারের আউটপুট:

    1
    3:14: runtime error: stack overflow

    শিক্ষা দুটি। প্রথমত, একটি উদাহরণ (fact(3)) ভুলটি দেখায়, কিন্তু এমন ভুলও হয় যা শুধু সীমানায় ধরা পড়ে, তাই n = 0, 1, 2 তিনটিই পরীক্ষা করা দরকার। দ্বিতীয়ত, ১,০০০-এর সীমা এখানে নিরাপত্তার জাল: সীমা না থাকলে program stack-এর সীমা পেরিয়ে অন্য memory নষ্ট করত বা segmentation fault হতো।

  3. হিসাব — একটি ছোট 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
      ret

    half(-7) = -3 (শূন্যের দিকে কাটা, C-র মতো) আর half(7) = 3; দুটিই ব্রাউজারের interpreter-এ চালানো। লক্ষ করুন, শুধু নির্দেশের সংখ্যা দিয়ে মাপলে div জেতে, কিন্তু আসল CPU-তে div অনেক ধীর; পর্ব ৬৯-এর LATENCY মডেলে DP tiler উল্টো সিদ্ধান্ত নিত।

  4. আউটপুট অনুমান — কোন পরীক্ষা আগে? নিচের 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 পর্যন্ত ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Parse আর lowering: Haat IR-এর রৈখিক কোড
  2. build_cfg: basic block আর CFG
  3. block_trees: প্রতিটি block-এর statement আর expression tree
  4. Tile বাছাই, frame, call আর runtime-পরীক্ষাসহ .s ফাইল লেখা
  5. Assembler আর linker: runtime-এর object file-সহ ELF
  6. 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, B2
  • blt t0, t1, B2 তারপর j B3
  • bge t0, t1, B3
  • bge 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

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Back end = জোড়া: IR (৬২) → গাছ আর tile (৬৯) → frame আর call (৭১) → এই পর্বের call, print, global আর runtime-পরীক্ষা → Clang-এর assembler আর linker.
  2. সরলতার চুক্তি: প্রতিটি IR নাম নিজের slot-এ, statement-এর পরে কোনো register দরকারি মান রাখে না; তাই call-এর আশেপাশে register নিয়ে ভাবতে হয় না, দাম অনেক ld/sd.
  3. Control flow: প্রতিটি block একটি local label; শাখা এক compare-and-branch নির্দেশ, পরের block-এ যেতে হলে শর্ত উল্টে নিচে গড়িয়ে পড়া; loop-এর ফেরা একটি j.
  4. ভাষার নিয়ম কোডে: অজানা ভাজকের আগে beqz, call-এর আগে ১,০০০-এর সীমা, global-এর পাশে initialized flag; বার্তা লেখে C-তে লেখা ছোট runtime, libc ছাড়া।
  5. বিশ্বাস চালিয়ে: ৩,০০৩টি program Clang আর Unicorn-এ reference-এর সঙ্গে হুবহু এক, প্রতিটি call-এ ABI পরীক্ষা; সঠিক আউটপুট একটি উদাহরণে প্রমাণ নয়, অনেক এলোমেলো program-এ সাক্ষ্য।

পরের পর্বে: পর্ব ৭৩ (WebAssembly target — Haat থেকে browser-এ চলা code). একই Haat IR, কিন্তু target-এ register নেই, আছে একটি stack machine আর কাঠামোবদ্ধ block/loop; Haat program সরাসরি ব্রাউজারের WebAssembly engine-এ চলবে।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান