এই পর্বে যা শিখবেন
- IR কেন লাগে, আর AST, stack code, three-address code, CFG ও SSA-র মতো IR-এর রূপ কোথায় আলাদা
- Quadruple, triple আর indirect triple দিয়ে একই expression লেখা, আর কোনটি সরানো সহজ
- Haat-এর একটি ছোট three-address IR, আর Haat program থেকে সেখানে নামার (lowering) পুরো নিয়ম ও কোড
- Leader-এর তিন নিয়মে basic block, control flow graph, successor আর predecessor
- IR interpreter আর differential test দিয়ে প্রমাণ করা যে IR-এর অর্থ program-এর অর্থের সমান; সঙ্গে সত্যিকারের Clang-এর LLVM IR
১ · কেন IR — m × n সমস্যা আর মাঝের ভাষা
ঢাকার একটি বড় সম্মেলনের কথা ভাবুন। অতিথিরা বাংলা, হিন্দি আর জাপানি বলেন; শ্রোতারা শোনেন বাংলা, ইংরেজি আর আরবিতে। প্রতিটি জোড়ার জন্য আলাদা দোভাষী রাখলে লাগবে ৩ × ৩ = ৯ জন। বাস্তবে আয়োজকেরা অন্য পথ নেন: প্রত্যেক বক্তার কথা আগে ইংরেজিতে, তারপর ইংরেজি থেকে প্রতিটি শ্রোতার ভাষায়। দোভাষী লাগে ৩ + ৩ = ৬ জন, আর নতুন একটি ভাষা যোগ করতে লাগে মাত্র একজন। মাঝের ইংরেজিটিই compiler-এর intermediate representation (IR).
Compiler-এর তিন অংশের কথা পর্ব ০৫-এ দেখেছেন। Front end source ভাষা বোঝে (lexer, parser, type checker: মডিউল ৮ আর ৯); back end লক্ষ্য-যন্ত্র বোঝে (মডিউল ১২)। মাঝখানের middle end কোনোটিকেই সরাসরি দেখে না; সে শুধু IR পড়ে আর IR লেখে। এই ভাগের তিনটি লাভ:
- m + n: একটি নতুন ভাষার জন্য শুধু একটি front end, একটি নতুন CPU-র জন্য শুধু একটি back end. এমন compiler-কে বলে retargetable compiler; Clang আর Rust-এর compiler একই LLVM back end ভাগ করে।
- Optimization একবার: constant folding বা loop optimization (পর্ব ৬৫–৬৬) IR-এ লিখলে সব ভাষা আর সব যন্ত্র সেটি পায়।
- সহজ অর্থ: AST-এ
&&, nested if, block scope আর shadowing মিলে অনেক নিয়ম; IR-এ শুধু ছোট নির্দেশ আর লাফ। ছোট ভাষার ওপর বিশ্লেষণ লেখা আর তার সঠিকতা যাচাই করা সহজ।
ছবি ৬২.১ — IR ছাড়া m × n, IR দিয়ে m + n
৩টি ভাষা আর ৩টি লক্ষ্য: ৯টি অনুবাদক বনাম ৬টি অংশ
ধারণাটি নতুন নয়। ১৯৫৮ সালের দিকে UNCOL (Universal Computer Oriented Language) নামে একটি সর্বজনীন মধ্যবর্তী ভাষার প্রস্তাব আসে, ঠিক এই m × n সমস্যা মেটাতে; সেই সর্বজনীন রূপটি কখনো পুরো তৈরি হয়নি (ভাবনার প্রশ্ন ১)। আজ ধারণাটি বেঁচে আছে LLVM IR, GCC-র GIMPLE, JVM bytecode আর WebAssembly-তে। Haat-এও একটি “মাঝের ভাষা” আছে: পর্ব ৫৮-এর stack bytecode. তাহলে আরেকটি কেন? কারণ bytecode বানানো হয়েছে চালানোর জন্য, আর এই মডিউলের IR বানানো হবে বিশ্লেষণ আর বদলের জন্য। পার্থক্যটি অংশ ৯-এ সংখ্যা দিয়ে দেখবেন।
২ · IR-এর রকমফের — গাছ, সারি আর graph
IR একটি নয়, একটি পরিবার। তিনটি প্রশ্নে এদের আলাদা করা যায়: গঠন কেমন (গাছ, সারি না graph), স্তর কতটা উঁচু (source-এর কাছে না যন্ত্রের কাছে), আর মাঝের ফল কোথায় থাকে (stack-এ না নামওয়ালা ঘরে)।
| রূপ | গঠন | কোথায় দেখবেন |
|---|---|---|
| AST, expression DAG | গাছ; DAG-এ একই subexpression একবার | Haat-এর AST (পর্ব ৪৯); Clang-এর AST |
| Stack code | সারি; মাঝের ফল operand stack-এ | Haat bytecode (পর্ব ৫৮), JVM, CPython, WebAssembly |
| Three-address code | সারি; মাঝের ফল নামওয়ালা temp-এ | পাঠ্যবইয়ের IR, Haat IR (এই পর্ব), GCC-র GIMPLE |
| CFG + three-address code | graph-এর প্রতিটি node একটি সারি | প্রায় সব optimizing compiler |
| SSA form | CFG, প্রতিটি নামে একবারই মান বসে, মিলনে φ | LLVM IR, GCC (GIMPLE-এর SSA রূপ); পর্ব ৬৩ |
| Graph IR (sea of nodes) | নির্দেশের ক্রমও শুধু নির্ভরতার edge | Java HotSpot-এর server compiler (C2) |
স্তরের দিক থেকে বড় compiler সাধারণত কয়েকটি IR পরপর ব্যবহার করে: ওপরের স্তরে ভাষার গঠন (loop, array-এর সূচক) টিকে থাকে, নিচের স্তরে register আর memory-র ঠিকানা আসে। GCC-তে GENERIC → GIMPLE → RTL, Rust-এ HIR → MIR → LLVM IR. ২০১৯ সালে প্রকাশ্যে আসা MLIR এই ধারণাকে একটি কাঠামো বানিয়েছে: একই কাঠামোয় অনেক স্তরের “dialect”.
Three-address code রাখার তিন উপায়
Three-address code-এর প্রতিটি নির্দেশে একটি operator আর বড়জোর তিনটি ঠিকানা: দুটি operand, একটি ফল। নির্দেশগুলো memory-তে রাখার পাঠ্যবইয়ের তিনটি পদ্ধতি আছে। Quadruple-এ চারটি ঘর: op, arg1, arg2, result; ফলের একটি নাম থাকে। Triple-এ result-এর ঘর নেই: একটি নির্দেশের ফল মানে তার সারির নম্বর, যেমন (0). Indirect triple-এ triple-গুলোর পাশে একটি আলাদা তালিকা রাখা হয়, যা বলে কোন ক্রমে চালাতে হবে। পর্ব ৫৩-এ attribute দিয়ে qty * unit - p / 10-এর three-address code তৈরি হতে দেখেছেন; এবার একই কাজের তিন সংরক্ষণ-রূপ, আর optimizer যখন নির্দেশ সরাতে চায় তখন কী হয়।
1pay = qty * unit - p / 102① qty * unit3② p / 104③ ① - ②5④ pay = ③6Haat IR: নামওয়ালা quadruple
| রূপ | |
| ঘর |
- গাছ থেকে কাজের তালিকা। Post-order-এ চারটি কাজ: গুণ, ভাগ, বিয়োগ, তারপর pay-তে রাখা। প্রতিটি কাজের operand তার আগেই তৈরি।
- Quadruple. প্রতিটি সারিতে চারটি ঘর। ফলের নিজের নাম (t1, t2, t3), তাই পরের সারি নাম দিয়ে আগের ফল ধরে:
- t1 t2. Symbol table-এ temp-গুলোর জন্য জায়গা লাগে। - Triple. Result-এর ঘর নেই; ফলের পরিচয় সারির নম্বর। বিয়োগ লেখে
(0)আর(1), অর্থাৎ “সারি ০ আর সারি ১-এর ফল”। জায়গা কম, temp-এর নাম নেই। - Triple-এ ক্রম বদল। ধরুন optimizer ভাগটিকে গুণের আগে নিতে চায় (যেমন loop optimization-এ, পর্ব ৬৬)। সারির নম্বর বদলে যায়, তাই যে সারি
(0)বা(1)উল্লেখ করে, সবগুলো খুঁজে ঠিক করতে হয়। বড় function-এ এটি ব্যয়বহুল আর ভুলপ্রবণ। - Indirect triple. Triple-গুলো নিজের জায়গায় স্থির (10–13), আর আলাদা একটি তালিকা বলে চালানোর ক্রম। ক্রম বদলাতে শুধু তালিকা বদলান: 11, 10, 12, 13. কোনো উল্লেখ ভাঙে না।
- Haat IR. Haat IR quadruple-ধাঁচের: প্রতিটি
Ins-এ kind, dst, args আর sym. নাম স্থির, তাই নির্দেশ সরানো সহজ। একটি পার্থক্য: Haat IR-এ operand শুধু নাম, তাই 10 আসে আলাদাt2 = const 10দিয়ে।
৩ · Haat IR — নির্দেশ, নাম আর লেখার নিয়ম
এই মডিউলের ছয়টি পর্ব একটি IR-এর ওপর কাজ করবে, নাম Haat IR. এর পুরো instruction set নিচের টেবিলে; φ (phi) আসবে পর্ব ৬৩-এ।
| লেখার রূপ | kind | অর্থ |
|---|---|---|
t = const k | const | ধ্রুবক: Int, true/false, "…", বা Unit () |
x = a | copy | মান কপি |
t = a op b | bin | + - * / % == != < <= > >=; Int ৬৪ বিটে wrap, / % C-ধাঁচের |
t = op a | un | - (wrap) বা ! |
t = call f(a, …) | call | top-level function f ডাকা |
print a | Haat-এর print | |
return a | return | function শেষ |
jump L | jump | শর্তহীন লাফ |
branch c L1 L2 | branch | c সত্য হলে L1, মিথ্যা হলে L2 |
label L | label | লাফের লক্ষ্য (শুধু রৈখিক রূপে) |
নামের নিয়মগুলো ছোট কিন্তু কড়া, কারণ পরের পর্বের প্রতিটি বিশ্লেষণ এগুলোর ওপর দাঁড়াবে:
- Operand শুধু নাম। Haat variable (
p), temporary (t1,t2…, প্রতিটি function-এ ১ থেকে), বা global (@fee). ধ্রুবক কখনো সরাসরি operand নয়; এতে প্রতিটি মানের একটি সংজ্ঞা-নির্দেশ থাকে, যা পর্ব ৬৪-এর dataflow analysis-কে সরল রাখে। - একটি binding, একটি নাম। Block-এর ভেতরে shadowing হলে নতুন binding পায়
total.1,total.2. Haat-এর নিজের নামt1হলে সেটিওt1.1হয়, যাতে temp-এর সঙ্গে না মেলে। - Global শুধু দরকার হলে। কোনো function যে top-level variable পড়ে বা লেখে, সেটি memory-তে থাকে আর লেখা হয়
@x; পড়াt = @x, লেখা@x = t. বাকি top-level variable<main>-এর সাধারণ local. কারণ সিদ্ধান্ত ১৮: hoisted function একটি global পড়তে পারে তারletচলার আগেই, তখন runtime error'k' is not initialized yet; এই পরীক্ষা শুধু@-ওয়ালা copy-তে লাগে। - লেখার রূপ। প্রথম লাইন
fn price(qty, unit):; তারপর রৈখিক রূপে প্রতিটি নির্দেশ দুই space ভেতরে, আর CFG রূপেB0:,B1:… শিরোনামের নিচে। Entry block সবসময় B0; top-level statement-গুলো<main>নামের function.
Optimizer-এর জন্য একটি স্থায়ী নিয়ম: Haat-এ শূন্য দিয়ে ভাগ বা ভাগশেষ একটি runtime error, যা নির্দিষ্ট line:col বলে (সিদ্ধান্ত ২৬)। তাই যে ভাগের ভাজক শূন্য হতে পারে, কোনো pass সেটি ভাঁজ করবে না, মুছবে না, আর অন্য জায়গায় সরাবে না। t = x / t0 যেখানে t0 = const 0: এটি “ভুল কোড” নয়, এটি program-এর অর্থ, আর ফলটি কখনো ব্যবহার না হলেও error-টি ঘটতেই হবে। এজন্য প্রতিটি Ins-এ একটি pos থাকে, যা text-এ ছাপা হয় না।
এই পাতার Python ব্লকগুলো তিনটি সহায়ক module ব্যবহার করে। haat_front.py হলো পর্ব ৫৭-এর lexer আর parser, resolver আর interpreter বাদ দিয়ে। haat_ir.py এই পর্বের পুরো কাজ: Ins, Lower, build_cfg আর run_ir. পর্ব ৬৩–৬৮ এই ফাইলটি হুবহু ব্যবহার করবে। haat_gen.py seed থেকে এলোমেলো program বানায় (অংশ ৮)।
@dataclass(eq=False)
class Ins: # Haat IR-এর একটি নির্দেশ
kind: str # const copy bin un call print return jump branch label phi
dst: str = None # যে নামে লেখে (variable, temp বা @global); না লিখলে None
args: list = field(default_factory=list) # যে নামগুলো পড়ে
sym: object = None # operator, ধ্রুবকের মান বা callee-র নাম
targets: list = field(default_factory=list) # jump/branch/label-এর লক্ষ্য; phi-তে predecessor block
pos: tuple = None # runtime error হলে কোন (line, col) বলা হবে
def __str__(self):
k, a = self.kind, self.args
if k == "const": return f"{self.dst} = const {lit(self.sym)}"
if k == "copy": return f"{self.dst} = {a[0]}"
if k == "bin": return f"{self.dst} = {a[0]} {self.sym} {a[1]}"
if k == "un": return f"{self.dst} = {self.sym} {a[0]}"
if k == "call": return f"{self.dst} = call {self.sym}({', '.join(a)})"
if k == "phi": return f"{self.dst} = phi(" + ", ".join(f"{b}: {x}" for b, x in zip(self.targets, a)) + ")"
return " ".join([k, *a, *self.targets]) # print a · return a · jump L · branch c L1 L2 · label L
সহায়ক module haat_ir.py পুরোটা দেখুন (এই পর্বের সব কোড একসঙ্গে)
# haat_ir.py — Haat IR (পর্ব ৬২): instruction, lowering, basic block আর CFG, IR interpreter.
# পর্ব ৬৩–৬৮ এই ফাইলটি হুবহু ব্যবহার করে। Text format: প্রতি লাইনে একটি নির্দেশ, block-এর ভেতরে দুই space.
# Operand শুধু নাম: Haat variable (x, x.1), temp (t1, t2 …) বা global (@x); ধ্রুবক আসে শুধু `t = const k` দিয়ে।
import re
from dataclasses import dataclass, field, replace
from haat_front import * # parse, AST class, HaatError, runtime_error, arith, wrap, show, MAX_CALL_DEPTH
@dataclass(eq=False)
class Ins: # Haat IR-এর একটি নির্দেশ
kind: str # const copy bin un call print return jump branch label phi
dst: str = None # যে নামে লেখে (variable, temp বা @global); না লিখলে None
args: list = field(default_factory=list) # যে নামগুলো পড়ে
sym: object = None # operator, ধ্রুবকের মান বা callee-র নাম
targets: list = field(default_factory=list) # jump/branch/label-এর লক্ষ্য; phi-তে predecessor block
pos: tuple = None # runtime error হলে কোন (line, col) বলা হবে
def __str__(self):
k, a = self.kind, self.args
if k == "const": return f"{self.dst} = const {lit(self.sym)}"
if k == "copy": return f"{self.dst} = {a[0]}"
if k == "bin": return f"{self.dst} = {a[0]} {self.sym} {a[1]}"
if k == "un": return f"{self.dst} = {self.sym} {a[0]}"
if k == "call": return f"{self.dst} = call {self.sym}({', '.join(a)})"
if k == "phi": return f"{self.dst} = phi(" + ", ".join(f"{b}: {x}" for b, x in zip(self.targets, a)) + ")"
return " ".join([k, *a, *self.targets]) # print a · return a · jump L · branch c L1 L2 · label L
def lit(v): # ধ্রুবকের লেখা, reference-এর disassembler-এর মতো
if v is None: return "()"
if isinstance(v, bool): return "true" if v else "false"
if isinstance(v, str): return '"' + v.replace("\\", "\\\\").replace('"', '\\"').replace("\n", "\\n") + '"'
return str(v)
@dataclass(eq=False)
class IRFunction:
name: str
params: list
code: list = field(default_factory=list) # রৈখিক রূপ: lowering-এর ফল, label L1 L2 …-সহ
blocks: dict = field(default_factory=dict) # "B0" -> [Ins]: build_cfg-এর পরে; B0 entry
@dataclass(eq=False)
class IRModule:
funcs: dict # নাম -> IRFunction; "<main>" = top-level statement
globals: list # যে top-level variable কোনো function ব্যবহার করে (@x)
def show_ir(fn): # text format
out = [f"fn {fn.name}({', '.join(fn.params)}):"]
if not fn.blocks: return "\n".join(out + [" " + str(i) for i in fn.code])
for b, body in fn.blocks.items(): out += [f"{b}:"] + [" " + str(i) for i in body]
return "\n".join(out)
def is_temp(x): return re.fullmatch(r"t\d+", x) is not None
class Unsupported(Exception): pass # Haat IR v1-এর বাইরে: closure আর function-কে মান হিসেবে ব্যবহার
class Lower: # Haat AST -> রৈখিক Haat IR, একবারে একটি function
def __init__(self, fns): self.fns, self.used = fns, set() # top-level fn-এর নাম; function-এর দেখা global
def emit(self, kind, dst=None, args=(), sym=None, targets=(), pos=None):
if not self.dead: # return/jump-এর পরের কোডে কখনো পৌঁছানো যায় না: বাদ
self.f.code.append(Ins(kind, dst, list(args), sym, list(targets), pos))
self.dead = kind in ("jump", "branch", "return"); self.hit |= set(targets)
return dst
def temp(self): self.nt += 1; return f"t{self.nt}"
def label(self): self.nl += 1; return f"L{self.nl}"
def place(self, L): # label বসে শুধু যদি সেখানে পৌঁছানো যায়
if not self.dead or L in self.hit: self.dead = False; self.emit("label", targets=[L])
def made(self, a): # a কি এইমাত্র শেষ নির্দেশে তৈরি temp?
return not self.dead and self.f.code and self.f.code[-1].dst == a and is_temp(a)
def into(self, x, a): # x = a; a নতুন temp হলে শেষ নির্দেশটিই x-এ লেখে
if self.made(a) and x[0] != "@":
self.f.code[-1].dst = x
if x != a and a == f"t{self.nt}": self.nt -= 1 # temp-টি আর লাগে না: নম্বরটি ফেরত
else: self.emit("copy", x, [a])
def lookup(self, name):
for scope in reversed(self.scopes):
if name in scope: return scope[name]
if name in self.fns: return None # top-level function
self.used.add(name); return "@" + name # function-এর ভেতর থেকে দেখা top-level variable
def expr(self, e): # post-order; ফেরত দেয় সেই নাম, যেখানে মানটি থাকবে
if isinstance(e, (Num, Str, Bool)): return self.emit("const", self.temp(), (), e.value)
if isinstance(e, Var):
x = self.lookup(e.name)
if x is None: raise Unsupported(f"{e.line}:{e.col}: function '{e.name}' used as a value")
return self.emit("copy", self.temp(), [x], pos=(e.line, e.col)) if x[0] == "@" else x
if isinstance(e, Unary): a = self.expr(e.operand); return self.emit("un", self.temp(), [a], e.op)
if isinstance(e, Binary) and e.op in ("&&", "||"): # short-circuit: শাখা দিয়ে
a = self.expr(e.left); t = a if self.made(a) else self.temp(); self.into(t, a)
right, end = self.label(), self.label()
self.emit("branch", None, [t], targets=[right, end] if e.op == "&&" else [end, right])
self.place(right); self.into(t, self.expr(e.right)); self.place(end); return t
if isinstance(e, Binary):
a, b = self.expr(e.left), self.expr(e.right) # বাঁ আগে (সিদ্ধান্ত ১২)
return self.emit("bin", self.temp(), [a, b], e.op, pos=(e.line, e.col))
if isinstance(e, Call) and isinstance(e.callee, Var) and self.lookup(e.callee.name) is None:
args = [self.expr(a) for a in e.args]
return self.emit("call", self.temp(), args, e.callee.name, pos=(e.line, e.col))
raise Unsupported(f"{e.line}:{e.col}: closures and function values are not in Haat IR v1")
def declare(self, name): # প্রতিটি Haat binding-এর আলাদা IR নাম: x, x.1, x.2 …
ir, k = name, 0
while ir in self.taken or is_temp(ir): k += 1; ir = f"{name}.{k}"
self.taken.add(ir); self.scopes[-1][name] = ir; return ir
def function(self, name, params, stmts):
self.f, self.nt, self.nl, self.dead, self.hit = IRFunction(name, []), 0, 0, False, set()
self.scopes, self.taken = [{}], set()
self.f.params = [self.declare(p.name) for p in params]
for s in stmts: self.stmt(s)
if not self.dead: self.emit("return", None, [self.emit("const", self.temp(), (), None)]) # Unit
return self.f
def block(self, stmts):
self.scopes.append({})
for s in stmts: self.stmt(s)
self.scopes.pop()
def stmt(self, s):
if isinstance(s, Let):
a = self.expr(s.init)
if self.f.name == "<main>" and len(self.scopes) == 1 and s.name in self.used:
self.scopes[0][s.name] = "@" + s.name; self.emit("copy", "@" + s.name, [a])
else: self.into(self.declare(s.name), a)
elif isinstance(s, Assign):
a, x = self.expr(s.value), self.lookup(s.name)
if x[0] == "@": self.emit("copy", x, [a], pos=(s.line, s.col)) # সিদ্ধান্ত ১৮-এর পরীক্ষা
else: self.into(x, a)
elif isinstance(s, If):
c = self.expr(s.cond); then = self.label()
other = self.label() if s.else_ else None; end = self.label(); other = other or end
self.emit("branch", None, [c], targets=[then, other]); self.place(then); self.block(s.then.stmts)
if s.else_:
self.emit("jump", targets=[end]); self.place(other)
self.block([s.else_] if isinstance(s.else_, If) else s.else_.stmts)
self.place(end)
elif isinstance(s, While):
top, body, end = self.label(), self.label(), self.label()
self.place(top); self.emit("branch", None, [self.expr(s.cond)], targets=[body, end])
self.place(body); self.block(s.body.stmts); self.emit("jump", targets=[top]); self.place(end)
elif isinstance(s, Return):
v = self.expr(s.value) if s.value else self.emit("const", self.temp(), (), None)
self.emit("return", None, [v])
elif isinstance(s, Print): self.emit("print", None, [self.expr(s.value)])
elif isinstance(s, ExprStmt): self.expr(s.expr)
elif isinstance(s, Block): self.block(s.stmts)
else: raise Unsupported(f"{s.line}:{s.col}: nested functions are not in Haat IR v1")
def lower_program(program): # top-level fn আগে, তারপর <main>
fns = [s for s in program.stmts if isinstance(s, FnDecl)]
low = Lower({f.name for f in fns})
funcs = {f.name: low.function(f.name, f.params, f.body.stmts) for f in fns}
main = low.function("<main>", [], [s for s in program.stmts if not isinstance(s, FnDecl)])
return IRModule({"<main>": main, **funcs}, sorted(low.used))
TERMINATORS = ("jump", "branch", "return")
def build_cfg(fn): # leader খুঁজে basic block B0, B1 …; প্রতিটির শেষে terminator
code, starts, name, pending = [], [], {}, []
for ins in fn.code: # label সরিয়ে, label-কে পরের নির্দেশের সঙ্গে জোড়া
if ins.kind == "label": pending.append(ins.targets[0]); continue
if not code or pending or code[-1].kind in TERMINATORS: starts.append(len(code)) # leader-এর তিন নিয়ম
for L in pending: name[L] = f"B{len(starts) - 1}"
pending = []; code.append(ins)
fn.blocks, ends = {}, starts[1:] + [len(code)]
for n, (s, e) in enumerate(zip(starts, ends)):
body = [replace(i, args=list(i.args), targets=[name.get(t, t) for t in i.targets]) for i in code[s:e]]
if body[-1].kind not in TERMINATORS: body.append(Ins("jump", targets=[f"B{n + 1}"])) # fall-through
fn.blocks[f"B{n}"] = body
return fn
def succs(fn, b): # block b-এর পরে কোন block চলতে পারে
last = fn.blocks[b][-1]
return [] if last.kind == "return" else list(dict.fromkeys(last.targets))
def preds(fn): # প্রতিটি block-এ কোন block থেকে আসা যায়
p = {b: [] for b in fn.blocks}
for b in fn.blocks:
for s in succs(fn, b): p[s].append(b)
return p
def compile_ir(src): # Haat source -> CFG-সহ IRModule
mod = lower_program(parse(src))
for fn in mod.funcs.values(): build_cfg(fn)
return mod
def run_ir(mod, out=print): # CFG-সহ IRModule চালায়; ফেরত দেয় কয়টি নির্দেশ চলল
mem, steps = {}, 0 # mem: global variable (@ ছাড়া নাম)
def val(x, env, pos):
if x[0] != "@": return env[x]
if x[1:] not in mem: raise runtime_error(*pos, f"'{x[1:]}' is not initialized yet")
return mem[x[1:]]
def enter(fr, b): # block b-তে ঢোকা; শুরুর phi-গুলো আগের block দেখে (পর্ব ৬৩)
body = fr[0].blocks[b]; phis = [p for p in body if p.kind == "phi"]
vals = [fr[1][p.args[p.targets.index(fr[2])]] for p in phis]
for p, v in zip(phis, vals): fr[1][p.dst] = v
fr[2], fr[3] = b, len(phis)
stack = [[mod.funcs["<main>"], {}, "B0", 0, None]] # frame: fn, env, block, index, caller-এর dst
while stack:
fr = stack[-1]; fn, env, b, i, _ = fr
ins = fn.blocks[b][i]; fr[3] += 1; steps += 1
k, a = ins.kind, [val(x, env, ins.pos) for x in ins.args]
if k in ("const", "copy", "bin", "un"):
v = ins.sym if k == "const" else a[0] if k == "copy" else \
arith(ins.sym, a[0], a[1], *(ins.pos or (0, 0))) if k == "bin" else wrap(-a[0]) if ins.sym == "-" else not a[0]
if ins.dst[0] != "@": env[ins.dst] = v
elif ins.pos and ins.dst[1:] not in mem: raise runtime_error(*ins.pos, f"'{ins.dst[1:]}' is not initialized yet")
else: mem[ins.dst[1:]] = v
elif k == "print": out(show(a[0]))
elif k == "jump": enter(fr, ins.targets[0])
elif k == "branch": enter(fr, ins.targets[0] if a[0] else ins.targets[1])
elif k == "call":
if len(stack) > MAX_CALL_DEPTH: raise runtime_error(*ins.pos, "stack overflow")
f = mod.funcs[ins.sym]; stack.append([f, dict(zip(f.params, a)), "B0", 0, ins.dst])
elif k == "return":
stack.pop()
if stack: stack[-1][1][fr[4]] = a[0]
return steps
def run_lines(mod): # ছাপা লাইন; runtime error হলে সেটি শেষ লাইন
lines = []
try: run_ir(mod, lambda s: lines.extend(s.split("\n")))
except HaatError as e: lines.append(str(e))
return linesসহায়ক module haat_front.py দেখুন (lexer, parser, runtime)
# haat_front.py — সহায়ক অংশ: IR-এর আগের ধাপ, সংক্ষেপে (পর্ব ৫৭-এর haat_front.py থেকে, resolver আর interpreter বাদ)।
# Reference-এর errors.py, tokens.py + lexer.py (পর্ব ৪৬), ast_nodes.py (পর্ব ৪৯), parser.py (পর্ব ৪৭–৪৮) আর runtime.py;
# নাম আর বার্তা reference-এর মতো। lexer আর parser প্রথম error-এ থামে; type checker (পর্ব ৫২) নেই — শুধু সঠিক program.
import re
from dataclasses import dataclass, field, make_dataclass
class HaatError(Exception): # errors.py
def __init__(self, line, col, message, runtime=False):
super().__init__(message); self.line, self.col, self.message, self.runtime = line, col, message, runtime
def __str__(self):
return f"{self.line}:{self.col}: {'runtime error' if self.runtime else 'error'}: {self.message}"
class HaatErrors(Exception): # all errors of one phase, sorted by position
def __init__(self, errors):
self.errors = sorted(errors, key=lambda e: (e.line, e.col))
super().__init__("\n".join(str(e) for e in self.errors))
@dataclass(frozen=True)
class Token:
kind: str; text: str; line: int; col: int
KW = "let var fn if else while return true false print".split()
OPS = dict(zip("== != <= >= && || -> + - * / % < > ! = ( ) { } , ; :".split(),
"EQ_EQ BANG_EQ LT_EQ GT_EQ AND_AND OR_OR ARROW PLUS MINUS STAR SLASH PERCENT LT GT "
"BANG EQ LPAREN RPAREN LBRACE RBRACE COMMA SEMI COLON".split()))
SPEC = (r'(?P<skip>//[^\n]*|[ \t\r\n]+)|(?P<IDENT>[A-Za-z_][A-Za-z0-9_]*)|(?P<INT>[0-9]+)'
r'|(?P<STRING>"(?:\\["\\n]|[^"\\\n])*")|(?P<op>==|!=|<=|>=|&&|\|\||->|[-+*/%<>!=(){},;:])|(?P<bad>.)')
def tokenize(src): # lexer stand-in: the first lexical error stops it
toks = []
for m in re.finditer(SPEC, src):
g, t, at = m.lastgroup, m[0], m.start()
line, col = src.count("\n", 0, at) + 1, at - src.rfind("\n", 0, at)
if g == "bad":
raise HaatError(line, col, "unterminated string literal" if t == '"' else f"unexpected character '{t}'")
if g == "skip": continue
kind = OPS[t] if g == "op" else t.upper() if g == "IDENT" and t in KW else g
toks.append(Token(kind, t, line, col))
return toks + [Token("EOF", "", src.count("\n") + 1, len(src) - src.rfind("\n"))]
NODES = {"Num": "value", "Str": "value", "Bool": "value", "Var": "name", "Unary": "op operand",
"Binary": "op left right", "Call": "callee args", "Param": "name type",
"Lambda": "params ret body", "Let": "name mutable type init", "Assign": "name value",
"If": "cond then else_", "While": "cond body", "Return": "value", "Print": "value",
"ExprStmt": "expr", "Block": "stmts", "FnDecl": "name params ret body"}
for _name, _fields in NODES.items(): # ast_nodes.py: same names and fields; line, col last
globals()[_name] = make_dataclass(_name, _fields.split() + ["line", "col"], eq=False)
Program = make_dataclass("Program", ["stmts"], eq=False)
TypeName = make_dataclass("TypeName", ["name"], frozen=True, namespace={"__str__": lambda s: s.name})
FnType = make_dataclass("FnType", ["params", "ret"], frozen=True, namespace={
"__str__": lambda s: "(" + ", ".join(map(str, s.params)) + ") -> " + str(s.ret)})
INT, BOOL, STR, UNIT = (TypeName(n) for n in ("Int", "Bool", "Str", "Unit"))
def start(e): # where an expression begins (for error positions)
while isinstance(e, (Binary, Call)): e = e.left if isinstance(e, Binary) else e.callee
return e.line, e.col
INFIX = {"OR_OR": 10, "AND_AND": 20, "EQ_EQ": 30, "BANG_EQ": 30, "LT": 40, "LT_EQ": 40,
"GT": 40, "GT_EQ": 40, "PLUS": 50, "MINUS": 50, "STAR": 60, "SLASH": 60, "PERCENT": 60}
class Parser: # parser.py: recursive descent + Pratt
def __init__(self, tokens): self.toks, self.pos = tokens, 0
def peek(self, ahead=0): return self.toks[min(self.pos + ahead, len(self.toks) - 1)]
def check(self, kind): return self.peek().kind == kind
def advance(self):
tok = self.peek()
if tok.kind != "EOF": self.pos += 1
return tok
def match(self, kind): return self.advance() if self.check(kind) else None
def expect(self, kind, message):
if self.check(kind): return self.advance()
if kind == "SEMI" and self.pos > 0:
prev = self.toks[self.pos - 1]; self.fail(message, (prev.line, prev.col + len(prev.text)))
self.fail(message)
def fail(self, message, where=None):
line, col = where or (self.peek().line, self.peek().col)
raise HaatError(line, col, message)
def statements_until(self, end):
stmts = []
while not self.check(end) and not self.check("EOF"): stmts.append(self.statement())
return stmts
def statement(self):
kind = self.peek().kind
if kind in ("LET", "VAR"):
mutable = self.advance().kind == "VAR"; kw = "var" if mutable else "let"
name = self.expect("IDENT", f"expected variable name after '{kw}'")
ann = self.parse_type() if self.match("COLON") else None
self.expect("EQ", f"expected '=' after variable name in '{kw}'"); init = self.expression()
self.expect("SEMI", "expected ';' after variable declaration")
return Let(name.text, mutable, ann, init, name.line, name.col)
if kind == "FN" and self.peek(1).kind == "IDENT":
self.advance(); name = self.advance()
return FnDecl(name.text, *self.function_rest("expected '(' after function name"), name.line, name.col)
if kind == "IF": return self.if_stmt()
if kind == "WHILE":
kw = self.advance(); cond = self.expression()
return While(cond, self.block("expected '{' after while condition"), kw.line, kw.col)
if kind == "RETURN":
kw = self.advance(); value = None if self.check("SEMI") else self.expression()
self.expect("SEMI", "expected ';' after return"); return Return(value, kw.line, kw.col)
if kind == "PRINT":
kw = self.advance(); self.expect("LPAREN", "expected '(' after 'print'")
value = self.expression(); self.expect("RPAREN", "expected ')' after print argument")
self.expect("SEMI", "expected ';' after print statement"); return Print(value, kw.line, kw.col)
if kind == "LBRACE": return self.block("expected '{'")
first = self.peek(); e = self.expression()
if self.check("EQ"):
if not isinstance(e, Var): self.fail("invalid assignment target")
self.advance(); value = self.expression()
self.expect("SEMI", "expected ';' after assignment"); return Assign(e.name, value, e.line, e.col)
self.expect("SEMI", "expected ';' after expression"); return ExprStmt(e, first.line, first.col)
def block(self, message):
lb = self.expect("LBRACE", message); stmts = self.statements_until("RBRACE")
self.expect("RBRACE", "expected '}' at end of block"); return Block(stmts, lb.line, lb.col)
def if_stmt(self):
kw = self.advance(); cond = self.expression(); then = self.block("expected '{' after if condition")
else_ = None
if self.match("ELSE"):
else_ = self.if_stmt() if self.check("IF") else self.block("expected '{' or 'if' after 'else'")
return If(cond, then, else_, kw.line, kw.col)
def function_rest(self, lparen_message):
self.expect("LPAREN", lparen_message); params = []
if not self.check("RPAREN"):
while True:
p = self.expect("IDENT", "expected parameter name")
self.expect("COLON", f"expected ':' and a type after parameter '{p.text}'")
params.append(Param(p.text, self.parse_type(), p.line, p.col))
if not self.match("COMMA"): break
self.expect("RPAREN", "expected ')' after parameters")
ret = self.parse_type() if self.match("ARROW") else UNIT
return params, ret, self.block("expected '{' before function body")
def parse_type(self):
tok = self.peek()
if tok.kind == "IDENT":
if tok.text not in ("Int", "Bool", "Str", "Unit"): self.fail(f"unknown type '{tok.text}'")
self.advance(); return TypeName(tok.text)
if not self.match("LPAREN"): self.fail("expected a type")
params = [] if self.check("RPAREN") else [self.parse_type()]
while self.match("COMMA"): params.append(self.parse_type())
self.expect("RPAREN", "expected ')' in function type"); self.expect("ARROW", "expected '->' in function type")
return FnType(tuple(params), self.parse_type())
def expression(self, min_bp=0):
t = self.peek()
if t.kind not in ("INT", "STRING", "TRUE", "FALSE", "IDENT", "LPAREN", "MINUS", "BANG", "FN"):
self.fail("expected expression")
self.advance()
if t.kind == "INT": left = Num(int(t.text), t.line, t.col)
elif t.kind == "STRING":
left = Str(re.sub(r'\\(.)', lambda m: "\n" if m[1] == "n" else m[1], t.text[1:-1]), t.line, t.col)
elif t.kind in ("TRUE", "FALSE"): left = Bool(t.kind == "TRUE", t.line, t.col)
elif t.kind == "IDENT": left = Var(t.text, t.line, t.col)
elif t.kind in ("MINUS", "BANG"): left = Unary(t.text, self.expression(70), t.line, t.col)
elif t.kind == "FN": left = Lambda(*self.function_rest("expected '(' after 'fn'"), t.line, t.col)
else:
left = self.expression(); self.expect("RPAREN", "expected ')' after expression")
last_cmp = None
while True:
t = self.peek()
if t.kind == "LPAREN":
if min_bp > 80: return left
self.advance(); args = [] if self.check("RPAREN") else [self.expression()]
while self.match("COMMA"): args.append(self.expression())
self.expect("RPAREN", "expected ')' after arguments")
left = Call(left, args, *start(left)); continue
bp = INFIX.get(t.kind, -1)
if bp < min_bp: return left
if bp in (30, 40) and last_cmp == bp: self.fail("comparison operators cannot be chained")
self.advance()
left = Binary(t.text, left, self.expression(bp + 1), t.line, t.col); last_cmp = bp
def parse(src): return Program(Parser(tokenize(src)).statements_until("EOF"))
MAX_CALL_DEPTH = 1000 # runtime.py: shared helpers
def wrap(n): return ((n + 2**63) % 2**64) - 2**63
def runtime_error(line, col, msg): return HaatError(line, col, msg, runtime=True)
def c_div(a, b, line, col):
if b == 0: raise runtime_error(line, col, "division by zero")
q = abs(a) // abs(b); return wrap(q if (a < 0) == (b < 0) else -q)
def c_mod(a, b, line, col):
if b == 0: raise runtime_error(line, col, "division by zero")
q = abs(a) // abs(b); q = q if (a < 0) == (b < 0) else -q
return wrap(a - b * q)
def arith(op, a, b, line, col):
if op == "+": return a + b if isinstance(a, str) else wrap(a + b)
if op == "-": return wrap(a - b)
if op == "*": return wrap(a * b)
if op == "/": return c_div(a, b, line, col)
if op == "%": return c_mod(a, b, line, col)
return {"==": a == b, "!=": a != b, "<": a < b, "<=": a <= b, ">": a > b, ">=": a >= b}[op]
def show(v): return ("true" if v else "false") if isinstance(v, bool) else str(v)৪ · Expression-এর lowering — post-order আর temp
AST থেকে IR-এ নামার কাজটির নাম lowering. Expression-এর জন্য নিয়মটি পর্ব ৫৮-এর stack code-এর মতোই postorder traversal: আগে operand, পরে operator. পার্থক্য একটি জায়গায়: stack code মাঝের ফল stack-এ রাখে, three-address code প্রতিটি মাঝের ফলকে একটি নতুন temp দেয়। নিয়মগুলো একটি function E দিয়ে লেখা যায়, যা expression e-এর কোড লেখে আর সেই নামটি ফেরত দেয় যেখানে e-এর মান থাকবে:
E(n) = নতুন t, কোড t = const n · E(x) = x, যদি x local (কোনো নির্দেশ নয়) · E(x) = নতুন t; t = @x, যদি x global · E(⊖e) = a ← E(e); নতুন t; t = ⊖ a · E(e1 ⊕ e2) = a ← E(e1); b ← E(e2); নতুন t; t = a ⊕ b · E(f(e1, …, en)) = ai ← E(ei) বাঁ থেকে ডানে; নতুন t; t = call f(a1, …, an)
এখানে “কোড” মানে নির্দেশটি তালিকার শেষে যোগ হয়, ⊕ যেকোনো binary operator (&& আর || বাদে, অংশ ৫), আর বাঁ আগে ডান পরে হলো reference-এর সিদ্ধান্ত ১২-এর সরাসরি রূপ। খেয়াল করুন local variable-এর জন্য কোনো নির্দেশই নেই: তার নামই ঠিকানা। নিচের stepper-এ qty * unit - p / 10, যেখানে তিনটি নামই local, আর ডানে একই expression-এর stack code পাশাপাশি।
1Binary "-"2├─ Binary "*"3│ ├─ Var qty4│ └─ Var unit5└─ Binary "/"6 ├─ Var p7 └─ Num 10
| নতুন নির্দেশ | |
| ফেরত নাম | |
| nt |
- মূল node বিয়োগ। Post-order, তাই আগে বাঁ সন্তান। এখনো কিছু লেখা হয়নি; temp-এর গণক
ntশূন্য। - গুণ।
qtyআরunitlocal, তাই E তাদের নামই ফেরত দেয়, কোনো নির্দেশ ছাড়া। তারপর একটি নির্দেশ:t1 = qty * unit. Stack code-এ এখানে তিনটি নির্দেশ লাগে, কারণ দুটি load আলাদা। - ভাগের দুই সন্তান।
pনামেই আসে; 10 একটি ধ্রুবক, আর Haat IR-এ ধ্রুবক operand হতে পারে না, তাইt2 = const 10. - ভাগ।
t3 = p / t2. এই নির্দেশেরpos-এ/চিহ্নের অবস্থান রাখা হয়, কারণ শূন্য দিয়ে ভাগ হলে error ঠিক এখানে বলতে হবে। - বিয়োগ।
t4 = t1 - t3, আর E ফেরত দেয়t4: পুরো expression-এর মান সেখানে। চারটি নির্দেশ, stack code-এর সাতটির জায়গায়। let pay = …;হলে।into(pay, t4)দেখে শেষ নির্দেশটিই এইমাত্রt4বানিয়েছে, তাই নতুন copy না লিখে সেই নির্দেশের dst বদলেpayকরে, আর t4-এর নম্বর ফেরত যায় (nt = 3). ফল:pay = t1 - t3, যেমন মানুষ হাতে লিখত।
এবার আসল কোড, haat_ir.py-র Lower class থেকে হুবহু। emit নির্দেশ যোগ করে আর dst ফেরত দেয়, temp() নতুন t নাম দেয়, lookup scope-এর শিকলে নাম খোঁজে (না পেলে সেটি top-level function, অথবা function-এর ভেতর থেকে দেখা global). made আর into হলো stepper-এর শেষ ধাপের কৌশল:
class Lower: # Haat AST -> রৈখিক Haat IR, একবারে একটি function
def __init__(self, fns): self.fns, self.used = fns, set() # top-level fn-এর নাম; function-এর দেখা global
def emit(self, kind, dst=None, args=(), sym=None, targets=(), pos=None):
if not self.dead: # return/jump-এর পরের কোডে কখনো পৌঁছানো যায় না: বাদ
self.f.code.append(Ins(kind, dst, list(args), sym, list(targets), pos))
self.dead = kind in ("jump", "branch", "return"); self.hit |= set(targets)
return dst
def temp(self): self.nt += 1; return f"t{self.nt}"
def label(self): self.nl += 1; return f"L{self.nl}"
def place(self, L): # label বসে শুধু যদি সেখানে পৌঁছানো যায়
if not self.dead or L in self.hit: self.dead = False; self.emit("label", targets=[L])
def made(self, a): # a কি এইমাত্র শেষ নির্দেশে তৈরি temp?
return not self.dead and self.f.code and self.f.code[-1].dst == a and is_temp(a)
def into(self, x, a): # x = a; a নতুন temp হলে শেষ নির্দেশটিই x-এ লেখে
if self.made(a) and x[0] != "@":
self.f.code[-1].dst = x
if x != a and a == f"t{self.nt}": self.nt -= 1 # temp-টি আর লাগে না: নম্বরটি ফেরত
else: self.emit("copy", x, [a])
def lookup(self, name):
for scope in reversed(self.scopes):
if name in scope: return scope[name]
if name in self.fns: return None # top-level function
self.used.add(name); return "@" + name # function-এর ভেতর থেকে দেখা top-level variable
def expr(self, e): # post-order; ফেরত দেয় সেই নাম, যেখানে মানটি থাকবে
if isinstance(e, (Num, Str, Bool)): return self.emit("const", self.temp(), (), e.value)
if isinstance(e, Var):
x = self.lookup(e.name)
if x is None: raise Unsupported(f"{e.line}:{e.col}: function '{e.name}' used as a value")
return self.emit("copy", self.temp(), [x], pos=(e.line, e.col)) if x[0] == "@" else x
if isinstance(e, Unary): a = self.expr(e.operand); return self.emit("un", self.temp(), [a], e.op)
if isinstance(e, Binary) and e.op in ("&&", "||"): # short-circuit: শাখা দিয়ে
a = self.expr(e.left); t = a if self.made(a) else self.temp(); self.into(t, a)
right, end = self.label(), self.label()
self.emit("branch", None, [t], targets=[right, end] if e.op == "&&" else [end, right])
self.place(right); self.into(t, self.expr(e.right)); self.place(end); return t
if isinstance(e, Binary):
a, b = self.expr(e.left), self.expr(e.right) # বাঁ আগে (সিদ্ধান্ত ১২)
return self.emit("bin", self.temp(), [a, b], e.op, pos=(e.line, e.col))
if isinstance(e, Call) and isinstance(e.callee, Var) and self.lookup(e.callee.name) is None:
args = [self.expr(a) for a in e.args]
return self.emit("call", self.temp(), args, e.callee.name, pos=(e.line, e.col))
raise Unsupported(f"{e.line}:{e.col}: closures and function values are not in Haat IR v1")into-এর শর্তটি গুরুত্বপূর্ণ: dst বদলানো নিরাপদ শুধু তখন, যখন a একটি নতুন temp যা এইমাত্র শেষ নির্দেশে তৈরি হয়েছে, কারণ তখন a আর কোথাও ব্যবহার হয়নি। a যদি একটি variable হয় (let y = x;), dst বদলালে x-এর সংজ্ঞাই মুছে যেত; তখন সাধারণ copy y = x. আর global-এ dst কখনো বদলায় না, যাতে @x-এ লেখা সবসময় একটি আলাদা, পরীক্ষাযোগ্য copy থাকে। শেষ লাইনটিও দেখুন: closure আর function-কে মান হিসেবে ব্যবহার Haat IR v1-এ নেই। বড় ভাষা এগুলো IR-এ নামার আগে closure conversion-এর মতো ধাপে আরও সরল রূপে আনে (পর্ব ৫৫ আর পর্ব ৫৭)।
৫ · Statement-এর lowering — শাখা, loop আর মৃত কোড
Statement-এর lowering লাফে নামে; if আর while-কে label আর লাফে নামানোর কৌশল, backpatching-সহ, পর্ব ২৭-এ বিস্তারিত। Haat IR-এর একটি সুবিধা আছে: লাফের লক্ষ্য একটি নাম (L3), সংখ্যা নয়, তাই নাম আগে বানিয়ে পরে বসানো যায়, backpatching লাগে না। নিয়মগুলো, যেখানে S(s) statement s-এর কোড লেখে:
S(if c {A} else {B}) = c′ ← E(c); branch c′ L1 L2; label L1; S(A); jump L3; label L2; S(B); label L3 · S(while c {A}) = label L1; c′ ← E(c); branch c′ L2 L3; label L2; S(A); jump L1; label L3 · S(let x = e) = into(x, E(e)) · S(return e) = return E(e)
else না থাকলে branch c′ L1 L3, আর then-এর শেষের jump বাদ, কারণ পরের নির্দেশই label L3. Short-circuit a && b expression হলেও শাখা দিয়ে নামে: t ← E(a); branch t L1 L2; label L1; t ← E(b); label L2. ফলে একটি temp t দুই জায়গায় মান পায়, যা পর্ব ৬৩-এর φ-এর জন্য একটি সুন্দর উদাহরণ। a || b একই, শুধু branch-এর দুই লক্ষ্য উল্টো।
একটি বাড়তি নিয়ম কোডকে পরিষ্কার রাখে: return, jump বা branch-এর পরে পরের label পর্যন্ত কোডে কখনো পৌঁছানো যায় না, তাই emit সেখানে কিছুই লেখে না (self.dead). আর একটি label বসে শুধু যদি কেউ সেখানে লাফায় বা আগের কোড সেখানে গড়িয়ে পড়ে। delivery-র if … { return 0; } else { return 60; }-এর পরে তাই কোনো মৃত block তৈরি হয় না। পর্ব ৫৪-এ এই unreachable code warning দিয়ে ধরা হয়েছিল; এখানে সেটি নিঃশব্দে বাদ যায়, কারণ চলার আচরণে তার কোনো প্রভাব নেই।
def function(self, name, params, stmts):
self.f, self.nt, self.nl, self.dead, self.hit = IRFunction(name, []), 0, 0, False, set()
self.scopes, self.taken = [{}], set()
self.f.params = [self.declare(p.name) for p in params]
for s in stmts: self.stmt(s)
if not self.dead: self.emit("return", None, [self.emit("const", self.temp(), (), None)]) # Unit
return self.f
def stmt(self, s):
if isinstance(s, Let):
a = self.expr(s.init)
if self.f.name == "<main>" and len(self.scopes) == 1 and s.name in self.used:
self.scopes[0][s.name] = "@" + s.name; self.emit("copy", "@" + s.name, [a])
else: self.into(self.declare(s.name), a)
elif isinstance(s, Assign):
a, x = self.expr(s.value), self.lookup(s.name)
if x[0] == "@": self.emit("copy", x, [a], pos=(s.line, s.col)) # সিদ্ধান্ত ১৮-এর পরীক্ষা
else: self.into(x, a)
elif isinstance(s, If):
c = self.expr(s.cond); then = self.label()
other = self.label() if s.else_ else None; end = self.label(); other = other or end
self.emit("branch", None, [c], targets=[then, other]); self.place(then); self.block(s.then.stmts)
if s.else_:
self.emit("jump", targets=[end]); self.place(other)
self.block([s.else_] if isinstance(s.else_, If) else s.else_.stmts)
self.place(end)
elif isinstance(s, While):
top, body, end = self.label(), self.label(), self.label()
self.place(top); self.emit("branch", None, [self.expr(s.cond)], targets=[body, end])
self.place(body); self.block(s.body.stmts); self.emit("jump", targets=[top]); self.place(end)
elif isinstance(s, Return):
v = self.expr(s.value) if s.value else self.emit("const", self.temp(), (), None)
self.emit("return", None, [v])
elif isinstance(s, Print): self.emit("print", None, [self.expr(s.value)])
elif isinstance(s, ExprStmt): self.expr(s.expr)
elif isinstance(s, Block): self.block(s.stmts)
else: raise Unsupported(f"{s.line}:{s.col}: nested functions are not in Haat IR v1")এবার চালিয়ে দেখুন। নিচের program-এ তিনটি জিনিস একসঙ্গে: function-এর ভেতর থেকে পড়া global (fee), শর্তে &&, আর top-level-এ shadowing. শেষে একটি lambda, যা Haat IR v1 ফিরিয়ে দেয়।
# ধাপ ১: Haat থেকে রৈখিক Haat IR — haat_ir.py-র Lower চালিয়ে দেখা
from haat_ir import * # Ins, Lower, lower_program, show_ir, parse …
src = """var fee = 60;
fn charge(total: Int, express: Bool) -> Int {
if total >= 1000 && !express { return 0; }
return fee;
}
let total = charge(1200, false) + charge(500, true);
{ let total = 1; print(total); }
print(total);
""" # src বদলে আবার চালান
mod = lower_program(parse(src))
print("globals:", mod.globals)
for fn in mod.funcs.values(): print(show_ir(fn))
try: lower_program(parse("let twice = fn(x: Int) -> Int { return x * 2; };"))
except Unsupported as e: print("Unsupported:", e)আসল আউটপুট (ব্রাউজারের Python):
globals: ['fee']
fn <main>():
t1 = const 60
@fee = t1
t2 = const 1200
t3 = const false
t4 = call charge(t2, t3)
t5 = const 500
t6 = const true
t7 = call charge(t5, t6)
total = t4 + t7
total.1 = const 1
print total.1
print total
t8 = const ()
return t8
fn charge(total, express):
t1 = const 1000
t2 = total >= t1
branch t2 L1 L2
label L1
t2 = ! express
label L2
branch t2 L3 L4
label L3
t3 = const 0
return t3
label L4
t4 = @fee
return t4
Unsupported: 1:13: closures and function values are not in Haat IR v1
পড়ার মতো কয়েকটি জিনিস। fee একমাত্র global, কারণ শুধু সেটিই function-এর ভেতর থেকে দেখা হয়; তাই <main>-এ @fee = t1 আর charge-এ t4 = @fee. অন্যদিকে top-level-এর total সাধারণ local, আর ভেতরের block-এর total হয়েছে total.1; charge-এর parameter-ও total, কিন্তু সেটি অন্য function, তাই কোনো সংঘাত নেই। &&-এর ফল t2 দুবার লেখা হয়েছে (t2 = total >= t1 আর t2 = ! express), আর তারপর if আবার t2 দেখে শাখা নেয়। reference একই program চালালে ছাপে 1 আর 60. শেষ লাইনটি সৎ সীমা: closure Haat IR v1-এর বাইরে, আর lowering সেটি চুপচাপ ভুল অনুবাদ না করে স্পষ্ট বার্তায় থামে।
৬ · Basic block আর leader
রৈখিক IR-কে এবার টুকরো করা হবে। একটি basic block হলো নির্দেশের এমন একটানা সারি, যাতে ঢোকা যায় শুধু প্রথম নির্দেশ দিয়ে আর বেরোনো যায় শুধু শেষ নির্দেশ দিয়ে; তাই block-এ ঢুকলে পুরোটা চলে, ক্রমে। মেট্রোরেলের কথা ভাবুন: দুটি স্টেশনের মাঝে ট্রেন থামে না, শাখাও নেয় না; সিদ্ধান্ত হয় শুধু স্টেশনে। Block-এর ভেতরে তাই হিসাব সহজ, আর পর্ব ৬৫-এর local optimization ঠিক এই সুবিধা নেয়।
Block খোঁজার পাঠ্যবইয়ের পদ্ধতি হলো leader চিহ্নিত করা; প্রতিটি leader থেকে পরের leader-এর আগ পর্যন্ত একটি block:
(১) প্রথম নির্দেশ একটি leader. (২) যেকোনো jump বা branch-এর লক্ষ্য (একটি label-এর পরের নির্দেশ) leader. (৩) যেকোনো jump, branch বা return-এর ঠিক পরের নির্দেশ leader. তারপর: label মুছে লক্ষ্যগুলো block-এর নামে বদলানো, আর যে block terminator ছাড়া শেষ হয় (পরের block-এ গড়িয়ে পড়ে), তার শেষে একটি স্পষ্ট jump যোগ করা।
শেষ ধাপটি Haat IR-এর একটি পছন্দ: প্রতিটি block-এর শেষ নির্দেশ সবসময় jump, branch বা return. তাহলে block-এর ক্রম বদলালেও অর্থ বদলায় না, আর block থেকে কোথায় যাওয়া যায়, তা শুধু শেষ নির্দেশ দেখেই জানা যায়। LLVM IR-ও ঠিক এই নিয়ম মানে। নিচে bazar.haat-এর <main>-এর ২৮ লাইনের রৈখিক রূপ (৩টি label-সহ), সংক্ষেপে:
10–8 t1 … print first29 total = const 0310 rounds = const 0411 label L1512 t8 = const 5000613 t9 = total < t8714 branch t9 L2 L3815 label L2916–19 t10 = … rounds + t111020 jump L11121 label L31222–27 print total …
| নতুন leader | |
| label → block | |
| block |
- নিয়ম ১. index 0 একটি leader, তাই B0 শুরু। 0 থেকে 10 পর্যন্ত কোনো label বা লাফ নেই, তাই সব B0-তে।
- প্রথম label. 11-এ
label L1, অর্থাৎ পরের আসল নির্দেশ 12 একটি লাফের লক্ষ্য (নিয়ম ২)। B1 শুরু হয়, আর L1-এর নাম হয় B1. B0 কোনো terminator ছাড়া শেষ হয়েছে (10 থেকে 12-এ গড়িয়ে পড়ে), তাই B0-র শেষে যোগ হলোjump B1. - Branch-এর পরে। 14-এর
branch-এর পরের নির্দেশ leader (নিয়ম ৩); সেটি আবার L2-এর লক্ষ্যও (নিয়ম ২)। দুই নিয়ম একই জায়গা দেখায়: B2 শুরু 16-এ। - Jump-এর পরে। 20-এর
jump L1-এর পরে 21-এlabel L3, তারপর 22: B3. এখানেও দুই নিয়ম মেলে। লক্ষ্য করুন, পরপর দুটি label থাকলে দুটিই একই block-এর নাম পেত, খালি block তৈরি হতো না। - লক্ষ্যের নাম বদল। সব label মুছে যায়;
branch t9 L2 L3হয়branch t9 B2 B3, আরjump L1হয়jump B1. - ফল। চারটি block: B0-তে ১২টি নির্দেশ (১১টি মূল আর যোগ করা jump), B1-এ ৩টি, B2-তে ৫টি, B3-তে ৬টি। রৈখিক রূপের ২৫টি আসল নির্দেশ আর একটি নতুন jump: মোট ২৬।
কোডে অ্যালগরিদমটি এক pass-এর: label জমিয়ে রাখা হয় (pending) যতক্ষণ না একটি আসল নির্দেশ আসে, আর leader-এর তিন নিয়ম একটি লাইনে। নিচের ব্লকের build_cfg, succs আর preds haat_ir.py-তে হুবহু এই রূপে আছে।
# ধাপ ২: leader থেকে basic block আর CFG — haat_ir.py-তে হুবহু এই কোড
from haat_ir import Ins, replace, lower_program, parse, show_ir
TERMINATORS = ("jump", "branch", "return")
def build_cfg(fn): # leader খুঁজে basic block B0, B1 …; প্রতিটির শেষে terminator
code, starts, name, pending = [], [], {}, []
for ins in fn.code: # label সরিয়ে, label-কে পরের নির্দেশের সঙ্গে জোড়া
if ins.kind == "label": pending.append(ins.targets[0]); continue
if not code or pending or code[-1].kind in TERMINATORS: starts.append(len(code)) # leader-এর তিন নিয়ম
for L in pending: name[L] = f"B{len(starts) - 1}"
pending = []; code.append(ins)
fn.blocks, ends = {}, starts[1:] + [len(code)]
for n, (s, e) in enumerate(zip(starts, ends)):
body = [replace(i, args=list(i.args), targets=[name.get(t, t) for t in i.targets]) for i in code[s:e]]
if body[-1].kind not in TERMINATORS: body.append(Ins("jump", targets=[f"B{n + 1}"])) # fall-through
fn.blocks[f"B{n}"] = body
return fn
def succs(fn, b): # block b-এর পরে কোন block চলতে পারে
last = fn.blocks[b][-1]
return [] if last.kind == "return" else list(dict.fromkeys(last.targets))
def preds(fn): # প্রতিটি block-এ কোন block থেকে আসা যায়
p = {b: [] for b in fn.blocks}
for b in fn.blocks:
for s in succs(fn, b): p[s].append(b)
return p
main = build_cfg(lower_program(parse(open("examples/bazar.haat", encoding="utf-8").read())).funcs["<main>"])
print(show_ir(main))
for b in main.blocks: print(f"{b}: succ {succs(main, b)} pred {preds(main)[b]}")আসল আউটপুট (ব্রাউজারের Python):
fn <main>():
B0:
t1 = const 2
t2 = const 520
t3 = call price(t1, t2)
t4 = const 2
t5 = const 520
t6 = call price(t4, t5)
t7 = call delivery(t6)
first = t3 + t7
print first
total = const 0
rounds = const 0
jump B1
B1:
t8 = const 5000
t9 = total < t8
branch t9 B2 B3
B2:
t10 = const 1250
total = total + t10
t11 = const 1
rounds = rounds + t11
jump B1
B3:
print total
t12 = const 1
t13 = rounds - t12
print t13
t14 = const ()
return t14
B0: succ ['B1'] pred []
B1: succ ['B2', 'B3'] pred ['B0', 'B2']
B2: succ ['B1'] pred ['B1']
B3: succ [] pred ['B1']
Stepper-এর চারটি block, একই নির্দেশ। শেষের চার লাইন graph-এর edge: B1-এর দুটি successor (loop-এর ভেতরে B2, বাইরে B3), আর B1-এর দুটি predecessor (প্রথমবার B0 থেকে, পরে প্রতিটি round-এর শেষে B2 থেকে)। একটি block-এ দুই দিক থেকে আসা যায় মানে সেখানে দুটি পথ মেলে; ঠিক এমন জায়গাতেই পর্ব ৬৩-এ φ বসবে। preds প্রতিবার পুরো graph ঘুরে হিসাব করে; বড় program-এ একবার হিসাব করে রাখাই ভালো, কিন্তু IR বদলানো pass-গুলোর জন্য টাটকা হিসাব নিরাপদ।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
a = b * c + d-এর three-address code?t1 = b * c; t2 = t1 + d; a = t2(বা শেষ দুটি মিলিয়েa = t1 + d).- Leader-এর নিয়ম? প্রথম নির্দেশ, যেকোনো লাফের লক্ষ্য, আর যেকোনো লাফ বা return-এর পরের নির্দেশ।
- Quadruple বনাম triple? Quadruple-এ ফলের নাম থাকে, সরানো সহজ; triple-এ ফল = সারির নম্বর, জায়গা কম কিন্তু সরালে উল্লেখ ভাঙে; indirect triple এর সমাধান।
- CFG-তে edge কখন? B1-এর শেষ নির্দেশ B2-তে লাফ দিতে পারলে, বা B1 B2-তে গড়িয়ে পড়লে।
- IR কেন? m × n থেকে m + n, optimization একবার লেখা, আর যন্ত্র-নিরপেক্ষ বিশ্লেষণ।
৭ · Control flow graph — successor, predecessor আর loop
Block-গুলোকে node আর “এরপর চলতে পারে” সম্পর্ককে edge ধরলে পাওয়া যায় control flow graph (CFG). আনুষ্ঠানিকভাবে: G = (N, E, B0), যেখানে N হলো block-এর সেট, B0 entry, আর (Bi, Bj) ∈ E যদি Bi-এর terminator Bj-তে যেতে পারে। Frances Allen ১৯৭০ সালের “Control Flow Analysis” প্রবন্ধে এই graph-কে optimization-এর কেন্দ্রে বসান; কাজটির জন্য তিনি ২০০৬ সালে Turing Award পান (ভাবনার প্রশ্ন ৩)।
ছবি ৬২.২ — bazar.haat-এর <main>-এর CFG
অংশ ৬-এর ব্লকের সত্যিকারের আউটপুট থেকে আঁকা
jump B1 থেকে।CFG-এর ওপর তিনটি প্রশ্ন বারবার আসবে। কোন block-এ পৌঁছানো যায় না? (B0 থেকে graph ঘুরে যে block-এ পৌঁছানো যায় না, তা মুছে ফেলা নিরাপদ; Haat-এর lowering আগেই মৃত কোড বাদ দেয়, তাই এখানে সাধারণত শূন্য।) Loop কোথায়? (একটি DFS-এ যে edge এখনো খোলা কোনো block-এ ফেরে, সেটি back edge; গ্রাফের DFS আছে DSA কোর্সের পর্ব ৪১-এ, আর loop-এর নিখুঁত সংজ্ঞা dominator দিয়ে, পর্ব ৬৬-এ।) আর কোথায় পথ মেলে? (যে block-এর একাধিক predecessor, যেমন B1.) Haat-এর CFG সবসময় reducible, কারণ Haat-এ goto নেই (পর্ব ২৭)।
নিচের JavaScript ব্লক Haat IR-এর text থেকে CFG বানায়। একটি নতুন function, stock_days, যা বাজারঘরের গুদামে মাল কত দিন চলবে তা গোনে, শর্তে &&-সহ: while left > 0 && days < 30. এর Haat IR ছয়টি block-এর; CFG-এর জন্য শুধু প্রতিটি block-এর terminator লাগে, তাই বাকি নির্দেশ বাদ রাখা হয়েছে।
// Haat IR-এর text থেকে CFG; শুধু terminator লাগে, তাই stock_days-এর বাকি নির্দেশ বাদ
const IR = `B0:
jump B1
B1:
branch t2 B2 B3
B2:
jump B3
B3:
branch t2 B4 B5
B4:
jump B1
B5:
return days`; // নিজের IR (পুরোটা বা শুধু terminator) বসিয়ে আবার চালান
const blocks = {}; let cur = null;
for (const line of IR.split("\n")) {
if (/^B\d+:$/.test(line)) blocks[cur = line.slice(0, -1)] = [];
else if (cur && line.trim()) blocks[cur].push(line.trim());
}
const succ = {}, pred = Object.fromEntries(Object.keys(blocks).map(b => [b, []]));
for (const b in blocks) {
const [op, ...rest] = blocks[b].at(-1).split(" "); // শেষ নির্দেশই বলে পরে কোথায়
succ[b] = op === "jump" ? rest : op === "branch" ? [...new Set(rest.slice(1))] : [];
succ[b].forEach(s => pred[s].push(b));
}
const state = {}, order = [], back = [];
function dfs(b) { // পথে এখনো খোলা block-এ ফেরা edge = back edge
state[b] = "open"; order.push(b);
for (const s of succ[b]) state[s] === "open" ? back.push(`${b}→${s}`) : !state[s] && dfs(s);
state[b] = "done";
}
dfs("B0");
for (const b in blocks) console.log(`${b} │ succ ${succ[b].join(",") || "—"} │ pred ${pred[b].join(",") || "—"}`);
console.log("DFS ক্রম:", order.join(" "), "│ back edge:", back.join(" ") || "নেই");
console.log("পৌঁছানো যায় না:", Object.keys(blocks).filter(b => !state[b]).join(" ") || "কোনোটি নয়");
console.log("digraph cfg { " + Object.keys(blocks).flatMap(b => succ[b].map(s => `${b} -> ${s};`)).join(" ") + " }");আসল আউটপুট (browser-এর JavaScript):
B0 │ succ B1 │ pred —
B1 │ succ B2,B3 │ pred B0,B4
B2 │ succ B3 │ pred B1
B3 │ succ B4,B5 │ pred B1,B2
B4 │ succ B1 │ pred B3
B5 │ succ — │ pred B3
DFS ক্রম: B0 B1 B2 B3 B4 B5 │ back edge: B4→B1
পৌঁছানো যায় না: কোনোটি নয়
digraph cfg { B0 -> B1; B1 -> B2; B1 -> B3; B2 -> B3; B3 -> B4; B3 -> B5; B4 -> B1; }
পুরো IR-টি haat_ir.py-র আসল আউটপুট: B1-এ t2 = left > t1 আর branch t2 B2 B3; B2-তে &&-এর ডান দিক, t2 = days < t3; B3 শুধু branch t2 B4 B5, অর্থাৎ loop-এর আসল সিদ্ধান্ত; B4 loop-এর শরীর। &&-এর কারণে loop-এর শর্ত এখন দুটি block জুড়ে, আর B3-এ দুই পথ মেলে (B1 থেকে, যখন বাঁ দিক মিথ্যা, আর B2 থেকে)। Back edge একটি: B4→B1. শেষ লাইনটি Graphviz-এর DOT ভাষা; যেকোনো Graphviz tool-এ দিলে ছবি আঁকা হয়। reference এই program-এ (stock_days(100, 15) আর stock_days(1000, 7)) ছাপে 7 আর 30, আর Haat IR interpreter-ও তাই।
৮ · IR interpreter আর differential test
IR বানানো হলো; কিন্তু কীভাবে জানবেন lowering অর্থ বদলায়নি? সবচেয়ে সরাসরি উত্তর: IR-টিকেই চালানো, আর ফল reference-এর tree-walking interpreter-এর সঙ্গে মেলানো। এই পরীক্ষার নাম differential testing, আর এই মডিউলে এটি স্থায়ী নিয়ম: প্রতিটি optimization-এর আগে আর পরে IR চালাতে হবে, আর আউটপুট python -B haat.py run-এর সঙ্গে হুবহু মিলতে হবে।
run_ir একটি ছোট loop: frame-এর একটি stack (function, variable-এর dict, এখনকার block, block-এর ভেতরে index), আর প্রতিটি নির্দেশে একটি কাজ। Python-এর recursion ব্যবহার করে না, তাই Haat-এর ১,০০০ গভীরতার call-ও নিরাপদ, আর stack overflow-এর সীমা reference-এর মতোই (সিদ্ধান্ত ২৬)। Block-এ ঢোকার সময় enter শুরুর φ-গুলো আগের block দেখে হিসাব করে; এই পর্বের IR-এ φ নেই, কিন্তু পর্ব ৬৩ এই interpreter-ই অপরিবর্তিত ব্যবহার করবে।
def run_ir(mod, out=print): # CFG-সহ IRModule চালায়; ফেরত দেয় কয়টি নির্দেশ চলল
mem, steps = {}, 0 # mem: global variable (@ ছাড়া নাম)
def val(x, env, pos):
if x[0] != "@": return env[x]
if x[1:] not in mem: raise runtime_error(*pos, f"'{x[1:]}' is not initialized yet")
return mem[x[1:]]
def enter(fr, b): # block b-তে ঢোকা; শুরুর phi-গুলো আগের block দেখে (পর্ব ৬৩)
body = fr[0].blocks[b]; phis = [p for p in body if p.kind == "phi"]
vals = [fr[1][p.args[p.targets.index(fr[2])]] for p in phis]
for p, v in zip(phis, vals): fr[1][p.dst] = v
fr[2], fr[3] = b, len(phis)
stack = [[mod.funcs["<main>"], {}, "B0", 0, None]] # frame: fn, env, block, index, caller-এর dst
while stack:
fr = stack[-1]; fn, env, b, i, _ = fr
ins = fn.blocks[b][i]; fr[3] += 1; steps += 1
k, a = ins.kind, [val(x, env, ins.pos) for x in ins.args]
if k in ("const", "copy", "bin", "un"):
v = ins.sym if k == "const" else a[0] if k == "copy" else \
arith(ins.sym, a[0], a[1], *(ins.pos or (0, 0))) if k == "bin" else wrap(-a[0]) if ins.sym == "-" else not a[0]
if ins.dst[0] != "@": env[ins.dst] = v
elif ins.pos and ins.dst[1:] not in mem: raise runtime_error(*ins.pos, f"'{ins.dst[1:]}' is not initialized yet")
else: mem[ins.dst[1:]] = v
elif k == "print": out(show(a[0]))
elif k == "jump": enter(fr, ins.targets[0])
elif k == "branch": enter(fr, ins.targets[0] if a[0] else ins.targets[1])
elif k == "call":
if len(stack) > MAX_CALL_DEPTH: raise runtime_error(*ins.pos, "stack overflow")
f = mod.funcs[ins.sym]; stack.append([f, dict(zip(f.params, a)), "B0", 0, ins.dst])
elif k == "return":
stack.pop()
if stack: stack[-1][1][fr[4]] = a[0]
return steps1B0:2 p = qty * unit3 t1 = const 10004 t2 = p >= t15 branch t2 B1 B26B1:7 t3 = const 108 t4 = p / t39 t5 = p - t410 return t511B2:12 return p
| block | |
| নতুন মান | |
| steps |
- ঢোকা।
<main>-এরt3 = call price(t1, t2)একটি নতুন frame ঠেলে দিয়েছে: env-এqty = 2,unit = 520, block B0, index 0. প্রথম নির্দেশ:p = 2 × 520 = 1040. - ধ্রুবক।
t1 = 1000. ধ্রুবক নির্দেশ শুধু env-এ একটি ঘর ভরে। - তুলনা।
t2 = 1040 >= 1000, অর্থাৎtrue. Haat-এর তুলনা Bool দেয়, তাইarithPython-এরTrueফেরত দেয়। - শাখা।
branch t2 B1 B2: t2 সত্য, তাইenter(fr, "B1"). Block আর index বদলায়; B1-এর শুরুতে কোনো φ নেই। চারটি নির্দেশ চলেছে। - B1-এর ধ্রুবক।
t3 = 10. - ভাগ।
t4 = 1040 / 10 = 104, reference-এরc_divদিয়ে, যা শূন্যের দিকে কাটে আর ভাজক শূন্য হলে এই নির্দেশেরpos-এ error দিত। - বিয়োগ।
t5 = 1040 − 104 = 936; প্রতিটি Int ফল ৬৪ বিটে wrap হয়। - ফেরা।
return t5: frame সরে, আর মানটি caller-এর frame-এt3-তে বসে, কারণ call-এর সময় dst মনে রাখা ছিল।price-এ মোট ৮টি নির্দেশ চলল; B2 এবার চলেনি।
এবার পুরো পরীক্ষা। Reference-এর examples ফোল্ডারের ১০টি program (তিনটি ইচ্ছাকৃত static error-এর ফাইল বাদে) পাতায় দেওয়া আছে, প্রতিটির সঙ্গে reference-এর .out ফাইল। আর haat_gen.py seed থেকে এলোমেলো program বানায়: global, ১–৩টি function, if/else, সীমিত while, &&/||, wrap হওয়া বড় সংখ্যা আর কখনো শূন্য দিয়ে ভাগ। লেখকের lab-এ প্রথম ২০০টি seed-এর program reference-এর run-এ চালিয়ে প্রতিটির আউটপুটের একটি ছোট digest (SHA-256-এর প্রথম ১০ hex অক্ষর) random_ref.txt-এ রাখা হয়েছে। নিচের ব্লক একই program বানিয়ে IR-এ চালায় আর digest মেলায়।
সহায়ক module haat_gen.py দেখুন (এলোমেলো program)
# haat_gen.py — সহায়ক অংশ: seed থেকে এলোমেলো, কিন্তু reference-এর check পাস করা first-order Haat program.
# Int-এর হিসাব (wrap, C-ধাঁচের / আর %, শূন্য দিয়ে ভাগ), && ||, if/else, while, call, global আর shadowing.
import random
def gen_program(seed):
R, lines, fns, loops = random.Random(seed), [], [], [0]
scopes = [{"g0": True, "g1": True}] # প্রতিটি scope: নাম -> var কি না; "#used": যে নাম পড়া হয়েছে
def names(): return [n for sc in scopes for n in sc if n[0] != "#"]
def use(n):
for sc in scopes: sc.setdefault("#used", set()).add(n)
def iexp(d): # Int expression
r, vs = R.random(), names()
if d <= 0 or r < 0.3:
if vs and R.random() < 0.6: n = R.choice(vs); use(n); return n
return R.choice([str(R.randint(0, 12)), str(R.randint(0, 12)), "9223372036854775807"])
if r < 0.38: return f"-{iexp(d - 1)}"
if r < 0.5 and fns:
f, k = R.choice(fns); return f"{f}(" + ", ".join(iexp(d - 1) for _ in range(k)) + ")"
op = R.choice("+-*/%+-*")
right = iexp(d - 1) if op not in "/%" or R.random() < 0.25 else f"({iexp(d - 1)} % 7 + 8)"
return f"({iexp(d - 1)} {op} {right})"
def bexp(d): # Bool expression
r = R.random()
if d <= 0 or r < 0.5: return f"({iexp(d - 1)} {R.choice(['<', '<=', '>', '>=', '==', '!='])} {iexp(d - 1)})"
if r < 0.6: return f"!{bexp(d - 1)}"
if r < 0.65: return R.choice(["true", "false"])
return f"({bexp(d - 1)} {R.choice(['&&', '||'])} {bexp(d - 1)})"
def block(ind, n, in_fn):
for _ in range(n): stmt(ind, in_fn)
def stmt(ind, in_fn):
r, pad, sc = R.random(), " " * ind, scopes[-1]
vis = {n: m for s in scopes for n, m in s.items() if n[0] != "#"} # ভেতরের নাম বাইরেরটিকে ঢাকে
muts = [n for n, m in vis.items() if m is True]
if r < 0.22:
e = iexp(2); free = [n for n in "abcpxy" if n not in sc and n not in sc.get("#used", ())]
if not free: return lines.append(f"{pad}print({e});")
n, mut = R.choice(free), R.random() < 0.6
sc[n] = mut; lines.append(f"{pad}{'var' if mut else 'let'} {n} = {e};")
elif r < 0.4 and muts:
n = R.choice(muts); use(n); lines.append(f"{pad}{n} = {iexp(2)};")
elif r < 0.55: lines.append(f"{pad}print({iexp(2) if R.random() < 0.7 else bexp(2)});")
elif r < 0.68 and ind < 3:
lines.append(f"{pad}if {bexp(2)} {{"); scopes.append({}); block(ind + 1, R.randint(1, 3), in_fn); scopes.pop()
if R.random() < 0.6:
lines.append(f"{pad}}} else {{"); scopes.append({}); block(ind + 1, R.randint(1, 2), in_fn); scopes.pop()
lines.append(f"{pad}}}")
elif r < 0.78 and ind < 3:
i = f"i{loops[0]}"; loops[0] += 1; sc[i] = False
lines.append(f"{pad}var {i} = 0;"); cond = f"{i} < {R.randint(1, 4)}"
if R.random() < 0.4: cond += f" && {bexp(1)}"
lines.append(f"{pad}while {cond} {{"); scopes.append({}); block(ind + 1, R.randint(1, 3), in_fn); scopes.pop()
lines.append(f"{pad} {i} = {i} + 1;"); lines.append(f"{pad}}}")
elif r < 0.86 and in_fn and ind > 1: lines.append(f"{pad}if {bexp(1)} {{ return {iexp(1)}; }}")
elif r < 0.92 and fns:
f, k = R.choice(fns); lines.append(f"{pad}{f}(" + ", ".join(iexp(1) for _ in range(k)) + ");")
else: lines.append(f"{pad}print({iexp(2)});")
lines += [f"var g0 = {R.randint(-5, 30)};", f"var g1 = {R.randint(-5, 30)};"]
for k in range(R.randint(1, 3)):
params = ["p", "q"][:R.randint(1, 2)]; fname = f"f{k}"
lines.append(f"fn {fname}(" + ", ".join(f"{p}: Int" for p in params) + ") -> Int {")
scopes.append({p: False for p in params}); block(1, R.randint(1, 4), True)
lines.append(f" return {iexp(2)};"); scopes.pop(); lines.append("}"); fns.append((fname, len(params)))
block(0, R.randint(3, 7), False)
return "\n".join(lines) + "\n"# ধাপ ৩: IR interpreter দিয়ে যাচাই — reference-এর `haat.py run`-এর সঙ্গে হুবহু?
import hashlib
from haat_ir import * # compile_ir, run_ir, run_lines, Unsupported
from haat_gen import gen_program # seed থেকে এলোমেলো, কিন্তু সঠিক program
def digest(lines): return hashlib.sha256("\n".join(lines).encode()).hexdigest()[:10]
same = 0
for name in ("bazar", "recursion", "mutual", "shadowing", "shortcircuit", "strings",
"loops", "err_divzero", "counter", "nested"):
src = open(f"examples/{name}.haat", encoding="utf-8").read()
want = open(f"examples/{name}.out", encoding="utf-8").read().split("\n")[:-1]
try: same += run_lines(compile_ir(src)) == want
except Unsupported as e: print(f"{name}: বাদ — {e}")
print(f"উদাহরণ: {same}টি reference-এর .out-এর সঙ্গে হুবহু")
ref = open("random_ref.txt", encoding="utf-8").read().split()
ok = sum(digest(run_lines(compile_ir(gen_program(s)))) == ref[s] for s in range(len(ref)))
print(f"এলোমেলো program: {ok}/{len(ref)} হুবহু")
mod = compile_ir(open("examples/bazar.haat", encoding="utf-8").read())
print("bazar:", run_lines(mod), "· চলা নির্দেশ:", run_ir(mod, out=lambda s: None))
for name, fn in mod.funcs.items():
print(f" {name}: {len(fn.blocks)} block, {sum(map(len, fn.blocks.values()))} নির্দেশ")আসল আউটপুট (ব্রাউজারের Python):
counter: বাদ — 4:16: closures and function values are not in Haat IR v1
nested: বাদ — 3:8: nested functions are not in Haat IR v1
উদাহরণ: 8টি reference-এর .out-এর সঙ্গে হুবহু
এলোমেলো program: 200/200 হুবহু
bazar: ['996', '5000', '3'] · চলা নির্দেশ: 74
<main>: 4 block, 26 নির্দেশ
price: 3 block, 9 নির্দেশ
delivery: 3 block, 7 নির্দেশ
দুটি উদাহরণ বাদ, কারণ closure; বাকি আটটির আউটপুট reference-এর .out-এর সঙ্গে লাইনে লাইনে এক, err_divzero-এর 3:18: runtime error: division by zero-সহ। এলোমেলো ২০০টিও এক। লেখকের lab-এ (CPython 3.14.4) পরীক্ষাটি আরও বড় করে চালানো হয়েছে: প্রথম ৩,০০০টি seed-এর সবগুলো reference-এর check পেরিয়েছে; ২,৬৭৫টি স্বাভাবিকভাবে শেষ হয়, ৩২৫টি division by zero-তে থামে; ২,৯৬৫টিতে অন্তত একটি @ global আছে; আর ৩,০০০টিতেই Haat IR-এর আউটপুট reference-এর run-এর সঙ্গে অক্ষরে অক্ষরে এক (reference-এর vm-ও ৩,০০০টিতে run-এর সমান)। এর বাইরে হাতে লেখা ১১টি কিনারার program: অসীম recursion-এ ১,০০০ গভীরতার সীমায় stack overflow, 'k' is not initialized yet পড়া আর লেখা দুই ক্ষেত্রেই, Unit function, খালি then, return-এর পরের মৃত কোড, t1 নামের variable, INT_MIN-এর wrap; সবগুলো মিলেছে।
একটি সতর্কতা, যা অনুশীলন ২-এ সংখ্যা দিয়ে দেখবেন: এলোমেলো test শক্তিশালী, কিন্তু সর্বশক্তিমান নয়। যে ভুল শুধু বিশেষ গঠনে ধরা পড়ে, তার জন্য বাছাই করা উদাহরণও লাগে।
৯ · Stack code বনাম three-address code, আর বাস্তব compiler-এর IR
একই bazar.haat-এর দুই রূপ পাশাপাশি। Stack code-এর সংখ্যা reference-এর dis থেকে; চলা নির্দেশের সংখ্যা লেখকের lab-এ reference-এর vm.py-র একটি কপিতে একটি গণক বসিয়ে (মূল ফাইল অপরিবর্তিত), আর Haat IR-এর সংখ্যা run_ir-এর ফেরত মান।
| program | stack code: লেখা / চলা | Haat IR: লেখা / চলা |
|---|---|---|
price | 16 / — | 9 / — |
delivery | 8 / — | 7 / — |
| bazar.haat (মোট) | 67 / 120 | 42 / 74 |
| loops.haat | 83 / 214 | 67 / 140 |
| recursion.haat | 58 / 243,298 | 39 / 165,879 |
Three-address code-এ নির্দেশ প্রায় ২০ থেকে ৪০ শতাংশ কম, কারণ local variable পড়তে কোনো নির্দেশ লাগে না আর ফল সরাসরি নামে যায়। কিন্তু এটি সময়ের মাপ নয়: প্রতিটি three-address নির্দেশ বড় (তিনটি নাম), আর এই দুই interpreter-এর নকশাও আলাদা। আসল তুলনা অন্য জায়গায়। Stack code-এ “p - p / 10-এর মাঝের ফল” কোনো নাম পায় না; সেটি শুধু stack-এর একটি অবস্থান। তাই “এই মান কোথায় তৈরি, কোথায় ব্যবহার” প্রশ্নের উত্তর পেতে stack-এর উচ্চতা অনুসরণ করতে হয়। Three-address code-এ প্রতিটি মানের একটি নাম আর একটি সংজ্ঞা-নির্দেশ; বিশ্লেষণ মানে শুধু নাম মেলানো। এজন্যই JVM-এর JIT compiler-গুলো stack bytecode পড়েই প্রথমে নিজের নামওয়ালা IR বানায়।
সত্যিকারের Clang-এর IR
এবার একটি বাস্তব compiler. price-এর C রূপ (long price(long qty, long unit), একই দেহ) PyPI-র ziglang 0.17.1 প্যাকেজের ভেতরের Clang 22.1.8 দিয়ে LLVM IR-এ নামানো হলো, লেখকের lab-এ সত্যিকারের run (-g0 আর -fno-sanitize=undefined, যাতে debug আর UBSan-এর বাড়তি লাইন না আসে):
~/ir $ python -m ziglang cc -O0 -g0 -fno-sanitize=undefined -fno-discard-value-names \
-S -emit-llvm --target=x86_64-linux-gnu price.c -o price_O0.ll
define i64 @price(i64 noundef %qty, i64 noundef %unit) #0 {
entry:
%retval = alloca i64, align 8
%qty.addr = alloca i64, align 8
%unit.addr = alloca i64, align 8
%p = alloca i64, align 8
store i64 %qty, ptr %qty.addr, align 8
store i64 %unit, ptr %unit.addr, align 8
%0 = load i64, ptr %qty.addr, align 8
%1 = load i64, ptr %unit.addr, align 8
%mul = mul nsw i64 %0, %1
store i64 %mul, ptr %p, align 8
%2 = load i64, ptr %p, align 8
%cmp = icmp sge i64 %2, 1000
br i1 %cmp, label %if.then, label %if.end
if.then: ; preds = %entry
%3 = load i64, ptr %p, align 8
%4 = load i64, ptr %p, align 8
%div = sdiv i64 %4, 10
%sub = sub nsw i64 %3, %div
store i64 %sub, ptr %retval, align 8
br label %return
if.end: ; preds = %entry
%5 = load i64, ptr %p, align 8
store i64 %5, ptr %retval, align 8
br label %return
return: ; preds = %if.end, %if.then
%6 = load i64, ptr %retval, align 8
ret i64 %6
}
Haat IR-এর সঙ্গে মিলগুলো চোখে পড়ার মতো: block-এর নাম (entry, if.then), প্রতিটি block-এর শেষে terminator (br, ret), দুই-লক্ষ্যের শর্তসাপেক্ষ br i1 %cmp, label %if.then, label %if.end, আর Clang নিজেই প্রতিটি block-এর predecessor মন্তব্যে লিখে দেয়। পার্থক্যও আছে: -O0-এ প্রতিটি variable memory-তে (alloca, load, store), আর একটি আলাদা return block. -O2-এ একই function:
define range(i64 -9223372036854775808, 9223372036854775708) i64 @price(i64 noundef %qty, i64 noundef %unit) local_unnamed_addr #0 {
entry:
%mul = mul nsw i64 %unit, %qty
%cmp = icmp sgt i64 %mul, 999
br i1 %cmp, label %if.then, label %cleanup
if.then: ; preds = %entry
%div = udiv i64 %mul, 10
%sub = sub nsw i64 %mul, %div
br label %cleanup
cleanup: ; preds = %entry, %if.then
%retval.0 = phi i64 [ %sub, %if.then ], [ %mul, %entry ]
ret i64 %retval.0
}
চারটি block তিনটিতে নেমেছে, memory-র সব কাজ উধাও, আর মিলনের block-এ একটি phi: “if.then থেকে এলে %sub, entry থেকে এলে %mul”. এটিই SSA form, পর্ব ৬৩-এর বিষয়। আরও দুটি জিনিস দেখার মতো, যদিও বিস্তার পর্ব ৬৮-এ: mul nsw-এর nsw বলে signed overflow হবে না ধরে নেওয়া যায় (C-তে signed overflow undefined behavior, Haat-এ wrap, তাই Haat-এর অনুবাদে এই পতাকা চলবে না), আর sdiv হয়েছে udiv: Clang প্রমাণ করেছে যে এই শাখায় %mul ৯৯৯-এর বড়, তাই চিহ্নহীন ভাগ একই ফল দেয়।
আরও গভীরে: GCC-র ভেতরে কয়েক স্তরের IR আছে: ভাষাভেদে আলাদা front end-এর গাছ থেকে GENERIC, তারপর তিন-ঠিকানার GIMPLE (GCC ৪.০ থেকে, “tree SSA” প্রকল্পের অংশ হিসেবে), আর যন্ত্রের কাছাকাছি RTL; বিস্তারিত সময়রেখা উৎসভেদে একটু আলাদা বলা হয়। Java HotSpot-এর C2 compiler Cliff Click-এর ১৯৯০-এর দশকের কাজের “sea of nodes” graph IR ব্যবহার করে, যেখানে নির্দেশের ক্রমও শুধু নির্ভরতার edge. CPython-ও নিজের compiler-এর ভেতরে basic block-এর একটি CFG বানায় (সাম্প্রতিক version-এ Python/flowgraph.c ফাইলে), তারপর bytecode লেখে।
১০ · AI-এর যুগে IR
AI assistant দিয়ে three-address code বা একটি ছোট IR লেখানো সহজ। কিন্তু IR-এর ভুলগুলো চুপচাপ: বেশির ভাগ program ঠিক চলে, ভুল ধরা পড়ে শুধু শর্তের ভেতরে side effect বা শূন্য দিয়ে ভাগের মতো কিনারায়।
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
&&/||-এর দুই দিক আগে হিসাব করে তারপর শাখা নেওয়া (short-circuit হারানো) | ডান দিকে print করা call বা শূন্য দিয়ে ভাগ রেখে test; reference-এর সঙ্গে differential test |
| Block-এর শেষে terminator না রাখা, বা গড়িয়ে পড়াকে edge হিসেবে না গোনা | প্রতিটি block-এর শেষ নির্দেশ যাচাই; block-এর ক্রম উল্টে IR চালানো |
| Shadowing-এ দুটি binding-কে একই নাম দেওয়া | ভেতরের block-এ একই নামের let রেখে test (shadowing.haat) |
Optimization-এর নামে x / 0 ভাঁজ করা বা অব্যবহৃত ভাগ মুছে ফেলা | শূন্য-ভাগের runtime error-সহ program আগে-পরে চালানো; error-এর line:col-ও মেলানো |
| বানানো Clang flag বা LLVM pass-এর নাম, বা অন্য version-এর IR দেখানো | নিজের যন্ত্রে সেই version-এর clang -S -emit-llvm চালানো; --version লিখে রাখা |
| “IR সবসময় দ্রুত” বা “stack code ধীর” ধরনের ঢালাও দাবি | নির্দেশ-গণনা আর সময় আলাদা করা; নিজের মাপ এক যন্ত্রের বলে চিহ্নিত করা |
AI-কে কাজে লাগাতে IR-এর নিয়ম আর যাচাইয়ের উপায় নিজেই বলে দিন:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১UNCOL থেকে LLVM আর WebAssembly: একটি সর্বজনীন IR-এর স্বপ্ন বারবার ফিরে আসে কেন, আর পুরোপুরি সফল হয় না কেন?
১৯৫০-এর দশকের শেষে কম্পিউটারের মডেল দ্রুত বদলাচ্ছিল, আর প্রতিটি নতুন যন্ত্রে প্রতিটি ভাষার compiler নতুন করে লেখা ছিল বিশাল খরচ। ১৯৫৮ সালের দিকে SHARE ব্যবহারকারী-গোষ্ঠীর একটি কমিটি আর Melvin Conway-র মতো লেখকেরা UNCOL নামে একটি সর্বজনীন মধ্যবর্তী ভাষার প্রস্তাব দেন: সব ভাষা UNCOL-এ, UNCOL থেকে সব যন্ত্রে। ধারণাটি সঠিক ছিল, কিন্তু সর্বজনীন রূপটি তৈরি হয়নি। কারণ “সব ভাষার সব অর্থ” ধরতে হলে IR-কে প্রায় সব ভাষার মিলন হতে হয়, আর তখন সেটি আর সরল থাকে না; আবার সরল রাখলে কিছু ভাষার অর্থ হারায়।
LLVM (Lattner আর Adve, কাজ শুরু ২০০০ সালের দিকে, CGO ২০০৪-এর প্রবন্ধ) সমস্যাটি অন্যভাবে ধরে: সর্বজনীন হওয়ার দাবি নেই, আছে একটি ভালো-নির্ধারিত, নিচু স্তরের SSA IR, যেখানে C-ধাঁচের ভাষা সহজে নামে। Clang, Rust, Swift আর আরও অনেক ভাষা এটি ব্যবহার করে, কিন্তু প্রত্যেকে আগে নিজের উঁচু স্তরের IR-এ (যেমন Rust-এর MIR) ভাষার নিজস্ব কাজ সেরে নেয়: borrow check, generics, pattern matching. WebAssembly (২০১৭) আবার বিতরণের জন্য: যন্ত্র-নিরপেক্ষ, যাচাইযোগ্য, নিরাপদ; কিন্তু optimization-এর জন্য বানানো নয়।
MLIR এই শিক্ষাকে কাঠামো বানিয়েছে: একটি IR নয়, IR বানানোর একটি কাঠামো, যেখানে প্রতিটি স্তর বা domain নিজের “dialect” আনে আর dialect থেকে dialect-এ ধাপে ধাপে নামা যায়। Haat-ও একই পথে: AST (উঁচু), stack bytecode (চালানোর জন্য), Haat IR (বিশ্লেষণের জন্য), পরে RISC-V আর Wasm.
মূল উপলব্ধি: m + n-এর লাভ বাস্তব, কিন্তু একটি IR সবার জন্য যথেষ্ট নয়; সফল নকশাগুলো কয়েক স্তরের IR রাখে, প্রতিটি একটি নির্দিষ্ট কাজের জন্য।
প্র ০২Triple জায়গা বাঁচায়, quadruple-এ নাম থাকে। বাস্তব compiler-এর পছন্দ কী, আর LLVM কেন আসলে দুটিরই মিশ্রণ?
পাঠ্যবইয়ের তুলনাটি memory-র হিসাব থেকে আসে। যখন compiler-এর জন্য কয়েক কিলোবাইট memory বড় ব্যাপার ছিল, triple-এর একটি ঘর কম মানে অনেক সাশ্রয়। কিন্তু optimization নির্দেশ সরায়, মুছে, নতুন বসায়; triple-এ ফলের পরিচয় সারির নম্বর, তাই প্রতিটি সরানোয় উল্লেখ ভাঙে। Indirect triple ক্রমের তালিকা আলাদা করে এর সমাধান দেয়; quadruple নাম দিয়ে।
আধুনিক compiler-এ প্রশ্নটি একটু অন্য রূপে আসে। LLVM-এর memory-র ভেতরে প্রতিটি নির্দেশ একটি object, আর একটি নির্দেশের operand হলো অন্য নির্দেশ-object-এর pointer. এটি triple-এর ধারণা: ফলের আলাদা নাম নেই, নির্দেশ নিজেই ফল। কিন্তু সারির নম্বরের বদলে pointer, তাই নির্দেশকে অন্য block-এ সরালেও উল্লেখ ঠিক থাকে, indirect triple-এর সুবিধাটি বিনা খরচে। আর প্রতিটি মানের সব ব্যবহারকারীর একটি তালিকা (use list) রাখা হয়, তাই “এই মান কে কে ব্যবহার করে” প্রশ্নের উত্তর তাৎক্ষণিক। Text-এ %mul-এর মতো নাম শুধু মানুষের পড়ার জন্য।
Haat IR quadruple-ধাঁচের, নাম দিয়ে, কারণ শেখার জন্য নাম পড়া সহজ আর Python dict-এ নাম দিয়ে মান রাখা স্বাভাবিক। দাম আছে: একই temp দুবার লেখা যায় (&&-এর t2), তাই “এই নামের মান কোথা থেকে এসেছে” বলতে dataflow analysis লাগে। SSA (পর্ব ৬৩) এই দাম মেটায়: প্রতিটি নামে একবারই মান বসে, তাই নাম আর সংজ্ঞা আবার এক-এক সম্পর্কে ফেরে, ঠিক triple-এর মতো।
মূল উপলব্ধি: প্রশ্নটি জায়গার নয়, পরিচয়ের: একটি মানকে কীভাবে চেনা হবে, যাতে নির্দেশ সরালে চেনা না ভাঙে; pointer বা SSA নাম দুটিই সেই উত্তর।
প্র ০৩Frances Allen আর control flow analysis: basic block আর CFG কেন optimization-এর মেরুদণ্ড হলো?
প্রথম FORTRAN compiler-এর (IBM, ১৯৫৭) কাজেই program-কে সোজা চলা টুকরোয় ভাগ করে বিশ্লেষণের ধারণা দেখা যায় বলে উল্লেখ পাওয়া যায়; লক্ষ্য ছিল হাতে লেখা assembly-র কাছাকাছি গতি, নইলে বিজ্ঞানীরা FORTRAN নিতেন না। ১৯৬০-এর দশকে IBM-এ Frances Allen আর John Cocke এই কাজকে একটি তত্ত্বে রূপ দেন। Allen-এর ১৯৭০ সালের “Control Flow Analysis” প্রবন্ধ program-কে basic block-এর একটি directed graph হিসেবে দেখায় আর graph-এর গঠন থেকে loop খোঁজার পদ্ধতি দেয় (interval analysis). ১৯৭০-এর দশকের শুরুতে Allen আর Cocke মিলে optimization-এর একটি তালিকা (“A Catalogue of Optimizing Transformations”) প্রকাশ করেন, যার অনেকগুলো আজও প্রতিটি compiler-এ আছে।
কেন CFG এত কেন্দ্রীয়? কারণ প্রায় প্রতিটি optimization একটি প্রশ্ন: “এই জায়গায় পৌঁছানোর সব পথে কী সত্য?” একটি variable-এর মান ধ্রুবক কি না, একটি হিসাব আগে হয়ে গেছে কি না, একটি মান পরে আর লাগবে কি না। “সব পথ” মানে CFG-এর পথ। Block-এর ভেতরে পথ একটিই, তাই উত্তর সহজ (local optimization); block-এর মাঝে graph ধরে তথ্য ছড়াতে হয় (global optimization, পর্ব ৬৪–৬৫)। Loop খুঁজে বের করা আরেক বড় কাজ, কারণ program-এর সময়ের বড় অংশ loop-এ কাটে (পর্ব ৬৬)।
Allen ২০০৬ সালে Turing Award পান, প্রথম নারী হিসেবে, compiler optimization-এর তত্ত্ব আর প্রয়োগে অবদানের জন্য। তাঁর ধারণাগুলো এখন এতই স্বাভাবিক যে পাঠ্যবই এগুলোকে প্রায় স্বতঃসিদ্ধ ধরে নেয়। এই পর্বের build_cfg সেই তত্ত্বের প্রথম ধাপ।
মূল উপলব্ধি: CFG “সব পথে কী সত্য” প্রশ্নটিকে একটি graph-এর প্রশ্ন বানায়, আর graph-এর প্রশ্নের জন্য অ্যালগরিদম আছে; এজন্যই এটি optimization-এর মেরুদণ্ড।
প্র ০৪JVM আর WebAssembly stack-ভিত্তিক bytecode বেছে নিল, অথচ তাদের JIT compiler ভেতরে আবার নামওয়ালা IR বানায়। এই দ্বৈততা কেন?
Bytecode-এর কাজ বিতরণ: নেটওয়ার্কে পাঠানো, অচেনা যন্ত্রে লোড করা, চালানোর আগে যাচাই করা। এর জন্য ছোট আকার, register-সংখ্যার ওপর নির্ভর না করা আর সহজ verifier দরকার; stack code তিনটিই দেয় (পর্ব ৫৮-এর আলোচনা)। WebAssembly-র নকশাও এমন যে validation এক pass-এ শেষ হয় আর browser দ্রুত machine code বানাতে পারে।
কিন্তু optimization-এর প্রশ্নগুলো, যেমন “এই মান কোথায় তৈরি, কোথায় ব্যবহার”, stack code-এ সরাসরি পড়া যায় না, কারণ মাঝের মানের কোনো নাম নেই। তাই JIT compiler প্রথমে bytecode-কে symbolic execution-এর মতো করে চালায়: stack-এর প্রতিটি ঘরকে একটি নাম দেয়, আর এভাবে নামওয়ালা IR বানায়, সাধারণত সরাসরি SSA রূপে। HotSpot-এর C2 Cliff Click-এর “sea of nodes” graph IR ব্যবহার করে; V8-এর TurboFan-ও দীর্ঘদিন এমন একটি graph IR ব্যবহার করেছে, আর সাম্প্রতিক বছরগুলোতে V8 দল প্রচলিত CFG-ভিত্তিক IR-এর দিকে ফিরছে বলে জানিয়েছে (বিস্তারিত সময় আর অবস্থা পরিবর্তনশীল)।
এই দ্বৈততা একটি স্থায়ী নকশা-নীতি দেখায়: বিতরণের ফরম্যাট আর optimization-এর IR আলাদা প্রয়োজন মেটায়। Android-এর ইতিহাসও তাই: Dalvik register-ভিত্তিক bytecode বেছেছিল, পরে ART আগেভাগে machine code-এ compile করে, ভেতরে নিজের IR দিয়ে। Haat-এও একই ভাগ: পর্ব ৫৮–৫৯-এর bytecode চালানোর জন্য, এই মডিউলের Haat IR বিশ্লেষণের জন্য, আর দুটিই একই AST থেকে আসে।
মূল উপলব্ধি: ভালো বিতরণ-ফরম্যাট আর ভালো optimization-IR আলাদা জিনিস; বাস্তব system দুটিই রাখে আর একটি থেকে অন্যটিতে অনুবাদ করে।
প্র ০৫Haat IR v1-এ closure নেই। বড় ভাষা closure, exception বা generics IR-এ কীভাবে আনে, আর কোন স্তরে?
Haat IR-এর call শুধু নাম-জানা top-level function ডাকে। Closure আনতে হলে IR-কে জানতে হবে function একটি মান, যার সঙ্গে একটি environment যায়। প্রচলিত সমাধান closure conversion: প্রতিটি lambda একটি top-level function হয়, যার একটি বাড়তি parameter হলো environment-এর record, আর lambda তৈরির জায়গায় সেই record আর function-এর ঠিকানা জোড়া হয়। তারপর IR-এ শুধু দুটি নতুন নির্দেশ লাগে: record বানানো আর “মান হিসেবে ধরা function ডাকা”। পর্ব ৫৭-এর cell আর পর্ব ৫৮-এর MAKE_CLOSURE এই ধারণারই runtime রূপ।
বড় ভাষা এমন কাজ কয়েক স্তরে ভাগ করে। Rust-এর compiler-এ HIR (desugar করা AST), তারপর MIR: একটি CFG-ভিত্তিক IR, যেখানে borrow checker চলে, আর যার প্রস্তাব ২০১৫ সালের একটি RFC-তে এসেছিল; তারপর LLVM IR. GHC (Haskell) চলে Core (একটি ছোট typed lambda calculus) → STG → Cmm-এর পথে, যেখানে lazy evaluation আর closure ধাপে ধাপে নিচু হয়। Exception-ও এভাবে নামে: LLVM IR-এ invoke নির্দেশের দুটি লক্ষ্য থাকে, স্বাভাবিক ফেরা আর exception-এর পথ; CFG-তে তাই exception-এর edge-ও থাকে।
নকশার নীতিটি পরিষ্কার: যে তথ্য একটি বিশ্লেষণের লাগে, তা সেই স্তরে বেঁচে থাকতে হবে যেখানে বিশ্লেষণটি চলে। Borrow check-এর জন্য lifetime-এর তথ্য লাগে, তাই সেটি LLVM IR-এ নয়, MIR-এ। Haat IR v1 ইচ্ছা করে ছোট: ছয় পর্বের optimization শেখাতে first-order কোডই যথেষ্ট, আর প্রতিটি নিয়ম স্পষ্ট থাকে।
মূল উপলব্ধি: জটিল বৈশিষ্ট্য IR-এ আসে উঁচু স্তরে আগে সরল রূপে নামিয়ে; কোন স্তরে কোন তথ্য বাঁচবে, তা ঠিক করে কোন বিশ্লেষণ কোথায় চলবে।
অনুশীলন
প্রথমে নিজে হিসাব করুন বা লিখুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর সত্যিকারের run দিয়ে যাচাই করা।
-
নকশা ও বাস্তবায়ন — IR-এর text থেকে আবার IR:
show_irIR-কে text বানায়। উল্টো কাজের একটিparse_ir(text)লিখুন, যা CFG-রূপের text থেকেIRFunctionফেরত দেয়, যাতে পরের পর্বে IR হাতে লিখে পরীক্ষা করা যায়। দেখান যেshow_ir(parse_ir(show_ir(f))) == show_ir(f). Text-এ কোন তথ্য হারায়, আর তার ফল কী?def parse_ir(text): # show_ir-এর উল্টো: text -> IRFunction (pos হারায়) lines = text.strip("\n").split("\n") m = re.fullmatch(r"fn (\S+)\((.*)\):", lines[0]) fn, cur = IRFunction(m[1], m[2].split(", ") if m[2] else []), None for line in lines[1:]: if not line.startswith(" "): cur = fn.blocks[line[:-1]] = []; continue w = line.split() if w[0] in ("jump", "branch", "print", "return"): ins = Ins(w[0], args=w[1:2] if w[0] != "jump" else [], targets=w[2:] if w[0] == "branch" else w[1:2] if w[0] == "jump" else []) elif w[2] == "const": v = line.split(" = const ", 1)[1] ins = Ins("const", w[0], sym=None if v == "()" else v == "true" if v in ("true", "false") else ast.literal_eval(v)) elif w[2] == "call": c = re.fullmatch(r"(\S+) = call (\S+)\((.*)\)", line.strip()) ins = Ins("call", c[1], c[3].split(", ") if c[3] else [], c[2]) elif len(w) == 3: ins = Ins("copy", w[0], [w[2]]) elif len(w) == 4: ins = Ins("un", w[0], [w[3]], w[2]) else: ins = Ins("bin", w[0], [w[2], w[4]], w[3]) cur.append(ins) return fnলেখকের lab-এ সত্যিকারের run: এলোমেলো ৩,০০০টি program-এর ৯,০০১টি function-এর সবগুলোতে round trip-এর text হুবহু এক, আর আটটি উদাহরণেও। কিন্তু চালালে ৩,০০০টির মধ্যে ২,৬৭৫টি একই আউটপুট দেয়, আর ৩২৫টিতে শুধু শেষ লাইনে পার্থক্য:
0:0: runtime error: division by zero, যেখানে আসলটি9:22: …. কারণ text-এposছাপা হয় না। হারায় দুটি জিনিস: runtime error-এর অবস্থান, আর@x = t-এর সিদ্ধান্ত ১৮-এর পরীক্ষা (text-এ লেখা আর সংজ্ঞা আলাদা করা যায় না)। বাস্তব IR এর সমাধান করে অবস্থান IR-এর অংশ বানিয়ে: LLVM IR-এর!dbgmetadata ঠিক এই কাজ করে। Haat-এর জন্য উপায়: text-এ ঐচ্ছিক একটি লেজ, যেমনt3 = p / t2 @4:33. -
ভুল খুঁজুন: একজন সহকর্মী
&&আর||-এর lowering “সরল” করলেন: আগে দুই দিকের কোড লেখেন (a = E(left); b = E(right)), তারপরt = a; branch t L1 L2; label L1; t = b; label L2. ফলের মান কি কখনো ভুল হয়? Reference examples-এরshortcircuit.haatআর ৩,০০০টি এলোমেলো program-এর differential test কী বলবে?শেষ মান ঠিকই আসে, কারণ শাখা এখনো বাঁ দিক দেখে বাছাই করে। ভুলটি অন্য জায়গায়: ডান দিক এখন সবসময় চলে, তাই short-circuit হারিয়েছে, আর ডান দিকের side effect ও runtime error সবসময় ঘটে। সত্যিকারের run (লেখকের lab-এ ভুল lowering-টি একটি subclass-এ বসিয়ে):
shortcircuit.haat-এ বাড়তি দুটি লাইন ছাপে,yes bআরno d, আরstock != 0 && 100 / stock > 2-এ থেমে যায়8:25: runtime error: division by zeroদিয়ে, যেখানে reference ছাপেfalseআর চলতে থাকে। কিন্তু ৩,০০০টি এলোমেলো program-এ অমিল শূন্য: generator-এর&&-এর ডান দিকে কখনো print-করা call বা শূন্য-ভাজক পড়েনি। শিক্ষা দুটি। এক, সংখ্যা বড় হলেই test যথেষ্ট নয়; generator-কে জেনেশুনে side effect আর error-এর কিনারায় পাঠাতে হয় (যেমন ডান দিকে ইচ্ছা করেprintকরা function). দুই, ভাষার প্রতিটি নিয়মের জন্য একটি করে বাছাই করা উদাহরণ রাখুন; reference-এরshortcircuit.haatঠিক এই ভুল ধরার জন্যই আছে। -
হিসাব ও trace: নিচের function-এর জন্য (ক) রৈখিক Haat IR লিখুন; (খ) leader আর basic block বের করুন, প্রতিটি block-এর successor আর predecessor-সহ; (গ) program কী ছাপে?
fn bags(items: Int) -> Int { var n = 0; var left = items; while left > 0 { left = left - 6; n = n + 1; } if n > 3 { n = n - 1; } return n; } print(bags(20)); print(bags(6));fn bags(items): B0: n = const 0 left = items jump B1 B1: t1 = const 0 t2 = left > t1 branch t2 B2 B3 B2: t3 = const 6 left = left - t3 t4 = const 1 n = n + t4 jump B1 B3: t5 = const 3 t6 = n > t5 branch t6 B4 B5 B4: t7 = const 1 n = n - t7 jump B5 B5: return n(ক) ও (খ) এটি
haat_ir.py-র সত্যিকারের আউটপুট, CFG রূপে; রৈখিক রূপে একই নির্দেশ, সঙ্গেlabel L1–L5. Leader:n = const 0(নিয়ম ১), loop-এর শর্তের শুরুt1 = const 0(L1, নিয়ম ২), loop-এর শরীর (L2, নিয়ম ২ ও ৩), loop-এর পরেরt5 = const 3(L3, নিয়ম ২ ও ৩), then-শাখা (L4) আরreturn n(L5). Edge: B0→B1, B1→B2, B1→B3, B2→B1 (back edge), B3→B4, B3→B5, B4→B5. Predecessor: B1 ← B0, B2; B5 ← B3, B4; বাকিগুলোর একটি করে। B4-এর শেষেরjump B5যোগ করা হয়েছে, কারণ then-শাখা গড়িয়ে পড়ে। (গ) bags(20): left 20 → 14 → 8 → 2 → −4, n = 4; 4 > 3, তাই 3. bags(6): left 6 → 0, n = 1. ছাপে3আর1; reference-এরrunআরrun_irদুটিই তাই। -
প্রমাণ — expression-এর lowering সঠিক: নিয়ম ৬২.১-এর E-এর জন্য দাবি: যেকোনো env ρ-তে E(e)-র কোড চালানোর পরে (runtime error না হলে) ফেরত নাম a-তে থাকে e-এর মান (পর্ব ৪০-এর big-step অর্থে ρ ⊢ e ⇓ v), আর কোডটি শুধু নতুন temp-এ লেখে। প্রমাণের রূপরেখা দিন, তারপর বলুন
into-এর “শুধু এইমাত্র তৈরি temp” শর্ত কেন লাগে।প্রমাণের রূপরেখা, e-এর গঠনের ওপর induction:
- ধ্রুবক n: কোড
t = const n; t নতুন, তাতে n. Local x: কোনো কোড নেই, a = x, আর ρ(x) = v. Global x:t = @x, t নতুন, তাতে memory-র মান। - e1 ⊕ e2: অনুমান অনুযায়ী E(e1)-এর পরে a-তে v1, আর কোডটি শুধু নতুন temp-এ লিখেছে। E(e2)-ও শুধু নতুন temp-এ লেখে, যারা a থেকে আলাদা (temp-এর নম্বর শুধু বাড়ে, আর a একটি variable হলে temp তার নাম পেতে পারে না), তাই a-র মান টিকে থাকে আর b-তে v2. শেষ নির্দেশ
t = a ⊕ b, t নতুন, তাতে v1 ⊕ v2; সিদ্ধান্ত ১২-এর বাঁ-আগে ক্রমও রক্ষা পায়। - call: argument-এর জন্য একই যুক্তি পরপর;
callনতুন frame-এ চলে, তাই caller-এর নামে লেখে না, শুধু ফলটি নতুন t-তে। ∎
into-এর শর্ত: dst বদলানো মানে শেষ নির্দেশের ফল এখন x-এ যায়, a-তে নয়। এটি নিরাপদ যদি a আর কোথাও পড়া না হয়। প্রমাণের দ্বিতীয় অংশ বলে E-এর ফেরত temp শুধু তার একমাত্র ব্যবহারকারী পড়ে, তাই এইমাত্র তৈরি temp-এর ক্ষেত্রে শর্তটি সত্য। কিন্তু a যদি একটি variable হয়, যেমনlet y = x;-এ a = x, তাহলে “শেষ নির্দেশ” হয়তো x-এর আগের সংজ্ঞা (x = …); তার dst বদলালে x আর কখনো মান পায় না। আর&&-এর ফল-temp দুবার লেখা হয়, তাই তার শেষ সংজ্ঞাটি একটি label-এর পরে, যাmade-এর পরীক্ষা ধরে ফেলে। - ধ্রুবক n: কোড
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি Haat program থেকে যাচাই-করা CFG পর্যন্ত ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Source parse করে AST
- Expression post-order-এ temp-এ, statement label আর লাফে: রৈখিক IR
- Leader-এর তিন নিয়মে block-এর শুরু খোঁজা
- Label মুছে লক্ষ্যকে block-এর নাম দেওয়া, গড়িয়ে পড়ায় স্পষ্ট jump
- Terminator থেকে successor আর predecessor
- IR interpreter-এ চালিয়ে reference-এর আউটপুটের সঙ্গে মেলানো
একটি compiler পরিবারে ৪টি source ভাষা আর ৫টি লক্ষ্য-যন্ত্র। একটি সাধারণ IR থাকলে কয়টি অনুবাদ-অংশ (front end আর back end মিলে) লাগে?
- 20
- 5
- 9
- 10
নিচের রৈখিক কোডে কোন নির্দেশগুলো leader?0: i = const 0 · 1: label L1 · 2: t1 = i < n · 3: branch t1 L2 L3 · 4: label L2 · 5: i = i + t2 · 6: jump L1 · 7: label L3 · 8: return i
- শুধু 0
- 0, 2, 5, 8
- 0, 3, 6
- 1, 4, 7
Three-address code-এর কোন রূপে একটি নির্দেশ সরালে অন্য নির্দেশের উল্লেখ বদলাতে হয়?
- Quadruple
- Indirect triple
- SSA form
- Triple
Haat-এ শূন্য দিয়ে ভাগ একটি runtime error. একটি optimizer IR-এ t2 = const 0 আর তারপর t3 = x / t2 দেখল, আর t3 কোথাও ব্যবহার হয় না। নির্দেশটির কী করা উচিত?
- যেমন আছে রেখে দেওয়া
- মুছে ফেলা, কারণ ফল অব্যবহৃত
- t3 = const 0-এ ভাঁজ করা
- function-এর শেষে সরিয়ে নেওয়া
Haat IR-এ a && b কীভাবে নামে?
- একটি নির্দেশ: t = a && b
- দুই দিক হিসাব করে, তারপর একটি branch
- বাঁ দিক t-তে, branch t, শুধু সত্য হলে ডান দিক t-তে
- একটি সাহায্যকারী function-এর call দিয়ে
একটি CFG-তে block B-এর শেষ নির্দেশ branch c B4 B7, আর B4 ও B7 দুটিতেই শুধু B থেকে আসা যায়। কোন কথাটি সঠিক?
- B-এর successor একটি
- B-এর successor B4 আর B7, আর B4-এর একমাত্র predecessor B
- B একটি loop-এর শর্ত, তাই back edge আছে
- B4 আর B7 পৌঁছানো যায় না
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- IR = মাঝের ভাষা: m × n থেকে m + n, optimization একবার; বড় compiler কয়েক স্তরের IR রাখে।
- Three-address code: প্রতি নির্দেশে একটি operator, মাঝের ফল নামওয়ালা temp-এ; quadruple-এ নাম, triple-এ সারির নম্বর, indirect triple-এ আলাদা ক্রমের তালিকা।
- Lowering: expression post-order-এ,
&&/||আর if/while শাখায়; Haat IR-এ operand শুধু নাম, global@x, shadowing-এx.1. - Basic block আর CFG: leader-এর তিন নিয়ম; প্রতিটি block terminator-এ শেষ; edge আসে terminator থেকে, back edge মানে loop.
- চালিয়ে যাচাই: IR interpreter আর differential test; শূন্য দিয়ে ভাগের error program-এর অর্থের অংশ, কোনো pass তা মুছতে পারে না।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৬৩ · SSA form — phi function আর dominatorপরবর্তী পর্বএই CFG-কে SSA রূপে আনা।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ৫৮ · Bytecode নকশাএই কোর্সেএকই Haat program-এর stack code.
- DFS — গ্রাফের গভীরে আগেপাশের ট্র্যাকCFG-তে back edge আর পৌঁছানোর হিসাবের ভিত্তি।
- গণনার তত্ত্ব · পর্ব ৭৮পাশের ট্র্যাককেন program analysis সবসময় আনুমানিক।
- C থেকে assemblyপাশের ট্র্যাকIR-এর পরের ধাপ: সত্যিকারের যন্ত্রের নির্দেশ।