এই পর্বে যা শিখবেন
- Call graph বানানো, Tarjan-এর অ্যালগরিদমে SCC আর recursion চেনা, bottom-up ক্রম
- Haat IR-এ একটি inliner লেখা: নাম বদল, একাধিক return, continuation block আর error-এর অবস্থান
- কখন inline করবেন: লাভ, code growth, আকারের সীমা; Clang-এর
-Rpass=inlineremark পড়া - Interprocedural constant propagation, আর whole-program বনাম আলাদা compile
- Tail call, devirtualization আর escape analysis-এর সঙ্গে inlining-এর সম্পর্ক; differential test আর জেনেশুনে বসানো ভুল
১ · Function-এর দেয়াল — interprocedural optimization কেন
বাজারঘরের ক্যাশিয়ার প্রতিটি অর্ডারের দাম জানতে গুদামঘরে ফোন করেন, আর সেখানে একজন খাতা খুলে হিসাব করে বলেন। দামের নিয়মটি (“১,০০০ টাকা বা বেশি হলে ১০% ছাড়”) কাউন্টারে সেঁটে দিলে ফোনের খরচ বাঁচে। বড় লাভ পরে: নিয়মটি চোখের সামনে থাকায় ক্যাশিয়ার দেখেন, “২টি, প্রতিটি ৫২০ টাকা” মানে সবসময় ৯৩৬, হিসাবই লাগে না। প্রথমটি ডাকার খরচ বাঁচানো; দ্বিতীয়টি ডাকার জায়গার তথ্য দিয়ে নতুন করে optimize করা। Inlining-এর আসল শক্তি এই দ্বিতীয়টিতে।
পর্ব ৬৫-এর শেষে একটি সীমা দেখা গিয়েছিল। bazar.haat-এর <main>-এ price(2, 520) দুবার ডাকা হয়, কিন্তু CSE call মেলায় না, কারণ optimizer জানে না price কিছু ছাপে কি না বা কোনো global বদলায় কি না। ফলে পুরো pipeline-এর পরেও চলা নির্দেশ ৭৪ থেকে মাত্র ৭২. প্রতিটি function আলাদা দেখলে এর বেশি সম্ভব নয়। একাধিক function একসঙ্গে দেখে যে optimization, তাকে বলে interprocedural optimization (IPO). দুটি বড় পথ:
- Inlining: call-এর জায়গায় callee-র দেহের একটি কপি বসানো। তারপর পর্ব ৬৫-এর সাধারণ pass-গুলোই বড় function-টিতে কাজ করে, এখন argument-এর ধ্রুবক দেখতে পেয়ে।
- Function না জুড়ে তথ্য পার করা: যেমন interprocedural constant propagation (অংশ ৬): “এই parameter প্রতিটি call-এ 2 পায়”, বা “এই function সবসময় 936 ফেরত দেয়”।
এই পর্ব পর্ব ৬২-এর Haat IR-এর ওপর কাজ করে। haat_front.py, haat_ir.py আর haat_gen.py পর্ব ৬২-এর, haat_dfa.py পর্ব ৬৪-এর, haat_opt.py পর্ব ৬৫-এর, সব হুবহু। নতুন সব কোড একটি নতুন ফাইল haat_inline.py-তে। একটি সুবিধা আগে থেকেই আছে: Haat IR v1-এ closure বা function-কে মান হিসেবে ব্যবহার নেই (সেসব program Unsupported), তাই প্রতিটি call একটি জানা top-level function-এর সরাসরি call. কে কাকে ডাকে, তা নিখুঁত জানা।
সঠিকতার চুক্তি পর্ব ৬৫-এর সংজ্ঞা ৬৫.১-এর মতোই: ছাপা লাইন, runtime error-এর বার্তা আর line:col, আর program থামে কি না, সব হুবহু থাকবে। তবে interprocedural কাজে একটি নতুন প্রশ্ন ওঠে। Haat-এ ১,০০০টির বেশি nested call একটি নির্ধারিত runtime error stack overflow (সিদ্ধান্ত ২৬)। Inlining একটি call মুছে দেয়, তাই stack-এর গভীরতা বদলায়। এটি কি আচরণ বদলায়? অংশ ৫-এ এর উত্তর একটি প্রমাণসহ নিয়ম।
২ · Call graph আর SCC — কে কাকে ডাকে, কে নিজেকে
Call graph একটি directed graph: প্রতিটি function একটি node, আর f-এর ভেতরে কোথাও g ডাকা হলে f → g একটি edge. যে নির্দিষ্ট জায়গায় ডাকা হয়, তা একটি call site; একই edge-এর পেছনে অনেক call site থাকতে পারে, আর inline করার সিদ্ধান্ত প্রতিটি call site-এর জন্য আলাদা। এই পর্বের দ্বিতীয় উদাহরণে তিন রকম function আছে: সাধারণ, নিজেকে ডাকা, আর একে অপরকে ডাকা।
// বাজারঘর: কোন function কাকে ডাকে
fn price(qty: Int, unit: Int) -> Int {
let p = qty * unit;
if p >= 1000 { return p - p / 10; }
return p;
}
fn bill(qty: Int, unit: Int) -> Int {
return price(qty, unit) + 60;
}
fn reward(taka: Int) -> Int {
if taka < 100 { return 0; }
return 1 + reward(taka - 100);
}
fn even(n: Int) -> Bool {
if n == 0 { return true; }
return odd(n - 1);
}
fn odd(n: Int) -> Bool {
if n == 0 { return false; }
return even(n - 1);
}
let b = bill(2, 520);
print(b);
print(reward(b));
print(even(reward(b)));Reference implementation (python -B haat.py run shop.haat) ছাপে 996, 9, false. call_graph(mod) প্রতিটি function-এর IR-এর call নির্দেশ গুনে graph বানায়: <main> → bill, reward, even; bill → price; reward → reward; even → odd; odd → even. Function pointer, virtual method বা closure থাকলে call site-এর লক্ষ্য সবসময় জানা যায় না, তখন call graph শুধু একটি অনুমান (অংশ ৭)।
Recursion মানে call graph-এ একটি cycle, আর even/odd-এর মতো mutual recursion মানে একাধিক function-এর cycle. পুরো cycle-গুলো ধরার সঠিক কাঠামো strongly connected component (SCC): এমন সবচেয়ে বড় দল, যার যেকোনো দুটি function একে অপরের কাছে পৌঁছায়। SCC-র তত্ত্ব আর দুটি অ্যালগরিদম DSA কোর্সের পর্ব ৪৬-এ আছে; এখানে শুধু Robert Tarjan-এর ১৯৭২ সালের অ্যালগরিদমটি কাজে লাগানো হলো।
- DFS-এ প্রতিটি function প্রথম দেখার সময় একটি
index(০, ১, ২ …) পায়;lowশুরুতে তার সমান, আর function-টি একটি stack-এ ওঠে। - প্রতিটি callee w: এখনো না দেখা হলে আগে তাকে ঘুরে আসুন, তারপর
low[v] = min(low[v], low[w]); w এখনো stack-এ থাকলে (একটি পেছনের edge)low[v] = min(low[v], index[w]). - v-এর সব callee শেষে
low[v] == index[v]হলে v একটি SCC-র মূল: stack থেকে v পর্যন্ত সবাই একটি দল। - SCC যে ক্রমে বেরোয়, তাতে callee-র দল সবসময় caller-এর দলের আগে: এটিই bottom-up ক্রম। একটি দল recursive, যদি তাতে একাধিক function থাকে, বা একমাত্র function-টি নিজেকে ডাকে।
def sccs(g, trace=None): # Tarjan (১৯৭২): একটি DFS-এ SCC; callee-র SCC আগে বেরোয় (bottom-up)
index, low, stack, out = {}, {}, [], []
def visit(v):
index[v] = low[v] = len(index); stack.append(v)
for w in g[v]:
if w not in index: visit(w); low[v] = min(low[v], low[w])
elif w in stack: low[v] = min(low[v], index[w]) # stack-এ থাকা পূর্বসূরিতে ফেরা edge
if trace is not None: trace.append((v, index[v], low[v], list(stack)))
if low[v] == index[v]: # v এই SCC-র মূল: stack থেকে v পর্যন্ত সবাই এক দল
k = stack.index(v); out.append(stack[k:]); del stack[k:]
for v in g:
if v not in index: visit(v)
return out
def recursive(g): # cycle-এ থাকা function: SCC-তে একাধিক, বা নিজেকেই ডাকে
return {f for comp in sccs(g) for f in comp if len(comp) > 1 or f in g[f]}ছবি ৬৭.১ — shop.haat-এর call graph, SCC আর inline-এর সিদ্ধান্ত
সবুজ edge inline হয়েছে; লাল ড্যাশ edge recursive SCC-তে যায় বলে হয়নি
1main → bill reward even2bill → price3price →4reward → reward5even → odd6odd → even
| index/low | |
| stack | |
| SCC |
- DFS শুরু.
<main>(এখানে সংক্ষেপে main) index 0 পায়, তার প্রথম callee bill index 1, bill-এর callee price index 2. তিনজনই stack-এ। - price. কোনো callee নেই, তাই low = index = 2: price একা একটি SCC, stack থেকে নামে। নিজেকে ডাকে না, তাই recursive নয়।
- bill. low 1-ই থাকে (price-এর low 2 বড়): bill-ও একা একটি SCC.
- reward. index 3; একমাত্র callee reward নিজেই, যে এখনো stack-এ, তাই low = min(3, 3) = 3. একা একটি SCC, কিন্তু নিজেকে ডাকে বলে recursive.
- even আর odd. even index 4, odd index 5; odd-এর callee even এখনো stack-এ, তাই odd-এর low = 4 ≠ 5: odd এখনো দল বানায় না।
- even-এ ফেরা. even-এর low 4 = index: stack থেকে even পর্যন্ত, অর্থাৎ even আর odd, একটি SCC. দুজন বলে recursive.
- main আর সিদ্ধান্ত. শেষে {main}. Bottom-up ক্রম price, bill, reward, {even, odd}, main. bill → price আর main → bill inline হয়; main → reward আর main → even হয় না, কারণ callee recursive SCC-তে।
SCC দুটি প্রশ্নের উত্তর দেয়। কোন call inline করা যাবে না: recursive function inline করলে দেহে আবার একই call, শেষ নেই। আর কোন ক্রমে: bottom-up-এ price আগে, তাই bill-কে <main>-এ বসানোর সময় তার ভেতরে price আগেই বসানো, আর bill-এর আকার চূড়ান্ত। LLVM-এর inliner-ও SCC ধরে bottom-up চলে বলে তার নথিতে বর্ণনা আছে। নিচের JS ব্লকে নিজের call graph লিখে দেখুন।
// call graph থেকে SCC (Tarjan), recursion আর কোন call inline-যোগ্য; নিজের তালিকা বসিয়ে আবার চালান
const CALLS = `<main> -> bill reward even
bill -> price
price ->
reward -> reward
even -> odd
odd -> even`;
const g = {};
for (const line of CALLS.split("\n")) {
const [f, rest] = line.split("->").map(s => s.trim());
g[f] = rest ? rest.split(/\s+/) : [];
}
const index = {}, low = {}, stack = [], sccs = [];
function visit(v) { // Tarjan: একটি DFS, index আর low
index[v] = low[v] = Object.keys(index).length; stack.push(v);
for (const w of g[v] || []) {
if (!(w in index)) { visit(w); low[v] = Math.min(low[v], low[w]); }
else if (stack.includes(w)) low[v] = Math.min(low[v], index[w]);
}
console.log(`${v.padEnd(7)} index ${index[v]} · low ${low[v]} · stack [${stack.join(" ")}]`);
if (low[v] === index[v]) sccs.push(stack.splice(stack.indexOf(v)));
}
Object.keys(g).forEach(v => { if (!(v in index)) visit(v); });
const rec = new Set(sccs.flatMap(c => (c.length > 1 || (g[c[0]] || []).includes(c[0])) ? c : []));
const reach = start => { // start থেকে পৌঁছানো যায় এমন সব function
const seen = new Set(start), todo = [...start];
while (todo.length) for (const w of g[todo.pop()] || []) if (!seen.has(w)) { seen.add(w); todo.push(w); }
return seen; };
const deep = reach([...rec]); // recursion যাদের ডাকতে পারে
console.log("SCC, bottom-up:", sccs.map(c => "{" + c.join(", ") + "}").join(" "));
console.log("recursive:", [...rec].join(", ") || "কেউ নয়");
for (const f in g) for (const c of g[f]) {
const why = rec.has(c) ? "না, recursive" : (deep.has(f) || [...reach([c])].some(x => rec.has(x))) ? "না, depth নিয়ম" : "হ্যাঁ";
console.log(`${f} → ${c}: inline? ${why}`);
}আসল আউটপুট (ব্রাউজারের JavaScript):
price index 2 · low 2 · stack [<main> bill price]
bill index 1 · low 1 · stack [<main> bill]
reward index 3 · low 3 · stack [<main> reward]
odd index 5 · low 4 · stack [<main> even odd]
even index 4 · low 4 · stack [<main> even odd]
<main> index 0 · low 0 · stack [<main>]
SCC, bottom-up: {price} {bill} {reward} {even, odd} {<main>}
recursive: reward, even, odd
<main> → bill: inline? হ্যাঁ
<main> → reward: inline? না, recursive
<main> → even: inline? না, recursive
bill → price: inline? হ্যাঁ
reward → reward: inline? না, recursive
even → odd: inline? না, recursive
odd → even: inline? না, recursive
প্রথম ছয় লাইন প্রতিটি function শেষ হওয়ার মুহূর্ত, stepper-এর সংখ্যার সঙ্গে হুবহু। শেষের তালিকা প্রতিটি edge-এর সিদ্ধান্ত; “depth নিয়ম” অংশ ৫-এ। CALLS-এ price -> bill যোগ করে আবার চালান: bill আর price তখন একটি SCC, আর দুটি call-ই বাতিল হয়।
৩ · Inlining-এর কারিগরি — নাম বদল, একাধিক return আর continuation
Haat IR-এ একটি call মানে নতুন activation record: run_ir callee-র জন্য নিজের নামের অভিধান (env)-সহ একটি frame খোলে। Inline করলে সেই frame থাকে না, callee-র নাম caller-এর env-এ বাস করে। তাই প্রথম কাজ নাম আলাদা রাখা, যা lambda calculus-এর α-renaming-এর মতোই (পর্ব ৪৩); আসলে inlining হলো একটি β-reduction: (λx. দেহ) a → দেহ, যেখানে x-এর জায়গায় a.
inline_site)
- ভাগ: block b-এর i-তম নির্দেশ
d = call f(a1, …). তার আগের অংশ b-তে থাকে; পরের অংশ একটি নতুন continuation block-এ যায়। - নাম বদল: callee-র temp tk হয় ttop+k (top = caller-এর সবচেয়ে বড় temp নম্বর); variable x হয়
f1.x(একই caller-এ f-এর প্রথম কপি); block-গুলো নতুন নম্বর পায়;@globalঅপরিবর্তিত, কারণ সেটি সত্যিই ভাগ করা। - Parameter: b-এর শেষে প্রতিটি parameter-এর জন্য
f1.p = a, তারপর callee-র কপির entry-তেjump. - Return: কপির প্রতিটি
return vহয়d = v'আর continuation-এjump. যত return, তত jump; Haat IR SSA-তে নেই বলে মিলনের জায়গায় phi লাগে না। - অবস্থান: প্রতিটি নির্দেশ তার
pos(line, col) নিয়ে কপি হয়, তাই callee-র ভেতরের ভাগের error একইline:colদেয়। মুছে যায় শুধুcall-এর নিজেরpos, যা কেবলstack overflow-এর জন্য লাগত।
def inline_site(fn, b, i, callee, tag, rename=True): # fn-এর block b-র i-তম নির্দেশ (call) -> callee-র দেহ
call, top = fn.blocks[b][i], top_temp(fn)
nb = max(int(x[1:]) for x in fn.blocks) + 1
def r(x): # callee-র নাম -> fn-এ নতুন নাম; @global একই থাকে
if x[0] == "@" or not rename: return x
return f"t{top + int(x[1:])}" if is_temp(x) else f"{tag}.{x}" # t3 -> t(top+3), p -> price1.p
blk = {c: f"B{nb + k}" for k, c in enumerate(callee.blocks)} # callee-র block-এর নতুন নাম
cont = f"B{nb + len(callee.blocks)}" # call-এর পরের অংশ: continuation block
copy = {}
for c, body in callee.blocks.items():
out = []
for ins in body:
if ins.kind == "return": # প্রতিটি return: ফল call-এর dst-এ, তারপর continuation-এ লাফ
out += [Ins("copy", call.dst, [r(ins.args[0])]), Ins("jump", targets=[cont])]
else: out.append(replace(ins, dst=ins.dst and r(ins.dst), args=[r(a) for a in ins.args],
targets=[blk[t] for t in ins.targets])) # pos অক্ষত: error-এর line:col
copy[blk[c]] = out
blocks = {}
for name, body in fn.blocks.items():
if name != b: blocks[name] = body; continue
blocks[b] = body[:i] + [Ins("copy", r(p), [a]) for p, a in zip(callee.params, call.args)] \
+ [Ins("jump", targets=[blk["B0"]])] # parameter = argument, তারপর দেহে
blocks.update(copy); blocks[cont] = body[i + 1:]
fn.blocks = blocks
renumber(fn)সহায়ক module haat_inline.py পুরোটা দেখুন (এই পর্বের সব নতুন কোড)
# haat_inline.py — পর্ব ৬৭: Haat IR-এর call graph, SCC দিয়ে recursion চেনা, inlining, interprocedural constant propagation.
# লাগে পর্ব ৬২-এর haat_ir.py, পর্ব ৬৪-এর haat_dfa.py আর পর্ব ৬৫-এর haat_opt.py, তিনটিই হুবহু।
# Haat IR v1-এ closure নেই, তাই প্রতিটি call একটি জানা top-level function-এর সরাসরি call: পুরো program-এর call graph জানা।
from collections import Counter
from haat_opt import *
def call_graph(mod): # caller -> যাদের ডাকে (প্রথম দেখার ক্রমে); "<main>" মূল
g = {f: [] for f in mod.funcs}
for f, fn in mod.funcs.items():
for body in fn.blocks.values():
for ins in body:
if ins.kind == "call" and ins.sym not in g[f]: g[f].append(ins.sym)
return g
def sccs(g, trace=None): # Tarjan (১৯৭২): একটি DFS-এ SCC; callee-র SCC আগে বেরোয় (bottom-up)
index, low, stack, out = {}, {}, [], []
def visit(v):
index[v] = low[v] = len(index); stack.append(v)
for w in g[v]:
if w not in index: visit(w); low[v] = min(low[v], low[w])
elif w in stack: low[v] = min(low[v], index[w]) # stack-এ থাকা পূর্বসূরিতে ফেরা edge
if trace is not None: trace.append((v, index[v], low[v], list(stack)))
if low[v] == index[v]: # v এই SCC-র মূল: stack থেকে v পর্যন্ত সবাই এক দল
k = stack.index(v); out.append(stack[k:]); del stack[k:]
for v in g:
if v not in index: visit(v)
return out
def recursive(g): # cycle-এ থাকা function: SCC-তে একাধিক, বা নিজেকেই ডাকে
return {f for comp in sccs(g) for f in comp if len(comp) > 1 or f in g[f]}
def reach(g, start): # start থেকে call graph ধরে যাদের কাছে পৌঁছানো যায় (start-সহ)
seen, todo = set(start), list(start)
while todo:
for w in g[todo.pop()]:
if w not in seen: seen.add(w); todo.append(w)
return seen
def top_temp(fn): # fn-এ ব্যবহৃত সবচেয়ে বড় temp-এর নম্বর
return max([int(x[1:]) for body in fn.blocks.values() for ins in body
for x in [ins.dst, *ins.args] if x and is_temp(x)], default=0)
def inline_site(fn, b, i, callee, tag, rename=True): # fn-এর block b-র i-তম নির্দেশ (call) -> callee-র দেহ
call, top = fn.blocks[b][i], top_temp(fn)
nb = max(int(x[1:]) for x in fn.blocks) + 1
def r(x): # callee-র নাম -> fn-এ নতুন নাম; @global একই থাকে
if x[0] == "@" or not rename: return x
return f"t{top + int(x[1:])}" if is_temp(x) else f"{tag}.{x}" # t3 -> t(top+3), p -> price1.p
blk = {c: f"B{nb + k}" for k, c in enumerate(callee.blocks)} # callee-র block-এর নতুন নাম
cont = f"B{nb + len(callee.blocks)}" # call-এর পরের অংশ: continuation block
copy = {}
for c, body in callee.blocks.items():
out = []
for ins in body:
if ins.kind == "return": # প্রতিটি return: ফল call-এর dst-এ, তারপর continuation-এ লাফ
out += [Ins("copy", call.dst, [r(ins.args[0])]), Ins("jump", targets=[cont])]
else: out.append(replace(ins, dst=ins.dst and r(ins.dst), args=[r(a) for a in ins.args],
targets=[blk[t] for t in ins.targets])) # pos অক্ষত: error-এর line:col
copy[blk[c]] = out
blocks = {}
for name, body in fn.blocks.items():
if name != b: blocks[name] = body; continue
blocks[b] = body[:i] + [Ins("copy", r(p), [a]) for p, a in zip(callee.params, call.args)] \
+ [Ins("jump", targets=[blk["B0"]])] # parameter = argument, তারপর দেহে
blocks.update(copy); blocks[cont] = body[i + 1:]
fn.blocks = blocks
renumber(fn)
def renumber(fn): # block-গুলোর নাম আবার B0, B1 …, dict-এর ক্রমে
names = {b: f"B{k}" for k, b in enumerate(fn.blocks)}
fn.blocks = {names[b]: [replace(ins, args=list(ins.args), targets=[names[t] for t in ins.targets])
for ins in body] for b, body in fn.blocks.items()}
def why_not(mod, g, rec, deep, f, c, limit, depth_safe): # f-এ c-এর call inline না করার কারণ, বা None
if c in rec: return "recursive" # SCC-তে cycle: inline করলে শেষ হয় না
if depth_safe and (f in deep or reach(g, [c]) & rec): return "depth" # ১,০০০-call সীমা বদলাতে পারে
if size(mod.funcs[c]) > limit: return "size"
return None
def inline_module(mod, limit=40, depth_safe=True, rename=True, log=None): # bottom-up: callee-র SCC আগে
g = call_graph(mod); rec = recursive(g); deep = reach(g, rec) # deep: recursion যাদের ডাকতে পারে
stats = Counter()
for comp in sccs(g):
for f in comp:
fn, k = mod.funcs[f], Counter()
while site := next(((b, i, ins.sym) for b, body in fn.blocks.items() for i, ins in enumerate(body)
if ins.kind == "call" and not why_not(mod, g, rec, deep, f, ins.sym, limit, depth_safe)), None):
b, i, c = site; k[c] += 1
inline_site(fn, b, i, mod.funcs[c], f"{c}{k[c]}", rename); stats["inlined"] += 1
if log is not None: log.append((f, c, size(fn)))
for body in fn.blocks.values():
stats.update(why_not(mod, g, rec, deep, f, ins.sym, limit, depth_safe) for ins in body if ins.kind == "call")
return stats
def prune(mod): # <main> থেকে আর ডাকা হয় না এমন function মোছা
keep = reach(call_graph(mod), ["<main>"])
gone = [f for f in mod.funcs if f not in keep]
for f in gone: del mod.funcs[f]
return gone
def ipcp(mod, log=None, rounds=10): # interprocedural constant propagation: argument আর return-এর ধ্রুবক
done, n = set(), 0
for rnd in range(1, rounds + 1):
args, rets = {}, {} # callee -> প্রতিটি call site-এর argument-এর মান; f -> return-এর মান
for f, fn in mod.funcs.items():
pts = points(CONSTANTS, fn, solve(CONSTANTS, fn))
for b, body in fn.blocks.items():
for i, ins in enumerate(body):
env = pts[b, i][0]
if env is None: continue # পৌঁছানো যায় না: কোনো দাবি নেই
if ins.kind == "call": args.setdefault(ins.sym, []).append([env.get(a, BOT) for a in ins.args])
if ins.kind == "return": rets.setdefault(f, []).append(env.get(ins.args[0], BOT))
new = 0
for c, sites in args.items(): # সব call site-এ একই ধ্রুবক -> callee-র শুরুতে p = const k
for j, p in enumerate(mod.funcs[c].params):
v = sites[0][j]
if (c, p) not in done and v is not BOT and all(same(s[j], v) for s in sites):
mod.funcs[c].blocks["B0"].insert(0, Ins("const", p, sym=v)); done.add((c, p)); new += 1
if log is not None: log.append((rnd, "arg", c, p, v))
for f, vals in rets.items(): # প্রতিটি return একই ধ্রুবক -> caller-এ call-এর পরে d = const k
v = vals[0]
if f == "<main>" or ("ret", f) in done or v is BOT or v is None or not all(same(x, v) for x in vals): continue
done.add(("ret", f)); new += 1
if log is not None: log.append((rnd, "ret", f, "return", v))
for fn in mod.funcs.values():
for body in fn.blocks.values():
for ins in [x for x in body if x.kind == "call" and x.sym == f]:
k, d = body.index(ins), ins.dst # call থাকে (ছাপা, error), ফল যায় নতুন temp-এ
body[k:k + 1] = [replace(ins, dst=f"t{top_temp(fn) + 1}", args=list(ins.args)), Ins("const", d, sym=v)]
if not new: break
n += new; optimize_module(mod)
return n
class Calls(dict): # mod.funcs-এর জায়গায় বসে; run_ir প্রতিটি call-এ এখান থেকে function খোঁজে
n = 0
def __getitem__(self, k): self.n += 1; return super().__getitem__(k)
def measure(mod): # (চলা নির্দেশ, চলা call), run_ir হুবহু; runtime error হলে নির্দেশ None
funcs = mod.funcs; mod.funcs = Calls(funcs)
try: steps = run_ir(mod, out=lambda s: None)
except HaatError: steps = None
calls = mod.funcs.n - 1; mod.funcs = funcs # প্রথম খোঁজটি "<main>"-এর
return steps, calls1B0: t1 = const 22 t2 = const 5203 price1.qty = t14 price1.unit = t25 jump B16B1: price1.p = price1.qty * price1.unit7 t15 = const 10008 t16 = price1.p >= t159 branch t16 B2 B310B2: t17 = const 1011 t18 = price1.p / t1712 t19 = price1.p - t1813 t3 = t1914 jump B415B3: t3 = price1.p16 jump B417B4: t4 = const 218 …19 first = t3 + t7
| ধাপ | |
| নাম | |
| block |
- Call site.
<main>-এর B0-এর তৃতীয় নির্দেশt3 = call price(t1, t2). price recursive নয়, আকারে ৯টি নির্দেশ। - ভাগ. call-এর আগের দুটি নির্দেশ B0-তে থাকে। পরের সবকিছু (
t4 = const 2থেকে loop-এ যাওয়া পর্যন্ত) একটি নতুন continuation block-এ, শেষে যার নাম B4. - নাম বদল.
<main>-এর সবচেয়ে বড় temp t14, তাই price-এর t1 … t5 হয় t15 … t19.pহয়price1.p; বিন্দুসহ নাম Haat-এর identifier হতে পারে না, তাই সংঘর্ষ অসম্ভব। - Parameter. B0-এর শেষে
price1.qty = t1,price1.unit = t2, তারপরjump B1: price-এর entry-র কপি। এটিই call-by-value: argument-এর মান parameter-এ কপি (পর্ব ২৯)। - দুটি return. price-এর
return t5হয়t3 = t19; jump B4, আরreturn pহয়t3 = price1.p; jump B4. দুই পথই একই t3-এ লিখে continuation-এ মেলে। - যাচাই.
t18 = price1.p / t17তার মূলposরাখে। আউটপুট 996, 5000, 3, reference-এর মতো। চলা নির্দেশ ৭৪ থেকে ৭৭: একটিcallআর একটিreturn-এর জায়গায় দুটি copy, দুটি jump আর ফলের একটি copy. Call ৩ থেকে ২.
ধরুন d = call f(a…) চলার সময় caller-এর env E আর f-এর নতুন frame-এর env F. Inline-এর পরে একই মুহূর্তে caller-এর env E ∪ F', যেখানে F' হলো F-এর নামগুলো নতুন নামে।
- নতুন নামগুলো caller-এর কোনো নামের সঙ্গে মেলে না (temp-এর নম্বর top-এর বড়, variable-এ বিন্দু), তাই কপির কোনো লেখা E-র কোনো মান বদলায় না, আর caller-এর কোনো নির্দেশ F'-এর নাম পড়ে না।
- কপির প্রতিটি নির্দেশ একই মানে একই হিসাব করে, একই
pos-সহ;@globalদুই রূপেই একই memory. - f-এর
return vমূল রূপে caller-এর d-তে v-এর মান লিখে call-এর পরের নির্দেশে ফেরে; কপিতেd = v'আর continuation-এ jump ঠিক একই কাজ। - তাই ছাপা লাইন আর error একই ক্রমে আসে। ব্যতিক্রম একটিই: frame কম, তাই stack-এর গভীরতা এক কম; অংশ ৫ দেখায় কখন তা নিরাপদ। ∎
এবার পুরো bazar.haat. inline_module bottom-up ক্রমে যোগ্য call site inline করে; prune মোছে সেই function, যাদের আর কেউ ডাকে না; তারপর পর্ব ৬৫-এর optimize_module. measure চলা নির্দেশ আর call গোনে: mod.funcs-এর জায়গায় একটি dict subclass বসিয়ে, যা প্রতিটি function খোঁজা গোনে; run_ir অপরিবর্তিত।
# ধাপ ১: bazar.haat — call graph, SCC, তারপর inline → prune → optimize; প্রতি ধাপে গোনা আর আউটপুট মেলানো
from haat_inline import * # call_graph, sccs, inline_module, prune, measure (+ পর্ব ৬২, ৬৪, ৬৫ হুবহু)
src = open("examples/bazar.haat", encoding="utf-8").read()
want = open("examples/bazar.out", encoding="utf-8").read().split("\n")[:-1] # reference `run`
def report(tag, mod):
steps, calls = measure(mod)
print(f"{tag:<15} স্থির {sum(map(size, mod.funcs.values())):2} · চলা {steps:2} · call {calls}"
f" · == reference: {run_lines(mod) == want}")
mod = compile_ir(src)
g = call_graph(mod)
print("call graph:", g)
print("SCC (bottom-up):", sccs(g), "· recursive:", recursive(g) or "কেউ নয়")
report("শুরুতে", mod)
log = []
print(dict(inline_module(mod, log=log)), "·", log)
report("inline-এর পরে", mod)
print("মোছা function:", prune(mod))
report("prune-এর পরে", mod)
optimize_module(mod)
report("optimize-এর পরে", mod)
print(show_ir(mod.funcs["<main>"]).split("B1:")[0].rstrip())
only = compile_ir(src)
optimize_module(only)
report("শুধু optimize", only)আসল আউটপুট (ব্রাউজারের Python):
call graph: {'<main>': ['price', 'delivery'], 'price': [], 'delivery': []}
SCC (bottom-up): [['price'], ['delivery'], ['<main>']] · recursive: কেউ নয়
শুরুতে স্থির 42 · চলা 74 · call 3 · == reference: True
{'inlined': 3} · [('<main>', 'price', 39), ('<main>', 'price', 52), ('<main>', 'delivery', 62)]
inline-এর পরে স্থির 78 · চলা 82 · call 0 · == reference: True
মোছা function: ['price', 'delivery']
prune-এর পরে স্থির 62 · চলা 82 · call 0 · == reference: True
optimize-এর পরে স্থির 19 · চলা 46 · call 0 · == reference: True
fn <main>():
B0:
first = const 996
print first
total = const 0
rounds = const 0
jump B1
শুধু optimize স্থির 40 · চলা 72 · call 3 · == reference: True
শুধু inline: স্থির নির্দেশ ৪২ থেকে ৭৮, চলা ৭৪ থেকে ৮২: call-এর বদলে parameter-এর copy আর বাড়তি jump, তাই inline একা কাজ সামান্য বাড়ায়। prune: price আর delivery মোছা, স্থির ৬২. optimize: এবার fold দেখে price1.qty 2 আর price1.unit 520, তাই 1040 ≥ 1000 সত্য, শাখা মুছে 936; delivery-র কপিতে 936 ≥ 1000 মিথ্যা, তাই 60; আর first = const 996. চলা নির্দেশ ৪৬, call ০; যা বাকি, তা loop. শুধু optimize-এ ৭২-এর সঙ্গে তুলনা করুন: আসল লাভ ডাকার খরচে নয়, ডাকার জায়গার তথ্যে।
৪ · কখন inline করবেন — লাভ, code growth আর Clang-এর হিসাব
Inlining-এর লাভ তিন স্তরে। (১) Call-এর নিজের খরচ: argument বসানো, ফেরার ঠিকানা, calling convention মেনে register বাঁচানো (পর্ব ৭১)। (২) ডাকার জায়গার তথ্য: ধ্রুবক argument আর আশপাশের একই হিসাব, যা fold আর CSE হয়; bazar-এ এটিই বড় লাভ। (৩) পরের বিশ্লেষণ সহজ হওয়া: escape analysis (অংশ ৭) বা loop optimization (পর্ব ৬৬) বড় function-এ বেশি দেখে।
দামও আছে। প্রতিটি কপি কোড বাড়ায় (code growth): compile ধীর, executable বড়, আর গরম কোড instruction cache-এ আর আঁটে না। বড় function-এ একসঙ্গে বেশি মান জীবিত থাকে, তাই register pressure বাড়ে (পর্ব ৭০)। আর বৃদ্ধি গুণে গুণে হতে পারে: f1 যদি f2-কে দুবার ডাকে, f2 f3-কে দুবার, এভাবে n স্তর, তাহলে সব inline করলে fn-এর 2n−1টি কপি। তাই প্রতিটি inliner-এর একটি নীতি লাগে। আমাদেরটি সরল: callee-র আকার (bottom-up ক্রমে, তার নিজের inline-এর পরে) বড়জোর limit = ৪০টি নির্দেশ। সীমা বদলালে কী হয়, লেখকের lab-এ ৩,০০০টি এলোমেলো program (haat_gen.py, seed 0–2999) দিয়ে মাপা, প্রতিটিতে inline → prune → optimize; সব সংস্করণে আউটপুট reference-এর সঙ্গে হুবহু (সত্যিকারের run; চলা নির্দেশ error ছাড়া শেষ হওয়া ২,৬৭৫টি program-এ):
| নীতি | inline করা call site | স্থির নির্দেশ | চলা নির্দেশ | চলা call | সবচেয়ে বড় function |
|---|---|---|---|---|---|
| শুধু optimize (পর্ব ৬৫) | ০ | −২২.৪% | −১৯.৯% | ১৬,৫৭০ | ২৮২ |
| শুধু prune + optimize | ০ | −২৯.০% | −১৯.৯% | ১৬,৫৭০ | ২৮২ |
| সীমা ১০ | ২,২৮১ | −২৮.৯% | −২১.১% | ১৪,১৪৮ | ২৮৯ |
| সীমা ২০ | ৬,০৯০ | −২৬.৩% | −২৩.৫% | ১০,২০৪ | ৩২৬ |
| সীমা ৪০ (আমাদের) | ১০,০২৮ | −১৮.০% | −২৬.২% | ৬,২৪৯ | ৫৩৮ |
| সীমা ৮০ | ১৩,৭৩০ | +১.৭% | −২৮.৩% | ২,৭১৬ | ৮৫৪ |
| সীমা নেই | ১৬,৮২২ | +৪৩.৪% | −৩০.৭% | ০ | ৫,৩২৮ |
শতাংশ মূল ৪,১৯,০২৮টি স্থির আর ৭,৫১,৯৩৯টি চলা নির্দেশের তুলনায়। এলোমেলো program-এর অনেক function কেউ ডাকে না, তাই শুধু prune স্থির কোড অনেক কমায়। সীমা বাড়ালে চলা নির্দেশ আর call কমে, কিন্তু স্থির কোড বাড়ে, আর সবচেয়ে বড় function ফুলে ওঠে: গতি না আকার, তার ওপর নির্ভর করে কোথায় থামবেন। এগুলো interpreter-এ গোনা নির্দেশ; বাস্তব CPU-র cache আর register-এর প্রভাব এখানে নেই।
বাস্তব compiler কীভাবে সিদ্ধান্ত নেয়? bazar.haat-এর একটি C রূপ (long দিয়ে, সঙ্গে একটি recursive fact) PyPI-র ziglang 0.17.1-এর ভেতরের Clang 22.1.8 দিয়ে চালানো হলো; -Rpass=inline প্রতিটি সফল inline, আর -Rpass-missed=inline প্রতিটি বাতিলের কারণ remark হিসেবে ছাপে। লেখকের lab-এ সত্যিকারের run (x86-64 Linux target; caret লাইন আর শেষের [-Rpass=…] ট্যাগ বাদ):
static long price(long qty, long unit) {
long p = qty * unit;
if (p >= 1000) return p - p / 10;
return p;
}
static long delivery(long total) {
if (total >= 1000) return 0; else return 60;
}
static long fact(long n) {
if (n <= 1) return 1;
return n * fact(n - 1);
}
long first(long q) {
return price(q, 520) + delivery(price(q, 520));
}
int main(void) {
printf("%ld\n", first(2));
printf("%ld\n", fact(5));
return 0;
}
~/inline $ python -m ziglang cc --target=x86_64-linux-musl -O2 -g0 -fno-sanitize=undefined \
-Rpass=inline -Rpass-missed=inline -S -emit-llvm bazar.c -o bazar_O2.ll
bazar.c:16:12: remark: 'price' inlined into 'first' with (cost=-15, threshold=225) at callsite first:1:12;
bazar.c:16:37: remark: 'price' inlined into 'first' with (cost=-15015, threshold=225) at callsite first:1:37;
bazar.c:16:28: remark: 'delivery' inlined into 'first' with (cost=-15025, threshold=337) at callsite first:1:28;
bazar.c:13:16: remark: fact has uninlinable pattern (recursive) and cost is not fully computed
bazar.c:13:16: remark: 'fact' not inlined into 'fact' because it should never be inlined (cost=never): recursive
bazar.c:19:21: remark: 'first' inlined into 'main' with (cost=-35, threshold=337) at callsite main:1:21;
bazar.c:20:21: remark: 'fact' inlined into 'main' with (cost=-15015, threshold=225) at callsite main:2:21;
LLVM প্রতিটি call site-এর একটি আনুমানিক cost (দেহ কত নির্দেশ যোগ করবে, ধ্রুবক argument-এ কতটা মুছবে) একটি threshold-এর সঙ্গে তুলনা করে; এখানে 225, কিছু ক্ষেত্রে 337. Cost ঋণাত্মক মানে inline-এর পরে কোড কমবে বলে অনুমান। −15015-এর মতো বিশাল ঋণাত্মক সংখ্যা আসে একটি বিশেষ ছাড় থেকে: একটি static function-এর শেষ call site inline হলে মূল function-টিই মুছে ফেলা যায়; LLVM-এর উৎসে এর জন্য ১৫,০০০-এর একটি বোনাস আছে বলে জানা যায়, আর −15 − 15000 = −15015 মিলে যায় (সঠিক সংখ্যা আর নিয়ম version-ভেদে বদলাতে পারে)। আমাদের prune পরে ঠিক এটিই করে। লক্ষ করুন bottom-up ক্রম (price আর delivery আগে first-এ, তারপর first main-এ), আর fact-এর দুটি বিপরীত remark (অংশ ৫)।
Inline-এর পরে first-এর LLVM IR (একই run, !dbg মেটাডেটা বাদ):
define dso_local range(i64 -9223372036854775748, 9223372036854775768) i64 @first(i64 noundef %0) local_unnamed_addr #0 {
%2 = mul nsw i64 %0, 520
%3 = icmp sgt i64 %0, 1
br i1 %3, label %4, label %7
4:
%5 = udiv i64 %2, 10
%6 = sub nsw i64 %2, %5
br label %7
7:
%8 = phi i64 [ %6, %4 ], [ %2, %1 ]
%9 = icmp sgt i64 %8, 999
%10 = select i1 %9, i64 0, i64 60
%11 = add nsw i64 %10, %8
ret i64 %11
}
price-এর দুটি কপির মাত্র একটি টিকে আছে: inline-এর পরে দুটি কপি একই হিসাব, তাই GVN (পর্ব ৬৫-এর CSE-এর বড় রূপ) সেগুলো মিলিয়েছে, যা দুটি call থাকা অবস্থায় অসম্ভব ছিল। p >= 1000 হয়েছে q > 1: mul nsw-এর “overflow হয় না” অনুমান থেকে (C-র UB; পর্ব ৬৫ দেখেছে Haat কেন এমন করতে পারে না)। আর main-এ দুটি printf সরাসরি 996 আর 120 পায়। -O0-এ একই ফাইলে কোনো inline remark আসে না (সত্যিকারের run). C-র inline শব্দটি শুধু একটি ইঙ্গিত (C standard-এ এর কার্যকারিতা implementation-এর ওপর); __attribute__((always_inline)) আর noinline সিদ্ধান্ত জোর করে বদলায়।
৫ · Recursion, tail call আর ১,০০০-call-এর সীমা
Clang-এর remark-এ fact “never be inlined: recursive”, অথচ পরে “'fact' inlined into 'main'”. মাঝখানে অন্য একটি pass কাজ করেছে। fact-কে non-static করে একই flag-এ -mllvm -print-changed=quiet দিয়ে চালালে (লেখকের lab-এ সত্যিকারের run) fact বদলানো pass-গুলোর তালিকায় আছে TailCallElimPass, আর শেষ IR-এ fact-এর ভেতরে আর কোনো call নেই, আছে একটি loop (৮ গুণ unroll করা)। n * fact(n - 1) আক্ষরিক অর্থে tail call নয়, কারণ call-এর পরে একটি গুণ বাকি; তবু LLVM-এর এই pass গুণের মতো associative কাজের জন্য একটি accumulator বসিয়ে recursion-কে loop বানাতে পারে। Loop হয়ে গেলে fact আর recursive নয়, তাই inline হয়, আর fact(5) fold হয়ে 120. Tail call আর তার optimization-এর ভাষাগত দিক পর্ব ৩২-এ।
Haat-এ গল্পটি সূক্ষ্ম, কারণ stack-এর গভীরতা আচরণের অংশ: ১,০০০-এর বেশি nested call হলে stack overflow একটি নির্ধারিত runtime error, reference-এর দুই back end-এ একই সীমায় (সিদ্ধান্ত ২৬)। C-তে stack ফুরানো standard-এর বাইরের ঘটনা, তাই Clang এ নিয়ে ভাবে না; Haat-এর inliner-কে ভাবতে হয়। এই program-টি দেখুন:
// বাজারঘর: গভীর recursion, ১,০০০-call সীমার কাছে
fn count(n: Int) -> Int {
if n == 0 { return 0; }
return count(n - 1) + 1;
}
fn start(n: Int) -> Int {
return count(n);
}
print(start(998));
print(start(999));Reference ছাপে 998, তারপর 4:12: runtime error: stack overflow: start(999)-এ start আর ১,০০০টি count মিলে ১,০০১টি nested call, সীমার একটি বেশি। start recursive নয়, তাই সরল inliner তাকে <main>-এ বসায়; nested call ঠিক ১,০০০টি হয়, আর program ছাপে 998, 999: আচরণ বদলে গেল। একটি Haat tail call optimization-ও ঠিক একই কারণে আচরণ বদলাত। আমাদের inliner তাই একটি বাড়তি নিয়ম মানে (depth_safe, স্বাভাবিকভাবে চালু):
নিয়ম: call site A → C inline করুন শুধু যদি (ক) C কোনো recursive SCC-তে পৌঁছায় না, আর (খ) A নিজে কোনো recursive function থেকে (পরোক্ষে হলেও) ডাকা যায় না। দাবি: program-এ ১,০০০টির বেশি function না থাকলে (<main>-সহ), নিয়ম মানা inlining কখনো stack overflow যোগ করে না বা সরায় না।
- একটি মুছে ফেলা C-frame stack-এ থাকার সময় তার নিচের frame-গুলো (main থেকে A) কোনো recursive function নয়, (খ)-এর কারণে; ওপরের frame-গুলো (C-র callee-রা) recursive নয়, (ক)-এর কারণে।
- Recursion ছাড়া একই function stack-এ দুবার থাকতে পারে না (থাকলে call graph-এ cycle হতো)। তাই তখন stack-এর গভীরতা ≤ function-এর সংখ্যা ≤ ১,০০০: মূল আর inline করা দুই program-এই সেই সময়ে কোনো overflow নেই।
- অন্য যেকোনো মুহূর্তে কোনো মুছে ফেলা frame stack-এ নেই, তাই দুই program-এর গভীরতা হুবহু সমান, আর overflow হলে একই call-এ, একই
line:col-এ। ∎
JS ব্লক আর ছবি ৬৭.১-এ “depth নিয়ম” এটিই। দাম মাপা যায়: লেখকের lab-এর ৩,০০৯টি program-এ (অংশ ৮) নিয়মটি মাত্র ২টি call site আটকেছে, দুটিই depth.haat-এ, আর নিয়মটি বন্ধ করলে ঠিক একটি program-এর আউটপুট বদলায়: depth.haat. সৎভাবে বলা দরকার, এলোমেলো program recursion বানায় না (haat_gen.py-এর function শুধু আগের function ডাকে), তাই এখানে recursion আসে শুধু উদাহরণ থেকে। অন্য ভাষার পছন্দ ভাবনার প্রশ্ন ৫-এ।
৬ · Interprocedural constant propagation — পুরো program দেখলে
Inlining-এর একটি বিকল্প কোড বাড়ায় না। Interprocedural constant propagation (IPCP) প্রতিটি parameter-এর জন্য সব call site-এর argument-এর meet নেয় (পর্ব ৬৫-এর constant lattice): সব একই k হলে k, নইলে ⊥. উল্টো দিকে: function-টির প্রতিটি return কি একই ধ্রুবক দেয়?
ipcp), রাউন্ডে রাউন্ডে
- প্রতিটি function-এ পর্ব ৬৫-এর
CONSTANTSবিশ্লেষণ চালিয়ে প্রতিটি call site-এ argument-এর মান আর প্রতিটি return-এ ফেরত মান সংগ্রহ (পৌঁছানো যায় না এমন জায়গা বাদ)। - Argument: parameter p প্রতিটি call site-এ একই ধ্রুবক k পেলে callee-র শুরুতে
p = const k. - Return: f-এর প্রতিটি return একই ধ্রুবক k দিলে প্রতিটি
d = call f(…)হয়t = call f(…)আরd = const k. Call-টি থাকে, কারণ f ছাপতে, global বদলাতে বা error দিতে পারে; শুধু ফলের মান এখন জানা। - নতুন তথ্য পেলে
optimize_moduleআর আবার ধাপ ১; নইলে থামা। শুরুতে সব parameter ⊥, তাই প্রতিটি দাবি প্রতিটি চলায় সত্য।
1fn price(qty: Int, unit: Int) -> Int {2 let p = qty * unit;3 if p >= 1000 { return p - p / 10; }4 return p;5}6fn delivery(total: Int) -> Int {7 if total >= 1000 { return 0; } else { return 60; }8}9let first = price(2, 520) + delivery(price(2, 520));
| qty, unit | |
| price ফেরত | |
| total | |
| delivery ফেরত | |
| first |
- রাউন্ড ১, argument. price-এর দুটি call site, দুটিতেই (2, 520), তাই price-এর শুরুতে
qty = const 2,unit = const 520. delivery-র একমাত্র argument একটি call-এর ফল, যা এখনো ⊥. - Optimize. price-এর ভেতরে p = 1040, শাখার শর্ত সত্য, অন্য শাখা অগম্য: price নেমে আসে
t5 = const 936; return t5-এ। একই রাউন্ডে return-এর তথ্য নেওয়া হয়নি, কারণ সংগ্রহ হয়েছিল optimize-এর আগে। - রাউন্ড ২, return. price-এর প্রতিটি return এখন 936.
<main>-এ দুটি call থাকে, কিন্তু ফল নতুন temp-এ যায় আর পুরোনো নামেconst 936. Optimize-এর পরে delivery-র argument 936. - রাউন্ড ৩, argument. delivery-র একমাত্র call site-এ 936, তাই
total = const 936; 936 ≥ 1000 মিথ্যা, delivery নামেreturn 60-এ। - রাউন্ড ৪, return. delivery-র return 60, তাই
first = 936 + 60fold হয়েconst 996. রাউন্ড ৫-এ নতুন কিছু নেই, থামা। তিনটি call-ই রয়ে গেছে।
# ধাপ ২: inline না করে interprocedural constant propagation — argument আর return-এর ধ্রুবক, রাউন্ডে রাউন্ডে
from haat_inline import *
for name in ("bazar", "err_divzero"):
src = open(f"examples/{name}.haat", encoding="utf-8").read()
want = open(f"examples/{name}.out", encoding="utf-8").read().split("\n")[:-1]
mod = compile_ir(src)
(s0, c0), n0 = measure(mod), sum(map(size, mod.funcs.values()))
log = []
ipcp(mod, log)
print(f"== {name}.haat")
for rnd, kind, f, p, v in log:
print(f" রাউন্ড {rnd}: {f}-এর {p} = {lit(v)}" + (" (প্রতিটি call site-এ)" if kind == "arg" else " (প্রতিটি return-এ)"))
for f in mod.funcs:
if f != "<main>": print(show_ir(mod.funcs[f]))
(s1, c1), n1 = measure(mod), sum(map(size, mod.funcs.values()))
ran = lambda s: "error-এ থামে" if s is None else s
print(f" স্থির {n0} → {n1} · চলা {ran(s0)} → {ran(s1)} · call {c0} → {c1}")
print(" আউটপুট:", run_lines(mod), "== reference:", run_lines(mod) == want)আসল আউটপুট (ব্রাউজারের Python):
== bazar.haat
রাউন্ড 1: price-এর qty = 2 (প্রতিটি call site-এ)
রাউন্ড 1: price-এর unit = 520 (প্রতিটি call site-এ)
রাউন্ড 2: price-এর return = 936 (প্রতিটি return-এ)
রাউন্ড 3: delivery-এর total = 936 (প্রতিটি call site-এ)
রাউন্ড 4: delivery-এর return = 60 (প্রতিটি return-এ)
fn price(qty, unit):
B0:
t5 = const 936
return t5
fn delivery(total):
B0:
t4 = const 60
return t4
স্থির 42 → 29 · চলা 74 → 58 · call 3 → 3
আউটপুট: ['996', '5000', '3'] == reference: True
== err_divzero.haat
রাউন্ড 1: share-এর total = 1000 (প্রতিটি call site-এ)
fn share(total, people):
B0:
total = const 1000
t1 = total / people
return t1
স্থির 14 → 14 · চলা error-এ থামে → error-এ থামে · call 2 → 2
আউটপুট: ['250', '3:18: runtime error: division by zero'] == reference: True
bazar-এ IPCP inline ছাড়াই স্থির নির্দেশ ৪২ থেকে ২৯, চলা ৭৪ থেকে ৫৮ নামায়; call ৩টিই থাকে। Inline-এর ৪৬-এর চেয়ে কম, কিন্তু কোড বাড়েনি। err_divzero-তে দুই call site-এ total 1000, কিন্তু people 4 আর 0, তাই শুধু total ধ্রুবক; ভাগটি থাকে, আর error একই 3:18-এ। লেখকের lab-এ ৩,০০৯টি program-এ IPCP মোট ১,৬৪৭টি তথ্য পেয়েছে, তবে চলা নির্দেশ কমেছে শুধু optimize-এর মতোই (১৬.৩%): এলোমেলো program-এ একই function সাধারণত আলাদা argument-এ ডাকা হয়, আর একটি call site আলাদা হলেই তথ্যটি হারায়।
এই সীমার উত্তর function specialization: একই ধ্রুবক দেওয়া call site-গুলোর জন্য function-এর আলাদা কপি। GCC-র -fipa-cp-clone এমন কপি বানায় বলে তার নথিতে আছে, LLVM-এও এমন pass আছে; কোন স্তরে চালু, তা version-ভেদে বদলায়। তবে IPCP-র একটি গভীর শর্ত আছে: প্রতিটি call site জানা থাকতে হবে। Haat IR v1-এ একটি ফাইলই পুরো program, আর function মান হিসেবে কোথাও যায় না, তাই শর্তটি সত্য। এই অনুমানকে বলে closed world, আর তার ওপর দাঁড়ানো কাজকে whole-program optimization.
৭ · Devirtualization, escape analysis আর আলাদা compile-এর দেয়াল
আলাদা compile. C-তে প্রতিটি .c ফাইল আলাদা compile হয় (separate compilation). একটি non-static function অন্য ফাইল বা library থেকেও ডাকা যেতে পারে, তাই compiler তার সব call site দেখে না: IPCP বা “শেষ call site inline করে function মোছা” চলে না। static লিখলে function ফাইলের ভেতরে বন্দি, আর ওপরের Clang run-এ ঠিক তাই −15015-এর বোনাস এসেছে। পুরো program একসঙ্গে দেখার বাস্তব উপায় link-time optimization (LTO): object file-এ machine code নয়, compiler-এর IR থাকে, আর link-এর সময় সব ফাইল মিলে optimize হয়। পর্ব ৭৪-এ এর সত্যিকারের run আছে: LTO-র পরে main ৩০৭ থেকে ৫৮ byte, আর price নামের symbol-ই নেই। সেটি এই পর্বের inliner আর IPCP-রই কাজ, linker-এর ভেতরে।
Devirtualization. C++ বা Java-তে d.apply(t) একটি dynamic dispatch: কোন apply চলবে, তা চলার সময় object দেখে ঠিক হয়, তাই call graph-এ edge-টি অনিশ্চিত আর inline অসম্ভব। Compiler যদি প্রমাণ করতে পারে যে একটিই সংস্করণ সম্ভব (class final, বা পুরো program-এ একটিই subclass), তবে পরোক্ষ call-কে সরাসরি call বানায়: devirtualization, আর তারপর সাধারণ inline. পর্ব ০৮-এ Clang -O2-তে final class-এ ঠিক এটি ঘটতে দেখেছেন। JIT আরও এক ধাপ যায় (পর্ব ৬১): প্রমাণ ছাড়াই profile দেখে অনুমান করে inline করে, সামনে একটি পাহারা (guard) রাখে, আর অনুমান ভুল হলে deoptimization. Haat-এর closure-এর call-ও একই সমস্যা, তাই Haat IR v1 এমন program নেয় না।
Escape analysis আর purity. একটি object callee-তে তৈরি হয়ে শুধু caller-এ ব্যবহার হলে, inline-এর পরে সেটি function-এর বাইরে যায় না; escape analysis তখন heap-এর বদলে stack বা register-এ রাখার অনুমতি দেয় (পর্ব ১৬, আর garbage collector-এর ওপর চাপ কমানোর দিক পর্ব ৭৫-এ)। উল্টো দিকে, function না জুড়েও জানা যায় একটি function side effect-মুক্ত, অর্থাৎ pure কি না। ওপরের Clang IR-এর first-এর attribute-এ memory(none) আর norecurse আছে (একই run): Clang নিজেই প্রমাণ করেছে first memory ছোঁয় না। এমন তথ্যে পর্ব ৬৫-এর CSE দুটি একই call মেলাতে পারত। কোন call site বেশি চলে, তা জানতে compiler আগের run-এর মাপও নেয় (profile-guided optimization), আর গরম call site-এ বেশি উদার হয়।
৮ · যাচাই — differential test আর জেনেশুনে বসানো ভুল
Inliner-এর ভুল সাধারণত চুপচাপ: program চলে, শুধু ভুল উত্তর দেয়। তাই পর্ব ৬৫-এর মতোই differential test: পর্ব ৬২-এর উদাহরণ, depth.haat, shop.haat আর প্রথম ৪০টি এলোমেলো program-এ inline → prune → optimize চালিয়ে আউটপুট reference-এর সঙ্গে মেলানো, error-এর বার্তা আর অবস্থানসহ। আর পরীক্ষাটি আসলে কিছু ধরে কি না, দেখতে একটি জেনেশুনে বসানো ভুল (mutation testing): rename=False, অর্থাৎ callee-র নাম বদলানো হয় না।
# ধাপ ৩: differential test — inline+optimize-এর পরে আউটপুট কি reference-এর মতো? আর নাম না বদলানো inliner কি ধরা পড়ে?
import hashlib
from haat_inline import *
from haat_gen import gen_program
def digest(lines): return hashlib.sha256("\n".join(lines).encode()).hexdigest()[:10]
def lines_of(mod): # ভুল inliner-এ IR interpreter নিজেই ভেঙে পড়তে পারে
try: return run_lines(mod)
except Exception as e: return ["crash: " + type(e).__name__]
progs = [] # (নাম, source, ঠিক আছে কি না যাচাইয়ের function)
for name in ("bazar", "recursion", "mutual", "shadowing", "shortcircuit", "strings", "loops", "err_divzero"):
want = open(f"examples/{name}.out", encoding="utf-8").read().split("\n")[:-1]
progs.append((name, open(f"examples/{name}.haat", encoding="utf-8").read(), lambda got, w=want: got == w))
for n in ("depth", "shop"):
want = open(f"{n}.out", encoding="utf-8").read().split("\n")[:-1]
progs.append((n, open(f"{n}.haat", encoding="utf-8").read(), lambda got, w=want: got == w))
ref = open("random_ref.txt", encoding="utf-8").read().split()
progs += [(s, gen_program(s), lambda got, s=s: digest(got) == ref[s]) for s in range(40)] # seed 0–39
ok, sites, fired, caught, nodepth = 0, Counter(), 0, [], []
for name, src, good in progs:
mod = compile_ir(src)
sites += inline_module(mod); prune(mod); optimize_module(mod)
ok += good(run_lines(mod))
bad = compile_ir(src) # জেনেশুনে বসানো ভুল: callee-র নাম বদলানো হয় না
if inline_module(bad, rename=False)["inlined"]:
fired += 1
if not good(lines_of(bad)): caught.append(name)
deep = compile_ir(src); inline_module(deep, depth_safe=False)
if not good(run_lines(deep)): nodepth.append(name)
print(f"সঠিক inliner: {ok}/{len(progs)} program হুবহু · call site: {dict(sites)}")
print(f"নাম না বদলানো inliner: খাটল {fired}টিতে, ধরা পড়ল {len(caught)}টিতে: {caught[:8]}")
print(f"depth নিয়ম ছাড়া: অমিল {nodepth}")আসল আউটপুট (ব্রাউজারের Python):
সঠিক inliner: 50/50 program হুবহু · call site: {'inlined': 153, 'recursive': 21, 'depth': 2, 'size': 91}
নাম না বদলানো inliner: খাটল 38টিতে, ধরা পড়ল 6টিতে: ['bazar', 15, 26, 30, 33, 34]
depth নিয়ম ছাড়া: অমিল ['depth']
সঠিক inliner প্রতিটি program-এ হুবহু। নাম না বদলানো inliner bazar-এ 996-এর বদলে 70 ছাপে: দ্বিতীয় price-এর কপির t3 = const 10 লেখে <main>-এর t3-এ, যেখানে প্রথম price-এর ফল 936 ছিল, তাই first = 10 + 60. কিন্তু ৩৮টি program-এ খাটলেও ধরা পড়ে মাত্র ৬টিতে: বেশির ভাগ ক্ষেত্রে সংঘর্ষের নামটি পরে আর পড়াই হয় না। depth নিয়ম বন্ধ করলে অমিল শুধু depth.haat-এ, অংশ ৫-এর মতোই।
লেখকের lab-এ (CPython 3.14.4) বড় পরীক্ষা: আটটি উদাহরণ, depth.haat আর seed 0–2999, মোট ৩,০০৯টি program (closure-এর দুটি উদাহরণ বাদ), reference-এর run সরাসরি চালিয়ে; সত্যিকারের run:
| সংস্করণ | অমিল | স্থির নির্দেশ | চলা নির্দেশ | চলা call |
|---|---|---|---|---|
| মূল IR | ০ | ৪,১৯,৩৫৪ | ৯,১৮,৩০৮ | ৩৮,৭১৮ |
| শুধু optimize (পর্ব ৬৫) | ০ | −২২.৪% | −১৬.৩% | ৩৮,৭১৮ |
| শুধু inline, optimize ছাড়া | ০ | +৫৩.৪% | +২.৮% | ২৮,৩৮৬ |
| inline → prune → optimize | ০ | −১৮.০% | −২১.৪% | ২৮,৩৮৬ |
| IPCP → optimize | ০ | −২২.৮% | −১৬.৩% | ৩৮,৭১৮ |
| নাম না বদলানো inliner | ৩৭১ (খাটল ২,৩৭০টিতে) | — | — | — |
| depth নিয়ম ছাড়া | ১ (depth.haat) | — | — | — |
চলা নির্দেশ আর call গোনা হয়েছে error ছাড়া শেষ হওয়া ২,৬৮২টি program-এ; ৩২৭টি program runtime error-এ থামে, বার্তা আর line:col প্রতিটি সংস্করণে হুবহু। ১০,০৪৩টি call site inline হয়েছে; বাতিল ৮,৪৭১টি আকারের জন্য, ১৫টি recursion-এর জন্য, ২টি depth নিয়মে; ৩,৮৭৬টি function মোছা গেছে। বাকি ২৮,৩৮৬টি call-এর ২২,১৩৭টি আসে recursion আর mutual উদাহরণের fact, fib, is_even আর is_odd থেকে, যা কোনো নিয়মেই inline হয় না; বাকি ৬,২৪৯টি এলোমেলো program-এর, যেখানে callee সীমা ৪০-এর বড়। নাম না বদলানোর ভুল ধরা পড়েছে মাত্র ১৫.৭% ক্ষেত্রে: পর্ব ৬৫-এর x / x → 1-এর মতোই, এলোমেলো test ভুলকে চালায়, কিন্তু সবসময় দেখায় না।
আরও গভীরে: Functional ভাষায় inlining আরও কেন্দ্রীয়। Haskell-এর GHC compiler-এর simplifier বারবার inline করে, আর Simon Peyton Jones ও Simon Marlow-এর ২০০২ সালের প্রবন্ধ “Secrets of the Glasgow Haskell Compiler inliner” দেখায়, recursive binding-এর একটি দলে (ঠিক এই পর্বের SCC) একটি “loop breaker” বেছে নিলে বাকিদের নিরাপদে inline করা যায়, inline অসীম হয় না। আমাদের inliner পুরো recursive SCC বাদ দেয়; loop breaker কৌশলে odd-কে breaker (কখনো inline নয়) ধরলে odd-এর ভেতরে even-এর call inline হতো, আর odd তখন নিজেকেই ডাকত।
পরীক্ষা ও ইন্টারভিউতে:
- Inlining কী, আর এর প্রধান লাভ কী? Call-এর জায়গায় callee-র দেহ বসানো; call-এর খরচ বাঁচে, আর বড় লাভ হলো ডাকার জায়গার তথ্য (ধ্রুবক argument) দিয়ে আরও optimization.
- Inlining-এর ক্ষতি? Code growth, বেশি compile সময়, instruction cache আর register-এর চাপ; তাই আকার বা cost-এর সীমা।
- Recursive function কেন সরাসরি inline হয় না, আর কীভাবে চেনা যায়? দেহে আবার একই call, শেষ নেই; call graph-এর SCC (Tarjan বা Kosaraju) একাধিক function-এর হলে বা নিজেকে ডাকলে recursive.
- Inline করার সময় callee-র variable-এর নাম বদলাতে হয় কেন? Callee-র আলাদা frame আর থাকে না; নাম না বদলালে caller-এর একই নামের মান মুছে যায় (α-renaming).
- Interprocedural constant propagation কখন নিরাপদ? যখন function-এর প্রতিটি call site জানা (whole program বা
static); বাইরে থেকে ডাকা গেলে নয়, যদি না LTO পুরো program দেখে।
৯ · AI-এর যুগে inlining আর interprocedural optimization
AI assistant-কে “এই function inline করে দাও” বা “-O2 কী inline করবে” জিজ্ঞেস করলে উত্তর নিশ্চিত স্বরে আসে, কিন্তু চোখে দেখে যাচাই কঠিন। প্রায়ই দেখা ভুল:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| হাতে inline করার সময় callee-র local variable বা temp-এর নাম না বদলানো, বা argument-কে দুবার মূল্যায়ন করা (macro-র মতো) | Side effect-ওয়ালা argument আর একই নামের variable দিয়ে আগে-পরে চালিয়ে আউটপুট মেলানো |
“C-র inline লিখলেই inline হবে” বা “recursive function কখনো inline হয় না” ধরনের সাধারণ দাবি | -Rpass=inline -Rpass-missed=inline দিয়ে নিজের compiler আর version-এ remark দেখা |
| বানানো flag বা threshold-এর সংখ্যা, এক compiler-এর নিয়ম অন্যটির বলে চালানো | GCC/Clang-এর নথি আর --help-এর আসল তালিকা মেলানো; না চললে “যাচাই করা হয়নি” |
| সব call site না দেখেই “এই parameter সবসময় 0” ধরে নেওয়া (বাইরে থেকে ডাকা, function pointer) | Function static কি না, address কোথাও নেওয়া হয়েছে কি না, দেখা |
| Stack-এর গভীরতা, tail call আর recursion-এর সীমা নিয়ে এক ভাষার নিয়ম সব ভাষায় চাপানো | ভাষার specification (Scheme, Python, C) আর সত্যিকারের run-এ সীমার কাছে পরীক্ষা |
AI-কে কাজে লাগাতে IR-এর নিয়ম আর যাচাইয়ের শর্ত আগেই বলে দিন:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১“Procedure integration” থেকে আজকের inliner: inlining কেন সবচেয়ে পুরোনো আর এখনো সবচেয়ে গুরুত্বপূর্ণ optimization-গুলোর একটি?
Function বা subroutine-এর ধারণা প্রায় প্রোগ্রামিংয়ের সমান পুরোনো, আর তার খরচও। ১৯৭০-এর দশকের শুরুতে Frances Allen আর John Cocke-এর “A Catalogue of Optimizing Transformations”-এ রূপান্তরের তালিকায় procedure integration, অর্থাৎ আজকের inlining-এর নাম আছে বলে জানা যায় (প্রকাশের সাল সূত্রভেদে ১৯৭১ বা ১৯৭২)। ১৯৭৭ সালে Robert Scheifler CLU ভাষার প্রসঙ্গে inline substitution নিয়ে একটি বিশ্লেষণ প্রকাশ করেন বলে উল্লেখ পাওয়া যায়, যেখানে প্রশ্নটি আজকের মতোই: কোন call inline করলে কতটা লাভ, আর কোড কতটা বাড়ে।
গুরুত্ব বেড়েছে ভাষার সঙ্গে সঙ্গে। Structured আর পরে object-oriented programming ছোট function লিখতে উৎসাহ দেয়: getter, setter, ছোট helper. C++-এর template library বা Java-র collection-এ একটি সাধারণ কাজ ডজনখানেক ছোট function পেরিয়ে যায়; inline ছাড়া এদের খরচ মূল কাজকে ছাপিয়ে যেত। C++-এর “zero-cost abstraction”-এর দাবি অনেকটা inliner-এর ওপর দাঁড়িয়ে: abstraction-এর স্তরগুলো compile-এর পরে মিলিয়ে যায়।
এই পর্বের মাপও একই কথা বলে। bazar.haat-এ inline একা চলা নির্দেশ ৭৪ থেকে ৮২-তে বাড়িয়েছিল; লাভ এসেছে পরের fold থেকে, যা inline ছাড়া argument দেখতে পেত না। Clang-এর first-এ price-এর দুটি কপি একটিতে মিলেছে, যা দুটি call থাকলে অসম্ভব। তাই inliner-কে প্রায়ই বলা হয় অন্য optimization-এর “enabler”: সে নিজে কম করে, কিন্তু বাকিদের দেখার জানালা বড় করে। বাস্তব compiler-এর pipeline-এ inliner তাই শুরুর দিকে আর বারবার চলে, আর তার নিয়ম বদলালে পুরো program-এর গতি আর আকার বদলায়।
মূল উপলব্ধি: inlining-এর মূল্য ডাকার খরচ বাঁচানোয় নয়, function-এর দেয়াল ভেঙে বাকি optimizer-কে পুরো ছবি দেখানোয়।
প্র ০২Self থেকে HotSpot আর V8: dynamic dispatch-এর ভাষায় JIT কীভাবে অনুমান করে inline করে, আর ভুল হলে কী হয়?
Smalltalk-এর উত্তরসূরি Self ভাষায় প্রায় প্রতিটি কাজ একটি message send, এমনকি যোগ বা variable পড়াও। Static compiler এখানে প্রায় কিছুই inline করতে পারে না, কারণ কোন method চলবে তা object-এর ওপর নির্ভর করে। Stanford-এ Craig Chambers, David Ungar আর পরে Urs Hölzle-এর কাজ (১৯৮৯–১৯৯২ সালের দিকের PLDI আর OOPSLA প্রবন্ধে) সমস্যাটি উল্টে দেয়: চলার সময় দেখা যাক কোন class আসছে। Polymorphic inline cache (ECOOP ১৯৯১) প্রতিটি call site-এ আসা class-গুলো মনে রাখে, আর optimizer সেই তথ্য দিয়ে অনুমান করে inline করে, সামনে একটি ছোট পরীক্ষা (guard) রেখে।
অনুমান ভুল হলে কী হবে? উত্তর deoptimization (Hölzle, Chambers আর Ungar, PLDI ১৯৯২-এর প্রবন্ধে, মূলত optimize করা কোড debug করার প্রসঙ্গে): optimize করা frame-কে সাধারণ, অ-optimize রূপের frame-এ রূপান্তর করে সেখান থেকে চালিয়ে যাওয়া। এই কৌশল পরে Java-র HotSpot VM-এ যায় (Self দলের কয়েকজন সেখানে কাজ করেছিলেন বলে জানা যায়), আর JavaScript engine-গুলোতেও একই চিন্তা দেখা যায়। পর্ব ৬১-এ এই tiered JIT-এর বিস্তারিত আছে।
এই পর্বের ভাষায়, JIT call graph-এর একটি অনিশ্চিত edge-কে profile দিয়ে নিশ্চিত বলে ধরে নেয়, আর ভুলের দাম দেয় guard আর deoptimization দিয়ে। Ahead-of-time compiler-এর পথ প্রমাণের: final class বা পুরো program-এ একটিই subclass দেখে devirtualization (পর্ব ০৮)। Haat IR v1-এ এই প্রশ্ন ওঠেই না, কারণ closure বাদ রেখে প্রতিটি call-এর লক্ষ্য জানা; Haat-এর পূর্ণ রূপে closure-এর call inline করতে হলে এই দুই পথের একটি লাগবে।
মূল উপলব্ধি: dynamic dispatch inlining-এর সবচেয়ে বড় বাধা; AOT compiler প্রমাণ দিয়ে, JIT অনুমান আর deoptimization দিয়ে সেটি পেরোয়।
প্র ০৩আলাদা compile, closed world আর LTO: পুরো program একসঙ্গে দেখা কি সবসময় ভালো?
C-র ফাইল-ভিত্তিক compile ১৯৭০-এর দশকের যন্ত্রের সীমা থেকে এসেছে: memory কম, তাই একবারে একটি ফাইল। এর বড় সুবিধা আজও আছে: একটি ফাইল বদলালে শুধু সেটিই আবার compile হয়, আর library আলাদা বিতরণ করা যায়। কিন্তু দাম এই পর্বে স্পষ্ট: অন্য ফাইলের function-এর দেহ অদেখা, তাই inline অসম্ভব, আর একটি non-static function-কে কে ডাকবে তা অজানা, তাই IPCP অসম্ভব।
LTO দুটির মাঝামাঝি পথ: compile-এর সময় IR রেখে link-এর সময় পুরো program optimize করা। পর্ব ৭৪-এর run-এ GCC আর Clang দুটিতেই LTO price আর delivery-কে main-এ মিলিয়ে দিয়েছে। দাম: link ধীর আর বেশি memory খায়, আর incremental build-এর সুবিধা কমে। LLVM-এর ThinLTO (CGO ২০১৭-এর প্রবন্ধ) এই দাম কমাতে প্রতিটি module-এর সারাংশ দেখে শুধু দরকারি function আমদানি করে; বড় প্রকল্পে এটি জনপ্রিয় বলে জানা যায়। কিছু compiler পুরোপুরি whole-program, যেমন Standard ML-এর MLton, যা পুরো program একসঙ্গে নিয়ে কাজ করে বলে পরিচিত।
তবে closed world-এর অনুমান ভাঙার উপায় অনেক: shared library-র function বাইরে থেকে ডাকা যায়, function pointer বা reflection দিয়ে যেকোনো function ডাকা যায়, আর plugin চলার সময় নতুন কোড আনে। তখন whole-program-এর দাবি ভুল হয়ে চুপচাপ ভুল কোড দেবে। তাই compiler-গুলো সতর্ক: shared library-তে export করা symbol, বা যার address নেওয়া হয়েছে, এমন function-এ IPCP সাধারণত হয় না। Haat IR v1 সহজ, কারণ একটি ফাইলই পুরো program আর function কোথাও মান হিসেবে যায় না; পূর্ণ Haat-এ closure এলে এই নিশ্চয়তা নিজে প্রমাণ করতে হবে।
মূল উপলব্ধি: পুরো program দেখলে optimizer অনেক বেশি পারে, কিন্তু সেই দেখা সত্যিই পুরো কি না, তা নিশ্চিত হওয়াই কঠিন অংশ; আলাদা compile, LTO আর ThinLTO সেই আপসের তিনটি বিন্দু।
প্র ০৪Inline-এর সীমা কীভাবে ঠিক হয়? হাতে লেখা cost, মাপা ফল আর machine learning — কোনটি কতটা বিশ্বাসযোগ্য?
প্রতিটি inliner-এর মূলে একটি অনুমান: এই call inline করলে কোড কত বাড়বে, আর কতটা কমবে। LLVM এটি একটি cost আর threshold দিয়ে প্রকাশ করে: অংশ ৪-এর remark-এ price-এর প্রথম call site-এর cost −15, threshold 225. Cost হিসাবে নির্দেশ গোনা হয়, আর argument ধ্রুবক হলে যে শাখা মুছে যাবে, তার ছাড় দেওয়া হয়; শেষ call site হলে বড় বোনাস। এই সংখ্যাগুলো বহু বছরের benchmark থেকে হাতে বসানো, তাই যুক্তিসংগত কিন্তু কোনো গাণিতিক সর্বোত্তম নয়।
এই পর্বের মাপ দেখায় সমস্যাটি কেন কঠিন। ৩,০০০টি এলোমেলো Haat program-এ সীমা ১০ থেকে ৮০ পর্যন্ত বাড়ালে চলা নির্দেশ ২১.১% থেকে ২৮.৩% কমে, কিন্তু স্থির কোড −২৮.৯% থেকে +১.৭%-এ যায়, আর সবচেয়ে বড় function ২৮৯ থেকে ৮৫৪ নির্দেশে। কোনটি ভালো, তা নির্ভর করে লক্ষ্যের ওপর: ফোনের app-এ আকার, server-এ গতি। আর বাস্তব CPU-তে বড় কোড instruction cache-এ না আঁটলে “কম নির্দেশ” আসলে ধীরও হতে পারে; আমাদের interpreter-এর গোনা এটি ধরে না, তাই এখানে কোনো সময়ের দাবি করা হয়নি।
নতুন পথ শেখা। MLGO (২০২১ সালের প্রবন্ধ) LLVM-এর inliner-এ “আকারের জন্য inline করব কি না” প্রশ্নটি reinforcement learning-এ শেখা একটি ছোট model-কে দেয়; প্রবন্ধে বড় codebase-এ কয়েক শতাংশ আকার কমার কথা বলা আছে। সতর্কতাও আছে: শেখা model কেন একটি সিদ্ধান্ত নিল, তা বোঝা কঠিন, আর প্রশিক্ষণের codebase থেকে অন্য ধরনের কোডে ফল আলাদা হতে পারে। Profile-guided optimization তৃতীয় পথ: আন্দাজের বদলে আগের run-এ মাপা call-এর সংখ্যা।
মূল উপলব্ধি: inline-এর সীমা একটি আপস, প্রমাণ নয়; হাতে লেখা cost, profile আর শেখা model সবই সেই আপসকে ভালো অনুমান করার চেষ্টা, আর প্রতিটির দাবি নিজের কোডে মেপে দেখতে হয়।
প্র ০৫Stack-এর গভীরতা কি একটি ভাষার semantics-এর অংশ? Scheme, Python, C আর Haat-এর চার রকম উত্তর।
Scheme-এর জন্ম (Guy Steele আর Gerald Sussman, ১৯৭৫) থেকেই tail call-এ stack না বাড়ানো তার পরিচয়ের অংশ; ভাষার standard (যেমন R5RS, ১৯৯৮) proper tail call বাধ্যতামূলক করে। ফলে Scheme-এ loop লেখা হয় recursion দিয়ে, আর একটি compiler tail call-এ frame না ফেললে সেটি ভুল বাস্তবায়ন। এখানে stack-এর গভীরতা আচরণের অংশ এক দিক থেকে: ভাষা কথা দেয় নির্দিষ্ট ধরনের call-এ stack বাড়বে না।
CPython উল্টো পথে। Guido van Rossum ২০০৯ সালের দিকে কয়েকটি blog লেখায় tail call elimination না করার পক্ষে যুক্তি দেন, প্রধানত traceback-এ প্রতিটি frame দেখানোর জন্য বলে জানা যায়। Python-এ recursion-এর একটি সীমা আছে, যা sys.setrecursionlimit দিয়ে বদলানো যায়, আর পার হলে RecursionError: অর্থাৎ সীমাটি আচরণের অংশ, কিন্তু সংখ্যাটি নির্দিষ্ট নয়। C-তে stack ফুরালে কী হবে, standard তা বলে না; বাস্তবে সাধারণত crash, আর optimizer যেকোনো সময় frame যোগ বা বাদ দিতে পারে (অংশ ৫-এ Clang fact-কে loop বানিয়েছে)।
Haat চতুর্থ পথ বেছেছে: ঠিক ১,০০০টি nested call-এর পরে একটি নির্ধারিত error, reference-এর দুই back end-এ একই (সিদ্ধান্ত ২৬)। এর ভালো দিক, একই program সবসময় একই আচরণ করে, আর test লেখা সহজ। দাম এই পর্বে দেখেছেন: inliner-কে depth নিয়ম মানতে হয়, যা recursion-এর পথে inline আটকায়, আর tail call optimization Haat-এ আচরণ বদলাত। ভাষা-নকশাকার এখানে বেছে নেন: নির্ধারিত সীমা (পূর্বানুমেয়, কিন্তু optimizer-এর হাত বাঁধা), proper tail call (গভীর recursion সম্ভব, কিন্তু traceback ছোট), বা অনির্ধারিত (optimizer স্বাধীন, programmer অনিশ্চিত)। পর্ব ০৬-এর আপসের তালিকায় এটিও একটি।
মূল উপলব্ধি: stack-এর গভীরতা “বাস্তবায়নের খুঁটিনাটি” না “আচরণ”, এই প্রশ্নের উত্তরই ঠিক করে inlining আর tail call optimization কতটা স্বাধীন।
অনুশীলন
প্রথমে নিজে হিসাব করুন বা লিখুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর সত্যিকারের run দিয়ে যাচাই করা।
-
নকশা ও বাস্তবায়ন — একমাত্র call site-এর নিয়ম: একটি function-কে পুরো program-এ মাত্র একবার ডাকা হলে, তাকে inline করলে কোড বাড়ে না (মূলটি পরে
pruneমোছে)।haat_inline.pyনা বদলে এমন একটি নিয়ম যোগ করুন: আকারের কারণে বাতিল হওয়া call site-ও inline হবে, যদি callee-র মোট call site একটি হয়। তারপর বলুন, LLVM-এর কোন remark-এ এই চিন্তা দেখা গেছে।import haat_inline as H old = H.why_not def why_not(mod, g, rec, deep, f, c, limit, depth_safe): w = old(mod, g, rec, deep, f, c, limit, depth_safe) sites = sum(i.kind == "call" and i.sym == c for fn in mod.funcs.values() for b in fn.blocks.values() for i in b) return None if w == "size" and sites == 1 else w H.why_not = why_not # inline_module এখন নতুন নিয়ম মানেশুধু আকারের কারণ উঠে যায়; recursion আর depth নিয়ম অটুট।
inline_modulemodule-এর global নামwhy_notডাকে, তাই বদলটি কাজ করে। লেখকের lab-এ ৩,০০৮টি program-এ (৮টি উদাহরণ, ৩,০০০টি এলোমেলো) সত্যিকারের run: inline করা call site ১০,০৪৩ থেকে ১০,৫৭৩, স্থির নির্দেশ ৩,৪৩,৯৪৮ থেকে ৩,৪০,০৩৮, চলা নির্দেশ ৭,২১,৪৯৩ থেকে ৭,১৯,৩৩০, অমিল ০. অর্থাৎ বেশি inline, অথচ কোড কম। অংশ ৪-এর remark-এstaticfunction-এর শেষ call site-এ cost −15015: সেই ১৫,০০০-এর বোনাস ঠিক এই চিন্তা। -
ভুল খুঁজুন আর প্রমাণ — কোন শর্টকাট নিরাপদ: দুইজন ছাত্র inliner-এ সময় বাঁচাতে চান। (ক) একজন একই caller-এ price-এর প্রতিটি কপির জন্য একই tag
price1ব্যবহার করেন (দুটি কপিইprice1.pলেখে)। (খ) অন্যজন callee-র temp-এর নম্বর বদলান না (rename=False-এর মতো)। bazar.haat-এ কোনটি ভুল আউটপুট দেয়, কী ছাপে, আর অন্যটি কেন নিরাপদ?(খ) ভুল।
rename=False-এ bazar ছাপে70,5000,3(সত্যিকারের run). প্রথম price-এর ফল<main>-এর t3-এ থাকে (936); দ্বিতীয় কপিতে price-এর নিজেরt3 = const 10একই নামে লেখে, তাই t3 = 10, আরfirst = t3 + t7= 10 + 60 = 70.(ক) নিরাপদ। লেখকের lab-এ ৩,০০৮টি program-এ প্রতিটি কপিতে একই tag দিয়ে চালানো হয়েছে: অমিল ০. প্রমাণের রূপরেখা:
- Callee-র প্রতিটি local নাম (parameter-সহ) ওই callee-র একবারের চলায় পড়ার আগে লেখা হয়: parameter-এ entry-র copy, variable-এ Haat-এর declaration-এর নিয়ম (সিদ্ধান্ত ১৬), আর temp lowering-এ।
- Recursive function inline হয় না, তাই একই callee-র দুটি কপির চলা কখনো একে অপরের ভেতরে থাকে না; একটি শেষ হলে (ফল caller-এর d-তে কপি হয়ে) তবেই অন্যটি শুরু।
- তাই দ্বিতীয় কপি
price1.pপড়ার আগে নিজেই লেখে; প্রথম কপির মান আর কারও দরকার নেই। caller-এর নিজের নাম (যেমন t3) কপির নামের সঙ্গে মেলে না, কারণ বিন্দুসহ নাম আর top-এর বড় temp নম্বর আলাদা। ∎
অর্থাৎ নাম বদলের আসল কাজ caller থেকে আলাদা রাখা, কপিগুলো একে অপর থেকে নয়; তবু আলাদা tag রাখা নিরাপদ অভ্যাস।
-
হিসাব — পরীক্ষার ধাঁচে Tarjan আর inline-এর সিদ্ধান্ত: একটি program-এর call graph:
main → a, e;a → b;b → c;c → a, d;dকাউকে ডাকে না;e → e, d. (ক) main থেকে DFS (callee-র ক্রমে) চালিয়ে প্রতিটি function-এর index/low আর SCC-গুলো bottom-up ক্রমে লিখুন। (খ) recursion আর depth নিয়মে কোন call site inline হবে?function index low কারণ d 4 4 callee নেই: SCC {d} c 3 1 c → a, a stack-এ b 2 1 c-এর low a 1 1 low = index: SCC {a, b, c} e 5 5 নিজেকে ডাকে; d আগেই শেষ, stack-এ নেই main 0 0 SCC {main} (ক) Bottom-up ক্রম: {d}, {a, b, c}, {e}, {main}. Recursive: a, b, c (তিনজনের SCC) আর e (নিজেকে ডাকে)। (খ) একটিও না। main → a, main → e আর SCC-র ভেতরের call: callee recursive. c → d আর e → d: d নিজে recursive নয়, কিন্তু caller c আর e recursive, তাই depth নিয়ম (খ শর্ত) আটকায়: d-এর frame গভীর recursion-এর ওপরে বসতে পারে। অংশ ২-এর JS ব্লকে
CALLSবদলে মেলানো (সত্যিকারের run). depth নিয়ম ছাড়া c → d আর e → d inline হতো। -
আউটপুট অনুমান — IPCP কী খুঁজে পায়: নিচের program কী ছাপে?
ipcpকোন তথ্য পায়? আর শেষ লাইনটি (print(fee(2, 2));) মুছে দিলে?fn fee(qty: Int, zone: Int) -> Int { if zone == 1 { return 40; } return 40 + qty * 10; } print(fee(3, 1)); print(fee(5, 1)); print(fee(2, 2));Reference-এ সত্যিকারের run:
40,40,60.ipcpকিছুই পায় না: qty তিন জায়গায় 3, 5, 2; zone 1, 1, 2; আর ফেরত মান 40 বা40 + qty * 10, এক নয়। একটি call site আলাদা হলেই তথ্য হারায়। Inline করলে কিন্তু প্রতিটি call site নিজের ধ্রুবক পায়: inline → prune → optimize-এর পরে<main>-এ শুধু ধ্রুবক ছাপা, চলা নির্দেশ ৩২ থেকে ৭, call ৩ থেকে ০ (সত্যিকারের run). শেষ লাইন মুছলে zone দুই জায়গাতেই 1: রাউন্ড ১-এzone = const 1, fee নামেreturn 40-এ, রাউন্ড ২-এ ফেরত মান 40; qty (3 আর 5) তখনো ⊥. আউটপুট40,40; চলা নির্দেশ ২০ থেকে ১৪, call ২টিই থাকে। zone = 1-এর একটি আলাদা কপি (function specialization) প্রথম program-এও দুটি call site-কে লাভ দিত।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমThree-address IR-এ একটি call site d = call f(a, b) inline করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Call graph-এর SCC দেখে নিশ্চিত হওয়া যে f recursive নয়
- Call-এর block দুই ভাগ করা: call-এর পরের অংশ একটি continuation block-এ
- f-এর দেহ কপি করে তার temp, variable আর block-এর নতুন নাম দেওয়া
- Call-এর জায়গায় parameter-এ argument-এর copy আর কপির entry-তে jump বসানো
- কপির প্রতিটি return-কে d-তে copy আর continuation-এ jump বানানো
- Optimizer চালিয়ে ধ্রুবক argument-এর সুবিধা নেওয়া আর differential test চালানো
একটি call graph: main → f, g; f → h; h → f; g → g. কোন function-গুলো recursive?
- শুধু f আর h
- f, h আর g
- main, f, h আর g
- শুধু g
একটি inliner callee-র variable আর temp-এর নাম বদলায় না। কোন অবস্থায় এটি ভুল আউটপুট দিতে পারে?
- কখনো না, কারণ IR-এ প্রতিটি নাম আলাদা
- শুধু callee-তে একাধিক return থাকলে
- যখন caller-এর একটি নাম callee-তেও আছে, আর caller call-এর পরে সেই নামের আগের মান পড়ে
- শুধু callee কোনো global পড়লে
একটি ভাষায় ১,০০০টির বেশি nested call একটি নির্ধারিত stack overflow error. fn start(n: Int) -> Int { return count(n); }, যেখানে count recursive. main-এ start inline করা কেন বিপজ্জনক?
- একটি frame কমে, তাই সীমার কাছের program-এ error আসা-না-আসা বদলাতে পারে
- start recursive, তাই inline শেষ হয় না
- count-এর ফল বদলে যায়
- Inline নতুন frame যোগ করে, তাই আগেই overflow হয়
একটি function tax(p: Int, rate: Int) তিনটি call site-এ ডাকা হয়: tax(100, 5), tax(250, 5), tax(80, 5), আর function-টি অন্য কোথাও থেকে ডাকা যায় না। Interprocedural constant propagation কী বলবে?
- p আর rate দুটিই ধ্রুবক
- কোনোটিই ধ্রুবক নয়, কারণ p আলাদা
- শুধু p ধ্রুবক
- শুধু rate = 5
C-তে একটি non-static function scale(int k) একটি ফাইলের সব call-এ k = 3 পায়। LTO ছাড়া compiler কেন k = 3 ধরে নিতে পারে না?
- C-তে parameter বদলানো যায় বলে
- অন্য ফাইল বা library থেকে অন্য মানে ডাকা হতে পারে, যা compiler দেখে না
- C-তে interprocedural optimization নিষিদ্ধ
- -O2 শুধু একটি function-এর ভেতরে কাজ করে
Clang 22-এর -Rpass=inline-এ একটি remark: 'price' inlined into 'first' with (cost=-15015, threshold=225). এর সবচেয়ে যুক্তিসংগত ব্যাখ্যা কোনটি?
- Cost threshold-এর চেয়ে কম বলে inline হয়নি
- Inline-এর পরে program ১৫,০১৫ ns দ্রুত হয়েছে
- Inline-এ কোড কমবে বলে অনুমান, বিশেষ করে এটি static function-এর শেষ call site বলে
- price recursive, তাই বিশেষ cost
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Call graph আর SCC: Tarjan-এর একটি DFS-এ SCC; একাধিক function বা self-loop মানে recursive; bottom-up ক্রমে callee আগে।
- Inline-এর চার কাজ: block ভাগ, callee-র নাম বদল (temp, variable, block), parameter-এ copy, প্রতিটি return থেকে continuation-এ jump; প্রতিটি নির্দেশের
posঅক্ষত। - লাভ পরে আসে: inline একা কাজ সামান্য বাড়ায়; ধ্রুবক argument দেখে optimize করলে bazar-এ ৭৪ → ৪৬, call ৩ → ০.
- সীমা: আকারের সীমা code growth আটকায়; recursive callee বাদ; Haat-এ stack-এর গভীরতা আচরণ, তাই recursion-এর পথে depth নিয়ম।
- IPCP আর closed world: সব call site একমত হলে parameter ধ্রুবক, সব return একমত হলে ফল ধ্রুবক (call থাকে); সব call site জানা থাকতে হবে, যা আলাদা compile-এ LTO ছাড়া মেলে না।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৬৮ · LLVM IR — সত্যিকারের clang আর opt দিয়েপরবর্তী পর্ববাস্তব একটি SSA IR, যার ওপর LLVM-এর inliner-এর মতো pass চলে।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ৬৫ · Optimizationএই কোর্সেfold, copy propagation, LVN আর DCE, যা inline-এর পরে আসল কাজ করে।
- পর্ব ৩২ · Recursion আর tail callএই কোর্সেTail call আর ভাষাভেদে stack-এর নিয়ম।
- পর্ব ৭৪ · Linking আর loadingএই কোর্সেLTO-র সত্যিকারের run: ফাইলের দেয়াল পেরিয়ে inline.
- DSA · পর্ব ৪৬ · SCC আর bridgeপাশের ট্র্যাকTarjan আর Kosaraju-র অ্যালগরিদম বিস্তারিত।