এই পর্বে যা শিখবেন
- Live range আর interference graph কী, liveness থেকে কীভাবে হাতে আর কোডে বানাবেন, আর কেন register allocation একটি graph colouring সমস্যা
- Chaitin-এর simplify/select, spill cost আর spill code, Briggs-এর optimistic colouring, পরীক্ষার ধাঁচে ধাপে ধাপে
- Copy মুছে ফেলার coalescing (Briggs-এর রক্ষণশীল নিয়ম) আর JIT-এর প্রিয় linear scan
- RISC-V-এর caller-saved আর callee-saved register: call পেরোনো মান কোথায় রাখবেন, আর সত্যিকারের Clang
-O0বনাম-O2কী করে - নিজের allocator চালিয়ে যাচাই: differential test, আর একটি জেনেশুনে বসানো ভুল ধরা
১ · অসীম নাম, গোনা register — সমস্যাটি কী
একটি রেস্তোরাঁর রান্নাঘরে চারটি চুলা। দুপুরে অর্ডার আসে বিশটি পদের। একটি পদ চুলায় থাকে চড়ানো থেকে নামানো পর্যন্ত; যে দুটি পদ একই সময়ে রান্না হচ্ছে, তারা এক চুলায় বসতে পারে না। কিন্তু ভাত নামানোর পরে সেই চুলায় ডাল চড়ানো যায়। চুলা কম পড়লে কোনো একটি আধা-রান্না পদ নামিয়ে পাশে রাখতে হয়, পরে আবার গরম করে চুলায় তুলতে হয়। এতে সময় নষ্ট, তাই রাঁধুনি এমন পদ নামান, যা অনেকক্ষণ আর ছোঁয়া হবে না।
Compiler-এর back end ঠিক এই সমস্যায় পড়ে। চুলা হলো CPU-র register, পদ হলো program-এর মান। পর্ব ৬২-এর Haat IR যত খুশি নাম বানায় (t1, t2, p, vat …), কিন্তু RISC-V-এর মতো CPU-তে integer register মাত্র ৩২টি, যার কয়েকটি (zero, sp, ra, gp, tp) সাধারণ কাজে লাগে না। কোন নাম কোন register পাবে, আর যেগুলো পাবে না সেগুলো memory-র কোন ঘরে যাবে, এই সিদ্ধান্তের নাম register allocation. নামানো পদকে compiler-এর ভাষায় বলে spill: মানটি stack-এর একটি ঘরে লেখা (store), আবার লাগলে পড়া (load).
কেন এত চেষ্টা? Register একই cycle-এ পড়া যায়; memory-তে যেতে অন্তত একটি load, cache-এ না থাকলে অনেক বেশি সময় (Computer Architecture কোর্সের পর্ব ৪৪)। পর্ব ৭১-এর Haat frame layout সবচেয়ে সরল পথ নিয়েছে: প্রতিটি IR নামের একটি stack slot (frame-এর ধারণা পর্ব ৩০-এ); Clang-এর -O0-ও প্রায় তাই করে (অংশ ৭)। এই পর্ব সেই slot-গুলোর বেশিরভাগকে register-এ তোলে।
ইনপুট: একটি function-এর IR (Haat IR, CFG রূপে) আর k টি register-এর তালিকা। আউটপুট: প্রতিটি নামের জন্য একটি register বা একটি stack slot, আর slot-এ যাওয়া নামের জন্য store/load নির্দেশ, এমনভাবে যে (১) একই মুহূর্তে বেঁচে থাকা দুটি মান কখনো একই register-এ না থাকে, আর (২) নতুন কোড চালালে আগের মতোই আউটপুট আসে। লক্ষ্য: যত কম store/load, বিশেষ করে loop-এর ভেতরে।
“বেঁচে থাকা” মানে পর্ব ৬৪-এর liveness: একটি নাম একটি বিন্দুতে live, যদি সেখান থেকে কোনো পথে তার বর্তমান মান পরে পড়া হয়। এই পর্বের কোড পর্ব ৬২-এর haat_front.py আর haat_ir.py, আর পর্ব ৬৪-এর haat_dfa.py হুবহু নেয়; নতুন সব কোড আলাদা ফাইল haat_ra.py-তে, যা পর্ব ৭২-এর RISC-V back end ব্যবহার করতে পারবে।
২ · Live range আর interference graph
চলমান উদাহরণ একটি নতুন বাজারঘর function, bill: দাম, ১/২০ অংশ VAT, তারপর coupon-এর ছাড়। সঙ্গে copy-র উদাহরণ হিসেবে best, যা অংশ ৫-এ লাগবে। Reference implementation এটি চালালে ছাপে 1185 আর 1092 (সত্যিকারের run).
// বাজারঘর: একটি অর্ডারের বিল, আর দুটি দামের বড়টি
fn bill(qty: Int, unit: Int, coupon: Int) -> Int {
let p = qty * unit;
let vat = p / 20;
let pay = p + vat;
return pay - coupon * qty;
}
fn best(a: Int, b: Int) -> Int {
var m = a;
if b > m { m = b; }
return m;
}
print(bill(3, 400, 25));
print(best(bill(2, 520, 0), 1000));
bill-এর Haat IR একটিই block, সাতটি নির্দেশ। প্রতিটি নির্দেশের পরে কোন নাম live, তা haat_dfa.py-র analyze থেকে (নিচের প্রথম Python ব্লক এটি ছাপে):
| # | নির্দেশ | পরে live | কয়টি |
|---|---|---|---|
| ০ | p = qty * unit | coupon, p, qty | ৩ |
| ১ | t1 = const 20 | coupon, p, qty, t1 | ৪ |
| ২ | vat = p / t1 | coupon, p, qty, vat | ৪ |
| ৩ | pay = p + vat | coupon, pay, qty | ৩ |
| ৪ | t2 = coupon * qty | pay, t2 | ২ |
| ৫ | t3 = pay - t2 | t3 | ১ |
| ৬ | return t3 | — | ০ |
একটি নামের live range হলো program-এর যে বিন্দুগুলোতে সে live. coupon-এর live range শুরু থেকে নির্দেশ ৪ পর্যন্ত লম্বা, অথচ মাঝের তিনটি নির্দেশে তাকে কেউ ছোঁয় না: রান্নাঘরের সেই পদ, যা চুলায় বসে আছে কিন্তু নাড়া হচ্ছে না। নির্দেশ ১ আর ২-এর পরে চারটি নাম একসঙ্গে live; এই সংখ্যাকে বলে register pressure. তিনটি register থাকলে কোথাও না কোথাও একজনকে নামতেই হবে।
দুটি নাম x আর y শত্রু (interfere করে), যদি কোনো নির্দেশ x লেখে আর সেই নির্দেশের ঠিক পরে y live থাকে (y ≠ x). ব্যতিক্রম: নির্দেশটি copy x = y হলে x আর y-এর মধ্যে edge হয় না, কারণ সেই মুহূর্তে দুজনের মান একই। Function-এর শুরুতে সব parameter একসঙ্গে লেখা হয়, তাই তারা পরস্পরের শত্রু। Interference graph-এ প্রতিটি নাম একটি node, প্রতিটি শত্রু-জোড়া একটি edge.
কেন “লেখার মুহূর্তে”? এক register-এ দুটি নাম থাকলে বিপদ শুধু তখন, যখন একজনের লেখা অন্যজনের এখনো-দরকারি মান মুছে দেয়। vat = p / t1-এ t1 শেষবার পড়া হয়, পরে live নয়; তাই vat আর t1 শত্রু নয়, vat t1-এর register-এই বসতে পারে।
1entry: qty, unit, coupon2p = qty * unit3t1 = const 204vat = p / t15pay = p + vat6t2 = coupon * qty7t3 = pay - t28return t3
| লেখে | |
| পরে live | |
| নতুন edge | |
| মোট edge |
- Entry. Call-এর মুহূর্তে তিনটি parameter একসঙ্গে লেখা হয়, তাই তারা পরস্পরের শত্রু: তিনটি edge. লক্ষ করুন, entry-র পরে unit-ও live, কারণ নির্দেশ ০ তাকে পড়বে।
- p লেখা হলো. নির্দেশের পরে coupon আর qty live, তাই p–coupon আর p–qty. unit এখানে শেষবার পড়া হলো, তাই p আর unit শত্রু নয়: p চাইলে unit-এর register নিতে পারে।
- t1 লেখা হলো. পরে live coupon, p, qty: তিনটি নতুন edge. এখানে চারটি নাম একসঙ্গে বেঁচে, এই function-এর সর্বোচ্চ register pressure.
- vat লেখা হলো. t1 এই নির্দেশেই শেষবার পড়া হলো, তাই পরে live নয়; vat–t1 edge নেই। নতুন edge vat–coupon, vat–p, vat–qty.
- pay লেখা হলো. p আর vat দুজনেই এখানে শেষ। পরে live coupon আর qty, কারণ নির্দেশ ৪ তাদের গুণ করবে।
- t2 লেখা হলো. coupon আর qty এখানে শেষ; পরে live শুধু pay. একটি edge: t2–pay.
- t3 লেখা হলো. পরে live শুধু t3 নিজে; নিজের সঙ্গে edge হয় না। t3 একটি একা node.
- ফল. ৯টি node, ১৪টি edge. qty আর coupon-এর degree সবচেয়ে বেশি (৬টি করে), কারণ তাদের live range সবচেয়ে লম্বা। p, t1, coupon, qty পরস্পরের শত্রু: চার node-এর একটি clique, তাই তিন রঙে এই graph রং করা অসম্ভব।
ছবি ৭০.১ — bill-এর interference graph, তিন রঙে (k = 3)
প্রতিটি বৃত্তে নাম আর প্রথম রাউন্ডে পাওয়া register
প্রশ্নটি এখন খাঁটি গণিতের: প্রতিটি node-কে k টি রঙের একটি দেওয়া, যাতে কোনো edge-এর দুই প্রান্তে একই রং না পড়ে। এটিই graph colouring (তত্ত্ব ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৬৩-এ): সবচেয়ে কম রঙের সংখ্যা chromatic number χ(G), আর একটি clique (সবাই সবার শত্রু) যত বড়, অন্তত তত রং লাগে। bill-এর চার node-এর clique-এর জন্য χ ≥ ৪, তাই k = ৩-এ একটি spill অনিবার্য। সাধারণ graph-এ “k রঙে সম্ভব কি না” NP-complete (k ≥ ৩), আর Chaitin ও সহকর্মীরা ১৯৮১ সালে দেখান যে যেকোনো graph কোনো program-এর interference graph হতে পারে। তাই compiler একটি দ্রুত heuristic চালায় (NP-কঠিন সমস্যা বাস্তবে: DSA কোর্সের পর্ব ৬৫).
এবার কোডে। haat_ra.py-র interference ঠিক সংজ্ঞা ৭০.২ অনুসরণ করে: প্রতিটি নির্দেশের “পরে live” set (পর্ব ৬৪-এর points) নিয়ে লেখা নামের সঙ্গে edge, copy-র উৎস বাদ। @x ধরনের global memory-তেই থাকে, আর $x নামগুলো (অংশ ৩) stack slot; দুটিই graph-এর বাইরে।
# ধাপ ১: bill-এর interference graph — পর্ব ৬৪-এর liveness থেকে
from haat_ra import * # interference, color, allocate … (+ haat_dfa, haat_ir)
fn = compile_ir(open("bill.haat", encoding="utf-8").read()).funcs["bill"]
sol, pts = analyze(fn, LIVENESS)
for i, ins in enumerate(fn.blocks["B0"]):
print(f"{str(ins):18} পরে live: {', '.join(sorted(pts['B0', i][1])) or '—'}")
G, moves = interference(fn)
edges = sorted((a, b) for a in G for b in G[a] if a < b)
print(len(G), "টি node,", len(edges), "টি edge, copy-জোড়া:", moves or "নেই")
for x in G:
print(f" {x:6} degree {len(G[x])}: {' '.join(sorted(G[x])) or '—'}")
print("একসঙ্গে সবচেয়ে বেশি live:", max(len(after) for _, after in pts.values()))আসল আউটপুট (ব্রাউজারের Python):
p = qty * unit পরে live: coupon, p, qty
t1 = const 20 পরে live: coupon, p, qty, t1
vat = p / t1 পরে live: coupon, p, qty, vat
pay = p + vat পরে live: coupon, pay, qty
t2 = coupon * qty পরে live: pay, t2
t3 = pay - t2 পরে live: t3
return t3 পরে live: —
9 টি node, 14 টি edge, copy-জোড়া: নেই
qty degree 6: coupon p pay t1 unit vat
unit degree 2: coupon qty
coupon degree 6: p pay qty t1 unit vat
p degree 4: coupon qty t1 vat
t1 degree 3: coupon p qty
vat degree 3: coupon p qty
pay degree 3: coupon qty t2
t2 degree 1: pay
t3 degree 0: —
একসঙ্গে সবচেয়ে বেশি live: 4
“পরে live” কলামটি ওপরের টেবিলের সঙ্গে হুবহু এক, আর degree-গুলো stepper-এর শেষ ধাপের সঙ্গে: qty আর coupon ৬, t3 ০। bill-এ কোনো copy নেই, তাই copy-জোড়ার তালিকা খালি। শেষ লাইনের ৪ হলো register pressure-এর সর্বোচ্চ; তিনটি register-এ কাজ চালাতে হলে কাউকে নামতে হবে।
৩ · Chaitin-এর simplify/select, spill আর Briggs-এর আশা
১৯৭০-এর দশকের শেষে IBM-এর গবেষণাগারে, পরীক্ষামূলক compiler-গুলোর কাজে (এর মধ্যে IBM 801 প্রকল্পের PL.8 compiler), Gregory Chaitin আর সহকর্মীরা graph colouring দিয়ে register allocation চালু করেন; ১৯৮১ সালের প্রবন্ধ আর ১৯৮২ সালের “Register allocation & spilling via graph coloring” প্রবন্ধে পদ্ধতিটি দাঁড়ায় (তারিখগুলো প্রকাশের, কাজ আরও আগের)। মূল কৌশলটি একটি সরল পর্যবেক্ষণ, যার শিকড় খুঁজলে পাওয়া যায় ১৮৭৯ সালে চার রঙের সমস্যায় Alfred Kempe-র যুক্তিতে:
Graph G-তে একটি node n-এর degree < k হলে: G − n যদি k রঙে রং করা যায়, তবে G-ও যায়।
প্রমাণ: (১) G − n-এর একটি k-রং নিন। (২) n-এর প্রতিবেশী k-এর কম, তাই তারা মিলে বড়জোর k − ১টি রং ব্যবহার করে। (৩) অন্তত একটি রং বাকি থাকে; সেটি n-কে দিন। কোনো edge-এর দুই প্রান্ত একই রঙের হয় না। ∎
এই উপপাদ্য থেকেই অ্যালগরিদম। Degree < k এমন node বারবার সরিয়ে একটি stack-এ রাখুন (simplify); শেষে stack থেকে উল্টো ক্রমে তুলে প্রত্যেককে প্রতিবেশীদের না-নেওয়া প্রথম রং দিন (select). উপপাদ্যের কারণে এভাবে সরানো প্রতিটি node রং পাবেই। আটকে গেলে, অর্থাৎ বাকি সবার degree ≥ k হলে, কাউকে spill-এর প্রার্থী করতে হয়।
allocate)
- Build: liveness থেকে interference graph; সম্ভব হলে copy-র দুই প্রান্ত মেলানো (অংশ ৫)।
- Simplify: degree < k এমন node সরিয়ে stack-এ; প্রতিবেশীদের degree এক কমে।
- Spill-এর প্রার্থী: আটকে গেলে যার spill cost ÷ degree সবচেয়ে কম, তাকে সরানো। Chaitin তাকে তখনই spill-এর তালিকায় রাখেন; Briggs তাকেও stack-এ রাখেন, হয়তো রং পাবে এই আশায়।
- Select: stack থেকে উল্টো ক্রমে রং। Briggs-এ যে প্রার্থী তখনো রং পায় না, সেটিই সত্যিকারের spill.
- Spill code আর আবার: spill হলে প্রতিটি লেখার পরে store, প্রতিটি পড়ার আগে load বসিয়ে ধাপ ১ থেকে আবার। কোনো spill না থাকলে নামগুলো register-এর নামে বদলে শেষ।
এখানে spill cost = লেখা + পড়ার সংখ্যা, loop-এর ভেতরে ১০ গুণ, parameter-এর entry-র লেখাসহ; ÷ degree, কারণ বেশি শত্রুওয়ালা node সরালে graph বেশি হালকা হয়। একটি প্রচলিত ধাঁচের সরল সূত্র; বাস্তব compiler আরও পরিমার্জিত। নিচের প্রতিটি মান lab-এ color-এর trace থেকে।
1simplify: degree < 3?2আটকে গেলে: cost ÷ degree3আবার simplify4select: উল্টো ক্রমে রং
| stack | |
| বাকি (degree) | |
| রং |
- শুরু. ছবি ৭০.১-এর graph, k = ৩. Node-গুলো তালিকার ক্রমে দেখা হয়, আর প্রথম যে node-এর degree < ৩, সে সরে।
- unit. Degree ২: সরিয়ে stack-এ। তার দুই প্রতিবেশী qty আর coupon-এর degree ৬ থেকে ৫.
- t2. Degree ১: সরল। pay-এর degree ৩ থেকে ২.
- pay. এখন degree ২: সরল। qty আর coupon নামল ৪-এ।
- t3, তারপর আটকে যাওয়া. t3-এর degree ০, সরল। বাকি পাঁচজনের degree ৪, ৪, ৪, ৩, ৩: কেউ ৩-এর কম নয়। Simplify আর এগোতে পারে না।
- Spill-এর প্রার্থী. cost ÷ degree: qty ৩/৪, coupon ২/৪, p ৩/৪, t1 ২/৩, vat ২/৩. সবচেয়ে কম coupon-এর (০.৫): কম ব্যবহার, অনেক শত্রু। Briggs তাকেও stack-এ রাখেন।
- আবার simplify. coupon সরতেই qty আর p নামল ৩-এ, t1 আর vat ২-এ। এরপর t1, qty, p, vat এক এক করে সরে; graph খালি।
- Select শুরু. Stack-এর ওপর থেকে: vat পায় r0, p পায় r1 (vat-এর r0 বাদ), qty পায় r2 (r0, r1 দুটিই প্রতিবেশীর), t1 পায় r0 (p r1, qty r2, আর vat শত্রু নয়)।
- coupon-এর পালা. রঙিন প্রতিবেশী qty r2, p r1, t1 r0, vat r0: তিনটি রংই নেওয়া। Briggs-এর আশা এখানে পূরণ হলো না; coupon সত্যিকারের spill. চার node-এর clique থাকায় এটি অনিবার্যই ছিল।
- বাকিরা আর দ্বিতীয় রাউন্ড. t3 r0, pay r0, t2 r1, unit r0. তারপর coupon-এর spill code বসিয়ে graph আবার বানানো হয়; এবার ১০টি node-এর সবাই রং পায়। মোট দুই রাউন্ড, একটি spill.
Spill code বসানোর নিয়ম যান্ত্রিক। Spill করা নাম x-এর জন্য stack-এ একটি ঘর, এখানে লেখা হয় $x. প্রতিটি লেখার পরে store $x = x~n, প্রতিটি পড়ার ঠিক আগে load x~n = $x, যেখানে x~n একটি নতুন, খুব ছোট live range-এর নাম। এই ছোট নামগুলো আর spill করা যায় না (cost অসীম), নইলে চক্র কখনো থামত না। Parameter spill হলে function-এ ঢুকেই store. bill-এর দ্বিতীয় রাউন্ডের IR:
fn bill(qty, unit, coupon~1):
B0:
$coupon = coupon~1 # store: ঢুকেই stack-এ
p = qty * unit
t1 = const 20
vat = p / t1
pay = p + vat
coupon~2 = $coupon # load: ব্যবহারের ঠিক আগে
t2 = coupon~2 * qty
t3 = pay - t2
return t3
coupon~1 বাঁচে শুধু প্রথম নির্দেশ পর্যন্ত, coupon~2 শুধু দুটি নির্দেশ। ভিড়ের অংশে এখন তিনজন live: একটি store আর একটি load-এর দামে চার register-এর প্রয়োজন তিনে নামল।
Chaitin আর Briggs-এর পার্থক্য দেখতে একটি বৃত্ত ভাবুন, a–b–c–d–a, আর k = ২. সবার degree ২, তাই simplify শুরুতেই আটকায়, আর Chaitin একজনকে তখনই spill করেন। অথচ বৃত্তটি দুই রঙেই হয় (a, c এক রং; b, d আরেক)! Preston Briggs ও সহকর্মীরা (Keith Cooper, Linda Torczon প্রমুখ; ১৯৮৯ আর ১৯৯৪ সালের প্রবন্ধে) তাই আনেন optimistic colouring: প্রার্থীকে stack-এ রাখা হয়, কারণ select-এ তার প্রতিবেশীরা হয়তো একই রং নেবে। উপপাদ্য ৭০.৩ যথেষ্ট শর্ত, প্রয়োজনীয় নয়।
// Interference graph-এ k রং: Chaitin (আটকে গেলে সঙ্গে সঙ্গে spill) বনাম Briggs (আশায় stack-এ রাখা)
function colour(edges, k, cost, optimistic) {
const G = {};
for (const [a, b] of edges) { (G[a] ??= new Set()).add(b); (G[b] ??= new Set()).add(a); }
const deg = {}, left = Object.keys(G), stack = [], spill = [];
for (const x of left) deg[x] = G[x].size;
while (left.length) {
let x = left.find(y => deg[y] < k), stuck = !x;
if (stuck) x = left.reduce((m, y) => cost[y] / deg[y] < cost[m] / deg[m] ? y : m);
left.splice(left.indexOf(x), 1);
for (const n of G[x]) if (left.includes(n)) deg[n]--;
if (stuck && !optimistic) spill.push(x); else stack.push(x);
}
const reg = {};
for (const x of stack.reverse()) { // select: প্রতিবেশীর না-নেওয়া প্রথম রং
const used = new Set([...G[x]].map(n => reg[n]));
const r = [...Array(k).keys()].find(c => !used.has(c));
if (r === undefined) spill.push(x); else reg[x] = r;
}
return Object.keys(G).map(x => `${x}:${x in reg ? "r" + reg[x] : "spill"}`).join(" ") + ` → spill ${spill.length}`;
}
// ১) চারটি নামের বৃত্ত a–b–c–d–a, k = 2: প্রত্যেকের degree 2, কেউ k-র কম নয়
const square = [["a", "b"], ["b", "c"], ["c", "d"], ["d", "a"]];
const one = { a: 1, b: 1, c: 1, d: 1 };
console.log("বৃত্ত, Chaitin:", colour(square, 2, one, false));
console.log("বৃত্ত, Briggs: ", colour(square, 2, one, true));
// ২) bill-এর graph (১৪টি edge), k = 3; খরচ = লেখা + পড়া
const bill = [["qty","unit"],["qty","coupon"],["unit","coupon"],["p","coupon"],["p","qty"],["t1","p"],["t1","coupon"],
["t1","qty"],["vat","p"],["vat","coupon"],["vat","qty"],["pay","coupon"],["pay","qty"],["t2","pay"]];
const cost = { qty: 3, unit: 2, coupon: 2, p: 3, t1: 2, vat: 2, pay: 2, t2: 2 };
console.log("bill, Briggs:", colour(bill, 3, cost, true));
console.log("bill, k = 4: ", colour(bill, 4, cost, true));আসল আউটপুট (ব্রাউজারের JavaScript):
বৃত্ত, Chaitin: a:spill b:r0 c:r1 d:r0 → spill 1
বৃত্ত, Briggs: a:r1 b:r0 c:r1 d:r0 → spill 0
bill, Briggs: qty:r2 unit:r0 coupon:spill p:r1 t1:r0 vat:r0 pay:r0 t2:r1 → spill 1
bill, k = 4: qty:r3 unit:r0 coupon:r2 p:r1 t1:r0 vat:r0 pay:r1 t2:r0 → spill 0
প্রথম দুই লাইন বৃত্তের গল্প: Chaitin a-কে spill করেছেন, অথচ Briggs একই graph দুই রঙে মিটিয়েছেন। তৃতীয় লাইনের রং Python-এর stepper-এর সঙ্গে হুবহু এক (qty r2, p r1, coupon spill …); t3-এর কোনো edge নেই বলে এই তালিকায় সে আসেনি। k = ৪ দিলে coupon-ও রং পায়, কারণ তখন clique-টি আর বাধা নয়। নিজের edge-তালিকা বসিয়ে চালিয়ে দেখুন।
৪ · চালিয়ে যাচাই — register-এর নামে লেখা IR
একটি allocator-এর ফল ঠিক কি না, শুধু graph দেখে বলা যায় না: liveness-এ ভুল, spill code-এ ভুল বা নাম বদলে ভুল, সবই চুপচাপ ভুল আউটপুট দেয়। তাই এখানে allocation-এর পরে প্রতিটি function নতুন করে লেখা হয়, যেখানে প্রতিটি নাম একটি register-এর নাম (r0, r1, r2) বা একটি stack slot ($coupon), আর সেই কোড পর্ব ৬২-এর run_ir-এ, কোনো বদল ছাড়াই, চালানো হয়।
এটি কেন ন্যায্য পরীক্ষা? run_ir প্রতিটি call-এর জন্য নামের একটি আলাদা ঘর-তালিকা (env) রাখে। নাম যখন r0, r1, r2, তালিকাটি তখন একটি তিন-ঘরের register file: দুটি মান একই register পেলে পরেরটি আগেরটিকে মুছে দেয়, যন্ত্রের মতোই। সরলীকরণ একটি: প্রতিটি call নিজের register file পায়, যেন ডাকা function সব register ফিরিয়ে দেয়; অংশ ৭ এই ফাঁক বন্ধ করে। আর machine_check যন্ত্রের নিয়ম দেখে: প্রতিটি operand একটি register, stack slot ছোঁয় শুধু load/store (r0 = $x, $x = r0).
def allocate(fn, regs, method="briggs", callee_saved=(), coalescing=True):
spilled = [] # method: "briggs", "chaitin" বা "linear"
for rnd in range(1, 50):
G, moves = interference(fn); cost = spill_cost(fn)
# … call পেরোনো মানের শর্ত (অংশ ৭), linear scan (অংশ ৬), coalescing (অংশ ৫)
colour, sp = color(G, len(regs), cost, regs, method == "briggs", allowed)
if not sp: break
spilled += sp; fn = spill_code(fn, sp) # store/load বসিয়ে আবার গোড়া থেকে
new, removed = apply_regs(fn, colour) # নাম -> register; r1 = r1 ধরনের copy মুছে যায়
return Allocation(new, colour, spilled, rnd, len(moves), removed)সহায়ক module haat_ra.py পুরোটা দেখুন (এই পর্বের সব নতুন কোড; পর্ব ৭২ এটি হুবহু নিতে পারে)
# haat_ra.py — পর্ব ৭০: Haat IR-এর register allocation — interference graph, Chaitin/Briggs, coalescing, linear scan.
# লাগে পর্ব ৬২-এর haat_ir.py আর পর্ব ৬৪-এর haat_dfa.py, হুবহু। পর্ব ৭২ এই ফাইলটি হুবহু ব্যবহার করতে পারে।
# Register শুধু একটি নাম ("r0", "t0", "s1" …); "$x" = x-এর stack slot (spill); "@x" = global, allocation-এর বাইরে।
import sys
from dataclasses import dataclass, replace
from haat_dfa import *
def live_across_calls(fn): # পর্ব ৬৪-এর অনুশীলনের উত্তর, হুবহু
_, pts = analyze(fn, LIVENESS)
return {(b, i): pts[b, i][1] - set(defs(ins)) for b, body in fn.blocks.items()
for i, ins in enumerate(body) if ins.kind == "call"}
def local(x): return x[0] not in "@$" # register চাইতে পারে এমন নাম
def interference(fn): # G: নাম -> প্রতিবেশী; moves: copy-জোড়া (dst, src)
_, pts = analyze(fn, LIVENESS)
G, moves = {}, []
def edge(a, b):
if a != b: G[a].add(b); G[b].add(a)
entry = [x for x in dict.fromkeys(fn.params + sorted(pts["B0", 0][0])) if local(x)]
for x in entry: G.setdefault(x, set())
for a in entry: # entry-তে সব parameter একসঙ্গে লেখা হয়
for b in entry: edge(a, b)
for b, body in fn.blocks.items():
for i, ins in enumerate(body):
for x in uses(ins) + defs(ins):
if local(x): G.setdefault(x, set())
for d in filter(local, defs(ins)): # নতুন মান d লেখার মুহূর্তে যারা live, তারা d-র শত্রু
src = ins.args[0] if ins.kind == "copy" else None
if src and local(src): moves.append((d, src))
for x in pts[b, i][1]:
if local(x) and x != src: edge(d, x) # copy-র উৎস বাদ: দুজনের মান তখন একই
return G, moves
def loop_blocks(fn): # যে block কোনো চক্রে আছে (নিজের কাছে ফেরা যায়)
S = {b: succs(fn, b) for b in fn.blocks}
def reach(b):
seen, todo = set(), list(S[b])
while todo:
c = todo.pop()
if c not in seen: seen.add(c); todo += S[c]
return seen
return {b for b in fn.blocks if b in reach(b)}
def spill_cost(fn): # (লেখা + পড়া), loop-এর ভেতরে ১০ গুণ; spill-এর নিজের temp অসীম
loops, cost = loop_blocks(fn), {p: 1 for p in fn.params}
for b, body in fn.blocks.items():
for ins in body:
for x in filter(local, uses(ins) + defs(ins)): cost[x] = cost.get(x, 0) + (10 if b in loops else 1)
return {x: float("inf") if "~" in x else c for x, c in cost.items()}
def coalesce(G, moves, k): # Briggs-এর রক্ষণশীল নিয়মে copy-র দুই নাম এক node
G, alias = {x: set(n) for x, n in G.items()}, {}
def find(x):
while x in alias: x = alias[x]
return x
changed = True
while changed:
changed = False
for d, s in moves:
a, b = find(d), find(s)
if a == b or b in G[a]: continue # আগেই এক, বা শত্রু: মেলানো যাবে না
nb = G[a] | G[b] # মেলানো node-এর প্রতিবেশী; ভারী = degree ≥ k
heavy = sum(len(G[n]) - (n in G[a] and n in G[b]) >= k for n in nb)
if heavy >= k: continue
for n in G[b]: G[n].discard(b); G[n].add(a)
G[a] = nb; del G[b]; alias[b] = a; changed = True
return G, alias
def color(G, k, cost, regs, optimistic=True, allowed={}, trace=None):
deg, left, stack, spill = {x: len(n) for x, n in G.items()}, list(G), [], []
while left: # simplify: degree < k হলে সরাও; না পেলে spill-এর প্রার্থী
x = next((x for x in left if deg[x] < k), None)
why = "simplify"
if x is None:
x = min(left, key=lambda y: (cost[y] / max(deg[y], 1), str(y))); why = "spill?"
left.remove(x)
for n in G[x]:
if n in left: deg[n] -= 1
if why == "spill?" and not optimistic:
if cost[x] == float("inf"): raise ValueError(f"too few registers for {x}")
spill.append(x) # Chaitin: এখনই spill
else: stack.append(x) # Briggs: আশায় stack-এ
if trace is not None: trace.append((why, x))
colour = {}
for x in reversed(stack): # select: উল্টো ক্রমে, প্রতিবেশীর না-নেওয়া প্রথম register
used = {colour[n] for n in G[x] if n in colour}
free = [r for r in allowed.get(x, regs) if r not in used]
if free: colour[x] = free[0]
elif cost[x] == float("inf"): raise ValueError(f"too few registers for {x}")
else: spill.append(x)
if trace is not None: trace.append(("select", x, colour.get(x, "spill")))
return colour, spill
def intervals(fn): # নাম -> (শুরু, শেষ); reverse postorder-এ নির্দেশ j: পড়া 2j, লেখা 2j+1
_, pts = analyze(fn, LIVENESS)
iv, j = {}, 0
def mark(x, p):
if local(x): a, b = iv.get(x, (p, p)); iv[x] = (min(a, p), max(b, p))
for p in fn.params: mark(p, -1)
for b in rpo(fn):
for i, ins in enumerate(fn.blocks[b]):
for x in set(pts[b, i][0]) | set(uses(ins)): mark(x, 2 * j)
for x in set(pts[b, i][1]) | set(defs(ins)): mark(x, 2 * j + 1)
j += 1
return iv
def linear_scan(fn, regs, cost, allowed={}, trace=None): # Poletto–Sarkar-এর ধাঁচে
iv, free, active, colour, spill = intervals(fn), list(regs), [], {}, []
for x in sorted(iv, key=lambda x: (iv[x][0], x)):
s, e = iv[x]
for y in [y for y in active if iv[y][1] < s]: # expire: যার শেষ পেরিয়ে গেছে
active.remove(y); free.append(colour[y])
free.sort(key=regs.index)
ok = [r for r in free if r in allowed.get(x, regs)]
if ok: colour[x] = ok[0]; free.remove(ok[0]); active.append(x)
else: # জায়গা নেই: যে সবচেয়ে দেরিতে শেষ হয়, সে spill
cand = [y for y in active if cost[y] < float("inf") and colour[y] in allowed.get(x, regs)]
v = max(cand, key=lambda y: iv[y][1], default=None)
if v is None and cost[x] == float("inf"): raise ValueError(f"{fn.name}: too few registers")
if v is not None and (iv[v][1] > e or cost[x] == float("inf")):
colour[x] = colour.pop(v); active.remove(v); active.append(x); spill.append(v)
else: spill.append(x)
if trace is not None: trace.append((x, s, e, colour.get(x, "spill"), sorted(active)))
return colour, spill
def spill_code(fn, spilled): # লেখার পরে store ($x = x~n), পড়ার আগে load (x~n = $x)
S, n, blocks, params, head = set(spilled), [0], {}, list(fn.params), []
def fresh(x): n[0] += 1; return f"{x}~{n[0]}"
for j, p in enumerate(params): # spill করা parameter: ঢুকেই slot-এ রাখা
if p in S: params[j] = fresh(p); head.append(Ins("copy", f"${p}", [params[j]]))
for b, body in fn.blocks.items():
out = []
for ins in body:
ins, got = replace(ins, args=list(ins.args), targets=list(ins.targets)), {}
for j, x in enumerate(ins.args):
if x in S:
if x not in got: got[x] = fresh(x); out.append(Ins("copy", got[x], [f"${x}"]))
ins.args[j] = got[x]
if ins.dst in S:
y = fresh(ins.dst); out += [replace(ins, dst=y), Ins("copy", f"${ins.dst}", [y])]
else: out.append(ins)
blocks[b] = out
if head and preds(fn)["B0"]: # B0 loop-এর মাথা হলে store-এর জন্য নতুন entry block
m = f"B{len(blocks)}"; ren = lambda t: m if t == "B0" else t
blocks = {"B0": head + [Ins("jump", targets=[m])],
**{ren(b): [replace(i, targets=[ren(t) for t in i.targets]) for i in body] for b, body in blocks.items()}}
elif head: blocks["B0"] = head + blocks["B0"]
return IRFunction(fn.name, params, [], blocks)
def apply_regs(fn, colour): # নাম -> register; একই register-এর copy (r1 = r1) মুছে যায়
R, blocks, removed = (lambda x: colour.get(x, x)), {}, 0
for b, body in fn.blocks.items():
blocks[b] = []
for ins in body:
new = replace(ins, dst=ins.dst and R(ins.dst), args=[R(x) for x in ins.args], targets=list(ins.targets))
if new.kind == "copy" and new.dst == new.args[0]: removed += 1
else: blocks[b].append(new)
return IRFunction(fn.name, [R(p) for p in fn.params], [], blocks), removed
@dataclass
class Allocation:
fn: IRFunction # register-এর নামে লেখা function (spill code-সহ)
colour: dict # শেষ রাউন্ডের IR নাম -> register
spilled: list # stack slot পাওয়া নাম, সব রাউন্ড মিলিয়ে
rounds: int # কতবার graph বানিয়ে রং করা হলো
moves: int # শেষ রাউন্ডে copy (দুই দিকেই local নাম)
removed: int # রং মিলে যাওয়ায় মুছে যাওয়া copy
def allocate(fn, regs, method="briggs", callee_saved=(), coalescing=True):
spilled = [] # method: "briggs", "chaitin" বা "linear"
for rnd in range(1, 50):
G, moves = interference(fn); cost = spill_cost(fn)
across = set().union(set(), *live_across_calls(fn).values()) if callee_saved else set()
allowed = {x: list(callee_saved) for x in across if local(x)} # call পেরোনো মান শুধু s-register-এ
if method == "linear": colour, sp = linear_scan(fn, regs, cost, allowed)
else:
alias = {}
if coalescing:
G, alias = coalesce(G, moves, len(regs))
for x, a in alias.items(): # মেলানো node: খরচ যোগ, শর্ত একত্র
while a in alias: a = alias[a]
cost[a] += cost[x]
if x in allowed: allowed[a] = list(callee_saved)
colour, sp = color(G, len(regs), cost, regs, method == "briggs", allowed)
for x in alias:
a = x
while a in alias: a = alias[a]
if a in colour: colour[x] = colour[a]
elif a in sp: sp.append(x)
if not sp: break
spilled += sp; fn = spill_code(fn, sp)
new, removed = apply_regs(fn, colour)
return Allocation(new, colour, spilled, rnd, len(moves), removed)
def machine_check(fn, regs): # যন্ত্রের নিয়ম: operand শুধু register; slot ছোঁয় শুধু load/store
bad = [p for p in fn.params if p not in regs]
for b, body in fn.blocks.items():
for ins in body:
names = ([ins.dst] if ins.dst else []) + ins.args
slots = [x for x in names if x[0] == "$"]
if slots and (ins.kind != "copy" or len(slots) == 2): bad.append(f"{b}: {ins}")
bad += [f"{b}: {ins}" for x in names if x[0] not in "$@" and x not in regs]
return bad
def clobber(fn, caller_saved, junk=-777): # call-এর পরে caller-saved register-এ আবর্জনা: ডাকা function নষ্ট করেছে ধরে নিয়ে
blocks = {}
for b, body in fn.blocks.items():
blocks[b] = []
for ins in body:
blocks[b].append(ins)
if ins.kind == "call": blocks[b] += [Ins("const", r, [], junk) for r in caller_saved if r != ins.dst]
return IRFunction(fn.name, list(fn.params), [], blocks)
def allocate_module(mod, regs, method="briggs", callee_saved=(), coalescing=True):
allocs = {name: allocate(fn, regs, method, callee_saved, coalescing) for name, fn in mod.funcs.items()}
return IRModule({n: a.fn for n, a in allocs.items()}, mod.globals), allocs
def run_fuel(mod, fuel=2_000_000): # run_lines-এর মতো, কিন্তু ভুল কোড অনন্ত loop-এ পড়লে থামে
n = [0]
def step(f, ev, a): # run_ir-এর প্রতিটি Python লাইনে এক ফোঁটা জ্বালানি
n[0] += 1
if n[0] > fuel: raise TimeoutError
return step
sys.settrace(lambda f, ev, a: step if f.f_code.co_name == "run_ir" else None)
try: return run_lines(mod)
except TimeoutError: return ["<out of fuel>"]
finally: sys.settrace(None)# ধাপ ২: Briggs-এর colouring, k = 3 — spill, আবার রং, তারপর register-এর নামে লেখা কোড চালানো
from haat_ra import *
R = ["r0", "r1", "r2"]
for name in ("bill.haat", "examples/bazar.haat"):
mod = compile_ir(open(name, encoding="utf-8").read())
new, allocs = allocate_module(mod, R) # Briggs + coalescing, যতক্ষণ spill থাকে
for f, a in allocs.items():
print(f"{f:9} রাউন্ড {a.rounds} · spill {', '.join(a.spilled) or '—'} · "
f"copy মুছল {a.removed}/{a.moves} · নিয়মভঙ্গ {len(machine_check(a.fn, R))}")
want = open(name[:-5] + ".out", encoding="utf-8").read().split()
got = run_lines(new)
print(f" {name}: {got} · reference-এর সঙ্গে মিল: {got == want} · "
f"চলা নির্দেশ {run_ir(mod, lambda s: None)} → {run_ir(new, lambda s: None)}")
print(show_ir(allocate(compile_ir(open("bill.haat", encoding="utf-8").read()).funcs["bill"], R).fn))আসল আউটপুট (ব্রাউজারের Python):
<main> রাউন্ড 1 · spill — · copy মুছল 0/0 · নিয়মভঙ্গ 0
bill রাউন্ড 2 · spill coupon · copy মুছল 0/0 · নিয়মভঙ্গ 0
best রাউন্ড 1 · spill — · copy মুছল 1/2 · নিয়মভঙ্গ 0
bill.haat: ['1185', '1092'] · reference-এর সঙ্গে মিল: True · চলা নির্দেশ 32 → 35
<main> রাউন্ড 1 · spill — · copy মুছল 0/0 · নিয়মভঙ্গ 0
price রাউন্ড 1 · spill — · copy মুছল 0/0 · নিয়মভঙ্গ 0
delivery রাউন্ড 1 · spill — · copy মুছল 0/0 · নিয়মভঙ্গ 0
examples/bazar.haat: ['996', '5000', '3'] · reference-এর সঙ্গে মিল: True · চলা নির্দেশ 74 → 74
fn bill(r2, r1, r0):
B0:
$coupon = r0
r1 = r2 * r1
r0 = const 20
r0 = r1 / r0
r1 = r1 + r0
r0 = $coupon
r0 = r0 * r2
r0 = r1 - r0
return r0
bill-এ দুই রাউন্ড আর একটি spill, stepper-এর মতো। দুটি program-ই reference-এর আউটপুট ছেপেছে (.out ফাইল দুটি পর্ব ৬২-এর মতো reference run থেকে নেওয়া), আর কোথাও যন্ত্রের নিয়ম ভাঙেনি। চলা নির্দেশের সংখ্যা bill.haat-এ ৩২ থেকে ৩৫: দুটি bill call-এ একটি করে store আর load যোগ হলো (৪টি), আর best-এর একটি copy মুছে গেল (১টি)। bazar-এ ৭৪-ই থাকল: তিনটি register-এই সব ধরে, কিছু বাড়েনি বা কমেনি। শেষের listing-টি পড়ুন: r0 = $coupon ঠিক গুণের আগে, আর তিনটি parameter এসেছে r2, r1, r0-তে।
দুটি উদাহরণ যথেষ্ট নয়। লেখকের lab-এ বড় মাপে: পর্ব ৬২-এর ১০টি উদাহরণের ৮টি (বাকি দুটিতে closure, Haat IR v1-এর বাইরে), bill.haat, cart.haat আর haat_gen.py-র ৩,০০০টি এলোমেলো program, প্রতিটির আউটপুট সরাসরি reference-এর run-এর সঙ্গে মেলানো। ৩,০১০টি program, ৯,০২৫টি function, নয় রকম সেটিং: প্রতিটিতে ৩,০১০/৩,০১০ মিল, নিয়মভঙ্গ শূন্য। খরচ (চলা নির্দেশ শুধু runtime error ছাড়া program-এর; মূল IR-এ মোট ৯,১৮,৩৭৭):
| register | পদ্ধতি | spill হওয়া function | load + store (কোডে) | বাড়তি চলা নির্দেশ |
|---|---|---|---|---|
| ৩ | Briggs | ৬,০৯০ | ৫১,৭৮৬ | +১,০২,৮২৩ |
| ৩ | Chaitin | ৬,০৯০ | ৫৬,৮৯৮ | +১,০৯,০৫৫ |
| ৩ | linear scan | ৬,৪৯৭ | ৭২,৬৮৫ | +১,৪৯,২৯০ |
| ৪ | Briggs | ৩,০৭১ | ১৮,৫৮৭ | +৩৬,২৩৪ |
| ৪ | Chaitin | ৩,০৭৭ | ২০,১৪৩ | +৩৭,৯৪৩ |
| ৪ | linear scan | ৩,৯৪৯ | ৩৮,৪৫০ | +৭৭,০৩৪ |
Briggs-এর আশা প্রতিবার Chaitin-এর চেয়ে কম load/store দিয়েছে, যদিও spill হওয়া function প্রায় সমান। Linear scan (অংশ ৬) সবচেয়ে দামি। আর একটি register বাড়ালে খরচ প্রায় তিন ভাগের এক ভাগে নামে; এজন্যই ৩২-register-এর RISC-V-এ, ৮টি সাধারণ register-এর পুরোনো ৩২-বিট x86-এর তুলনায়, spill সাধারণত অনেক কম। এই এলোমেলো program-গুলো ইচ্ছা করে ঘন; সংখ্যাগুলো পরীক্ষাগারের ছবি, বাস্তব program-এর পরিমাপ নয়।
পরীক্ষাটি নিজে কি ভুল ধরে? লেখকের lab-এ একটি ভুল বসানো হয়েছে: প্রতিটি function-এ একজোড়া শত্রুকে জোর করে এক register-এ, যেন allocator একটি interference ভুলে গেছে। ৩,০০০টি এলোমেলো program-এর ১,৭৮৮টিতে আউটপুট বদলেছে (২৩৪টি থামেনি; run_fuel একটি সীমার পরে থামায়)। বাকি ১,২১২টিতে ভুলটি চোখ এড়িয়েছে: জোড়ার একজনের মান হয়তো তখন আর কেউ পড়ে না। Differential test ভুলের উপস্থিতি দেখায়, অনুপস্থিতি প্রমাণ করে না। নিচের ব্লক একই পরীক্ষা ব্রাউজারে ছোট মাপে চালায়, পর্ব ৬২-এর random_ref.txt (reference run-এর আউটপুটের digest) দিয়ে।
# ধাপ ৩: differential test — তিন allocator, ৪০টি এলোমেলো program; তারপর জেনেশুনে একটি ভুল
import hashlib, haat_ra
from haat_ra import *
from haat_gen import gen_program
ref = open("random_ref.txt").read().split() # reference run-এর digest (পর্ব ৬২)
digest = lambda lines: hashlib.sha256("\n".join(lines).encode()).hexdigest()[:10]
R, RV, S = ["r0", "r1", "r2"], ["t0", "t1", "t2", "s1", "s2"], ["s1", "s2"]
mods = [compile_ir(gen_program(s)) for s in range(40)]
for method in ("briggs", "chaitin", "linear"):
ok = mem = 0
for s, mod in enumerate(mods):
new, allocs = allocate_module(mod, R, method)
ok += digest(run_lines(new)) == ref[s]
mem += sum("$" in str(i) for f in new.funcs.values() for b in f.blocks.values() for i in b)
print(f"{method:8} k=3: {ok}/40 মিল, load/store নির্দেশ {mem}")
ok = 0
for s, mod in enumerate(mods): # RISC-V-ধাঁচ: call-এর পরে t-register-এ আবর্জনা
new, _ = allocate_module(mod, RV, "briggs", S)
ok += digest(run_lines(IRModule({n: clobber(f, RV[:3]) for n, f in new.funcs.items()}, new.globals))) == ref[s]
print(f"t0–t2 + s1–s2, call-এর পরে আবর্জনা: {ok}/40 মিল")
real = haat_ra.coalesce # ভুল: প্রতিটি function-এ একজোড়া শত্রুকে এক register-এ
def wrong(G, moves, k):
G, alias = real(G, moves, k)
pairs = sorted((a, b) for a in G for b in G[a] if a < b)
if pairs:
a, b = pairs[0]
for n in G[b]: G[n].discard(b); G[n].add(a)
G[a] = (G[a] | G[b]) - {a, b}; del G[b]; alias[b] = a
return G, alias
haat_ra.coalesce = wrong
caught = sum(digest(run_fuel(allocate_module(m, R)[0], 300_000)) != ref[s] for s, m in enumerate(mods))
haat_ra.coalesce = real
print(f"ভুল allocator: ৪০টির মধ্যে {caught}টিতে আউটপুট আলাদা — test ধরেছে")আসল আউটপুট (ব্রাউজারের Python):
briggs k=3: 40/40 মিল, load/store নির্দেশ 745
chaitin k=3: 40/40 মিল, load/store নির্দেশ 821
linear k=3: 40/40 মিল, load/store নির্দেশ 915
t0–t2 + s1–s2, call-এর পরে আবর্জনা: 40/40 মিল
ভুল allocator: ৪০টির মধ্যে 26টিতে আউটপুট আলাদা — test ধরেছে
তিন পদ্ধতিই ৪০/৪০, আর load/store-এর ক্রম lab-এর বড় টেবিলের মতোই: Briggs < Chaitin < linear scan. চতুর্থ লাইনটি অংশ ৭-এর RISC-V-ধাঁচের পরীক্ষা। শেষ লাইনে ভুল allocator ৪০টির ২৬টিতে ধরা পড়েছে, lab-এর ১,৭৮৮/৩,০০০-এর কাছাকাছি অনুপাত। wrong function শুধু coalesce-এর ফলের ওপর একটি শত্রু-জোড়া মিলিয়ে দেয়; allocator-এর বাকি কোড অপরিবর্তিত।
৫ · Coalescing — copy মুছে ফেলা
Haat IR-এ m = a ধরনের copy আসে var m = a; বা m = b; থেকে, আর পর্ব ৬৩-এর out-of-SSA ধাপ থেকে আসে ঝাঁকে ঝাঁকে। Copy-র দুই প্রান্ত একই register পেলে নির্দেশটি r1 = r1 হয়ে যায়, যা মুছে ফেলা যায়। Coalescing এটিকে ভাগ্যের ওপর ছাড়ে না: copy-র দুই প্রান্ত শত্রু না হলে graph-এ দুটি node মিলিয়ে একটি করে, তাই তারা একই রং পাবেই।
ঝুঁকিও আছে। দুটি node মেলালে নতুন node-এর শত্রু দুজনের শত্রুর মিলন, degree বাড়ে, আর আগে রং-যোগ্য graph spill-এ পড়তে পারে। Chaitin-এর মূল পদ্ধতি সম্ভব হলেই মেলাত (aggressive). Briggs একটি রক্ষণশীল নিয়ম দেন, যা coalesce মানে:
Copy a = b-এর a আর b শত্রু না হলে মেলানো যাবে, যদি মেলানো node-এর প্রতিবেশীদের মধ্যে degree ≥ k এমন (“ভারী”) প্রতিবেশী k-এর কম হয়। কারণ: simplify-তে হালকা প্রতিবেশীরা আগেই সরে যাবে, তখন মেলানো node-এর degree k-এর কম হবে, আর উপপাদ্য ৭০.৩ অনুযায়ী সে রং পাবে। তাই এই মেলানো কখনো নতুন spill আনে না। (George-এর আরেকটি নিয়ম প্রতিবেশীদের এক এক করে পরীক্ষা করে; George আর Appel ১৯৯৬ সালে দুটিকে simplify-এর সঙ্গে পালা করে চালানোর “iterated coalescing” দেন।)
1B0: m = a2 t1 = b > m3 branch t1 B1 B24B1: m = b5 jump B26B2: return m
| edge | |
| copy | |
| রং |
- Graph. চারটি edge: entry-তে a–b;
m = a-র পরে b আর m live, তাই m–b (a উৎস, বাদ);t1 = b > m-এর পরে t1, b, m live, তাই t1–b, t1–m. Copy-জোড়া দুটি: (m, a) আর (m, b). - m = a. a আর m-এর মধ্যে edge নেই। মেলানো node-এর প্রতিবেশী b আর t1; মেলানোর পরে দুজনেরই degree ২, যা k = ৩-এর কম: কোনো ভারী প্রতিবেশী নেই। Briggs-এর নিয়মে মেলানো নিরাপদ: a আর m এখন একটি node.
- m = b. m আর b শত্রু: প্রথম copy-র পরে দুজনেই live, আর তখন তাদের মান আলাদা হতে পারে (b > a হলে পরে m বদলাবে)। মেলানো নিষেধ। রং: t1 r0, m (আর a) r1, b r2.
- ফল.
m = aহয়ে গেলr1 = r1, তাই মুছে গেল;m = bথাকলr1 = r2হয়ে। Coalescing ছাড়া চালালে a পেত r0, আরr1 = r0copy-টি থেকে যেত (অংশ ৪-এর ব্লকের “copy মুছল ১/২”).
বড় মাপে (Briggs, k = ৩, ৩,০১০টি program): শেষ রাউন্ডে ৪,২৯৮টি copy; coalescing-সহ মুছেছে ৪,২৪০টি, coalescing ছাড়া ৩,৭৭৭টি, শুধু রং কাকতালীয়ভাবে মেলায়। SSA থেকে আসা কোডে copy আরও বেশি। পর্ব ৬৩-এ বলা আছে, strict SSA program-এর interference graph chordal, যেখানে ন্যূনতম রং বহুপদী সময়ে মেলে; এ থেকে SSA-র ওপর সরাসরি register allocation-এর একটি গবেষণা-ধারা এসেছে।
৬ · Linear scan — JIT-এর দ্রুত পথ
Graph colouring-এর দাম আছে: graph বানাতে সময় আর memory, edge নামের সংখ্যার বর্গের মতো বাড়তে পারে, আর spill হলে আবার গোড়া থেকে। পর্ব ৬১-এর JIT-এর কাছে সময়টাই দামি। Massimiliano Poletto আর Vivek Sarkar ১৯৯৯ সালের প্রবন্ধে (আগে Poletto ও সহকর্মীদের একটি dynamic code generation system-এ) linear scan দেন: graph নয়, একটি সারি।
নির্দেশগুলো একটি রৈখিক ক্রমে সাজান (এখানে block-গুলো পর্ব ৬৪-এর reverse postorder-এ, নির্দেশ j-এর পড়ার বিন্দু 2j আর লেখার বিন্দু 2j + 1; parameter-এর লেখা −1). প্রতিটি নামের live interval হলো সেই ক্রমে তার প্রথম থেকে শেষ live বিন্দু পর্যন্ত একটি টানা অংশ। Loop থাকলে মাঝে ফাঁক থাকতে পারত, interval সেই ফাঁকসহ ধরে: সাবধানী, কিন্তু সঠিক। তারপর অ্যালগরিদম, শুরুর ক্রমে একবার হেঁটে:
linear_scan)
- Interval-গুলো শুরুর বিন্দু অনুযায়ী সাজান। “active” তালিকা খালি, সব register মুক্ত।
- প্রতিটি নতুন interval i-এর জন্য: active-এর যাদের শেষ i-এর শুরুর আগে, তাদের সরিয়ে register মুক্ত করুন (expire).
- মুক্ত register থাকলে i পায় প্রথমটি, i যায় active-এ।
- না থাকলে active আর i-এর মধ্যে যার শেষ সবচেয়ে দূরে, সে spill; সে active-এর কেউ হলে তার register i পায়।
1coupon [-1, 8]2qty [-1, 8]3unit [-1, 0]4p [ 1, 6]5t1 [ 3, 4]6vat [ 5, 6]7pay [ 7, 10]8t2 [ 9, 10]9t3 [11, 12]
| expire | |
| পেল | |
| active | |
| মুক্ত |
- Interval. নির্দেশ j-এর পড়া 2j, লেখা 2j + 1. যেমন p লেখা হয় নির্দেশ ০-এ (বিন্দু ১) আর শেষবার পড়া হয় নির্দেশ ৩-এ (বিন্দু ৬): [1, 6]. Parameter-রা −1 থেকে। সাজানো ক্রমে হাঁটা শুরু।
- coupon. Active খালি, সব মুক্ত: r0.
- qty. শুরু −1, কেউ শেষ হয়নি: r1.
- unit. r2. এখন তিনটি register-ই ভরা।
- p, শুরু ১. unit-এর শেষ 0, যা ১-এর আগে: expire, r2 মুক্ত। p পায় r2. লক্ষ করুন, p আর unit শত্রুও নয় (অংশ ২)।
- t1, শুরু ৩. কেউ শেষ হয়নি, register নেই। Active-এর শেষগুলো: coupon 8, qty 8, p 6; t1-এর নিজের 4. সবচেয়ে দূরে coupon (qty-র সমান, প্রথমজন বাছা হলো): coupon spill, তার r0 পেল t1. Colouring-এর মতোই coupon, কিন্তু অন্য যুক্তিতে: “যে সবচেয়ে দেরিতে লাগবে”.
- vat, শুরু ৫. t1-এর শেষ 4: expire. vat পায় r0.
- pay, শুরু ৭. p আর vat দুজনেরই শেষ 6: expire, r2 আর r0 মুক্ত। pay পায় তালিকার প্রথমটি, r0.
- t2, শুরু ৯. qty-র শেষ 8: expire, r1 মুক্ত। t2 পায় r1.
- t3 আর ফল. pay, t2 শেষ; t3 পায় r0. একটি spill (coupon); spill code বসিয়ে দ্বিতীয় রাউন্ডে কোনো spill নেই। graph একবারও বানানো হয়নি, শুধু সাজানো আর একবার হাঁটা।
ছবি ৭০.২ — bill-এর live interval আর linear scan-এর প্রথম রাউন্ড
ওপরের সংখ্যা: রৈখিক ক্রমের বিন্দু
দাম কোথায়? Linear scan interval-কে টানা অংশ ধরে, loop বা শাখার “গর্ত” দেখে না, আর spill করা নাম পুরো জীবন memory-তে থাকে। তাই অংশ ৪-এর টেবিলে তার load/store Briggs-এর প্রায় ১.৪ গুণ (k = ৩) থেকে ২ গুণ (k = ৪)। বিনিময়ে গতি: সাজানোর পরে একটি পাস। পরের কাজ ফাঁক কমায়: Traub, Holloway আর Smith-এর ১৯৯৮ সালের “second-chance binpacking”, আর Wimmer ও Mössenböck-এর ২০০৫ সালের interval splitting, যা তাঁদের ভাষ্যে Java HotSpot-এর client compiler-এ গেছে। JavaScript engine-এর JIT-গুলোও linear scan-এর কোনো রূপ ব্যবহার করেছে (engine আর version-ভেদে বদলায়)।
৭ · RISC-V-এর দুই দল register, call আর সত্যিকারের Clang
অংশ ৪-এর সরলীকরণটি এবার ভাঙি। বাস্তবে সব register একটিই, আর call-এর পরে কোনগুলো অক্ষত থাকবে তা calling convention ঠিক করে। পর্ব ৭১ RISC-V psABI v1.0 থেকে নিয়মটি দিয়েছে: caller-saved register (t0–t6, a0–a7, ra) ডাকা function নষ্ট করতে পারে; callee-saved register (s0–s11, sp) সে বদলালে রেখে ফিরিয়ে দেয়। তাই allocator-এর জন্য নিয়ম: যে মান একটি call পেরিয়ে বাঁচে, সে s register পাবে, নয়তো spill হবে।
কোন মান call পেরোয়, তা বলে পর্ব ৬৪-এর অনুশীলনের live_across_calls (হুবহু নেওয়া)। allocate(…, callee_saved=["s1", "s2"]) দিলে এমন নাম শুধু ওই দুটি register থেকে বাছে। যাচাইয়ে clobber প্রতিটি call-এর পরে প্রতিটি caller-saved register-এ (ফলের register ছাড়া) আবর্জনা -777 লেখে, যেন ডাকা function সেগুলো নষ্ট করেছে; callee-saved register call-এর নিজের register file-এ নিরাপদ থাকে। নিচের stepper bazar-এর <main>-এ, পাঁচটি register নিয়ে: t0, t1, t2, s1, s2 (allocation-এর পরে t1 মানে RISC-V register, IR-এর temp নয়).
1t3 = call price(t1, t2)2t6 = call price(t4, t5)3t7 = call delivery(t6)4first = t3 + t75print first
| নিয়ম | |
| t3 → | |
| ছাপা |
- কে call পেরোয়?
live_across_calls: প্রথম call-এ খালি set, দ্বিতীয় আর তৃতীয়টিতে {t3}. প্রথমprice(2, 520)-এর ফল (936) শেষেfirst = t3 + t7-এ লাগবে, তাই দুটি call পেরোতে হবে। - নিয়ম ছাড়া allocation.
callee_savedনা দিলে Briggs t3-কে দেয় caller-savedt2; কোড:t2 = call price(t1, t0). - Call নষ্ট করে.
clobber-এর মডেলেdeliveryথেকে ফিরেt1আরt2-তে -777 (t0-তে call-এর ফল)। বাস্তব যন্ত্রে ডাকা function সত্যিই এই register-গুলো যা খুশি ব্যবহার করতে পারে। - ভুল আউটপুট.
t0 = t2 + t0= -777 + 60 = -717. Reference ছাপে 996. Calling convention ভুলে যাওয়া allocator-এর ভুল এভাবেই চুপচাপ আসে। - নিয়মসহ.
callee_saved=["s1", "s2"]: t3 পায়s1, কোডs1 = call price(t1, t0); clobber-এর পরেও ছাপা 996, 5000, 3. দাম:<main>-কে prologue-এs1রাখতে আর epilogue-এ ফেরাতে হবে, পর্ব ৭১-এরframe_layout(fn, callee_saved)ঠিক এই কাজের জন্য।
বড় মাপে, লেখকের lab-এ: পাঁচ register (দুটি callee-saved), clobber-সহ চালিয়ে ৩,০১০/৩,০১০ মিল, Briggs আর linear scan দুটিতেই। আর নিয়মটি বন্ধ করে (সব register সমান ধরে) clobber-সহ চালালে ৩,০০০টি এলোমেলো program-এর ১,৪২৬টিতে আউটপুট বদলেছে (২,৫৯২টিতে কোনো মান অন্তত একটি call পেরোয়)। একই কোড clobber ছাড়া চালালে ৩,০০০/৩,০০০ মিল: অংশ ৪-এর সরল মডেল এই ভুল দেখতেই পেত না। পরীক্ষার মডেল যত বাস্তবের কাছে, তত বেশি ভুল ধরা পড়ে।
এবার সত্যিকারের compiler. লেখকের lab-এ PyPI-র ziglang (MIT লাইসেন্স; Zig 0.17.1, ভেতরে clang 22.1.8) দিয়ে bill আর first-এর C রূপ RISC-V-তে compile করা হয়েছে:
// bazar.c (অংশ)
long first(long qty, long unit) { // price-এর ফল একটি call পেরিয়ে বাঁচে
long a = price(qty, unit);
return a + delivery(a);
}
long bill(long qty, long unit, long coupon) {
long p = qty * unit;
long vat = p / 20;
long pay = p + vat;
return pay - coupon * qty;
}
$ python -m ziglang cc -S -O0 -target riscv64-linux-musl -fno-sanitize=undefined bazar.c
bill: # -O0: প্রতিটি variable-এর একটি stack slot
addi sp, sp, -64
sd ra, 56(sp)
sd s0, 48(sp)
addi s0, sp, 64
sd a0, -24(s0) # qty → slot
sd a1, -32(s0) # unit → slot
sd a2, -40(s0) # coupon → slot
ld a0, -24(s0)
ld a1, -32(s0)
mul a0, a0, a1
sd a0, -48(s0) # p → slot
ld a0, -48(s0)
… # p / 20: গুণ আর shift দিয়ে (৬টি নির্দেশ)
sd a0, -56(s0) # vat → slot
ld a0, -48(s0)
ld a1, -56(s0)
add a0, a0, a1
sd a0, -64(s0) # pay → slot
ld a0, -64(s0)
ld a1, -40(s0) # coupon আবার slot থেকে
ld a2, -24(s0)
mul a1, a1, a2
sub a0, a0, a1
… # epilogue
$ python -m ziglang cc -S -O2 -target riscv64-linux-musl -fno-sanitize=undefined bazar.c
first:
addi sp, sp, -32
sd ra, 24(sp)
sd s0, 16(sp)
sd s1, 8(sp) # callee-saved s1 নিজে রাখল
addi s0, sp, 32
call price
mv s1, a0 # a: call পেরোবে, তাই s1-এ
call delivery
add a0, a0, s1
ld ra, 24(sp)
ld s0, 16(sp)
ld s1, 8(sp)
addi sp, sp, 32
ret
bill: # -O2: প্রোলগ-এপিলগ বাদে সব register-এ
… # ra/s0 রাখা, 1/20-এর ধ্রুবক load
mul a1, a1, a0 # p = qty * unit
mul a0, a2, a0 # coupon * qty: আগেই, coupon-কে বাঁচিয়ে রাখার দরকার নেই
mulh a2, a1, a3
srli a3, a2, 63
srai a2, a2, 3 # vat = p / 20
add a2, a2, a3
sub a0, a1, a0
add a0, a0, a2
… # epilogue
সত্যিকারের run, trim করা (মন্তব্য লেখকের)। -O0-এর bill-এ ৩২টি নির্দেশ, যার ১৪টি slot-এ ld/sd; -O2-এ ১৮টি, slot-এ একটিও নয় (একটি ld শুধু ১/২০-এর জাদু-ধ্রুবক পড়ে)। -O2 coupon * qty আগেই হিসাব করেছে, তাই coupon-এর লম্বা live range-ই উধাও; আমাদের allocator নির্দেশের ক্রম বদলায় না, তাই তাকে spill করতে হয়েছিল। first-এ call পেরোনো a গেছে s1-এ, prologue-এ s1 রাখা: stepper-এর নিয়মই। এই target-এ zig cc frame pointer (s0) রাখে; -fomit-frame-pointer দিলে bill ১১টি নির্দেশে নামে (lab-এর run).
আরও গভীরে: LLVM ৩.০ (২০১১) থেকে তার প্রধান allocator একটি “greedy” allocator, যা live range-কে ভাগ (split) করে, ভারী ব্যবহারের অংশ register-এ রাখে আর হালকা অংশ spill করে; Chaitin-ধাঁচের সম্পূর্ণ graph আর বানায় না (LLVM-এর নিজের নথি আর ২০১১ সালের ব্লগ-লেখা অনুযায়ী)। GCC-র বর্তমান allocator IRA/LRA নামে পরিচিত, যা অঞ্চলভিত্তিক graph colouring-এর ধারণা থেকে এসেছে। গবেষণায় register allocation-কে integer linear programming দিয়ে নিখুঁতভাবে সমাধান করার চেষ্টাও আছে, যা ছোট function-এ সম্ভব কিন্তু compile-এর সময়ে দামি। আর rematerialization: যে মান একটি ধ্রুবক, তাকে spill না করে দরকারের সময় আবার বানানো (অনুশীলন ১).
পরীক্ষা ও ইন্টারভিউতে:
- Interference graph কীভাবে বানাবেন? প্রতিটি নির্দেশের পরে live set; লেখা নামের সঙ্গে সেই set-এর প্রতিটির edge, copy-র উৎস বাদ; parameter-রা পরস্পরের শত্রু।
- k রঙে graph রং করা যাবে কি না, কীভাবে আন্দাজ করবেন? সবচেয়ে বড় clique ≤ k দরকার; degree < k node বারবার সরিয়ে সব সরলে k রঙে নিশ্চিত।
- Spill কাকে করবেন? কম ব্যবহার, অনেক শত্রু, loop-এর বাইরে: cost ÷ degree সবচেয়ে কম।
- Chaitin বনাম Briggs? আটকে গেলে Chaitin সঙ্গে সঙ্গে spill, Briggs select পর্যন্ত অপেক্ষা; বৃত্ত a–b–c–d, k = ২ পার্থক্যটি দেখায়।
- Linear scan কোথায়, কেন? JIT-এ, কারণ graph ছাড়া এক পাসে দ্রুত; বিনিময়ে বেশি spill.
৮ · AI-এর যুগে register allocation
AI assistant একটি graph colouring allocator কয়েক মিনিটে লিখে দেয়, আর ছোট, loop-হীন উদাহরণে তা প্রায়ই ঠিক চলে। ভুলগুলো লুকিয়ে থাকে loop, call আর spill-এর কোণায়, আর ভুল allocation কোনো error দেয় না: শুধু একটি ভুল সংখ্যা ছাপে, যেমন অংশ ৭-এর -717.
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| “একসঙ্গে live” দিয়ে edge, কিন্তু loop-এর back edge বাদ দিয়ে liveness | Loop-ওয়ালা function-এ hand-trace; পর্ব ৬৪-এর solver-এর সঙ্গে তুলনা |
| Copy-র ব্যতিক্রম সব নির্দেশে লাগানো, বা copy-র দুই প্রান্ত শত্রু হলেও মেলানো | best-এর মতো উদাহরণ চালিয়ে আউটপুট মেলানো |
| Spill code-এর নতুন temp-কে আবার spill করা, ফলে অনন্ত চক্র | খুব কম register (k = ২ বা ৩) দিয়ে অনেক program চালানো |
| Calling convention ভুলে call পেরোনো মান caller-saved register-এ রাখা | Call-এর পরে caller-saved register-এ আবর্জনা লিখে চালানো (clobber) |
| “Linear scan সবসময় সমান ভালো” বা “graph colouring সবসময় সর্বোত্তম” জাতীয় সাধারণ দাবি | একই program-এ দুটির load/store গুনে দেখা; heuristic-এর কোনো নিশ্চয়তা নেই |
| বানানো LLVM option বা ভুল ABI-র register নাম | নিজের Clang version-এ চালিয়ে -S listing পড়া; psABI-র নথি মেলানো |
AI-কে কাজে লাগাতে কাঠামো, নিয়ম আর যাচাইয়ের উপায় নিজেই বলে দিন:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Register allocation NP-complete হলে compiler প্রতিদিন হাজার হাজার function-এ এটি কীভাবে করে, আর কেন সেটি যথেষ্ট ভালো?
Chaitin ও সহকর্মীদের ১৯৮১ সালের প্রবন্ধের একটি অংশ ছিল নেতিবাচক খবর: যেকোনো graph-এর জন্য এমন একটি program লেখা যায়, যার interference graph ঠিক সেটি। তাই “এই program কি k টি register-এ spill ছাড়া চলে?” প্রশ্নটি সাধারণ k-colouring-এর মতোই কঠিন, আর k ≥ ৩-এ তা NP-complete. মানে, P ≠ NP হলে কোনো দ্রুত অ্যালগরিদম সব program-এ নিখুঁত উত্তর দেবে না।
তবু তিনটি কারণে বাস্তবে ব্যাপারটি সামলানো যায়। প্রথমত, compiler নিখুঁত উত্তর চায় না; চায় এমন একটি allocation, যা সঠিক আর সাধারণত ভালো। Simplify/select প্রায় রৈখিক সময়ে চলে, আর উপপাদ্য ৭০.৩ নিশ্চিত করে যে যে node সরল, সে রং পাবে: ভুল হয় শুধু “কতটা ভালো” প্রশ্নে, “ঠিক কি না” প্রশ্নে নয়। দ্বিতীয়ত, বাস্তব program-এর graph এলোমেলো graph নয়। বেশিরভাগ নামের live range ছোট, তাই degree কম, আর সরল ধাপেই বেশিরভাগ graph ফুরিয়ে যায়। অংশ ৪-এর lab-এ চার register-এ ৯,০২৫টি function-এর ৫,৯৫৪টিতে কোনো spill লাগেনি, এমনকি ইচ্ছা করে ঘন এলোমেলো কোডেও। তৃতীয়ত, SSA রূপে (পর্ব ৬৩) graph chordal হয়ে যায়, যেখানে সর্বনিম্ন রং বহুপদী সময়ে মেলে; কঠিনতা তখন সরে যায় spill আর coalescing-এর সিদ্ধান্তে।
এই ছবিটি compiler-এর প্রায় সব কঠিন সমস্যার: instruction scheduling, instruction selection-এর অনেক রূপ, এমনকি optimization pass-এর ক্রম। প্রতিটিতে একটি দ্রুত heuristic যা সবসময় সঠিক ফল দেয় আর সাধারণত ভালো ফল দেয়, আর মাঝে মাঝে গবেষকেরা ILP বা SAT solver দিয়ে নিখুঁত উত্তর বের করে দেখান heuristic কত দূরে।
মূল উপলব্ধি: NP-completeness বলে “সব ক্ষেত্রে নিখুঁত, দ্রুত” অসম্ভব; compiler সঠিকতা নিশ্চিত রেখে নিখুঁততা ছেড়ে দেয়, আর বাস্তব program-এর গড়ন সেই ছাড়কে সস্তা করে।
প্র ০২Briggs-এর “আশা” কখনো কি Chaitin-এর চেয়ে খারাপ ফল দিতে পারে? Optimistic colouring-এর দাম কী?
Chaitin আটকে গেলে প্রার্থীকে তখনই spill-এর তালিকায় পাঠান; Briggs তাকে stack-এ রাখেন আর select পর্যন্ত অপেক্ষা করেন। Select-এর সময় প্রার্থীর প্রতিবেশীরা যদি k-এর কম আলাদা রং নেয় (বৃত্তে a আর c একই রং নেয়), প্রার্থী রং পেয়ে যায়। আর রং না পেলে সে তখনই spill হয়, যা Chaitin-ও করতেন। তাই একই প্রার্থী-ক্রমে Briggs-এর spill-এর set Chaitin-এরটির উপসেট: Preston Briggs আর সহকর্মীদের প্রবন্ধে এই যুক্তিই মূল, আর অংশ ৪-এর টেবিলে প্রতিটি সারিতে Briggs-এর load/store কম।
তবে “উপসেট” কথাটি এক রাউন্ডের জন্য। Spill-এর পরে graph বদলায়, পরের রাউন্ডে প্রার্থী আলাদা হতে পারে, আর spill code-এর ছোট নামগুলো নতুন চাপ আনে। তাই পুরো চক্রের শেষে কোনো একটি function-এ Briggs-এর ফল Chaitin-এর চেয়ে খারাপ হওয়া তত্ত্বে অসম্ভব নয়; শুধু গড়ে ভালো। দ্বিতীয় দাম জটিলতায়: Chaitin-এর simplify শেষ হলেই spill-এর তালিকা জানা, Briggs-এ select পর্যন্ত যেতে হয়। আর optimistic রঙের সিদ্ধান্ত কোন node আগে, কোন রং আগে, তার ওপর নির্ভর করে, তাই একই code-এ ছোট বদলে ফল বদলাতে পারে, যা compiler-এর আচরণকে কম অনুমানযোগ্য করে।
পরের গবেষণা এই সূত্র ধরেই এগিয়েছে: কোন রং বাছবেন (biased colouring, যাতে copy-র দুই প্রান্ত একই রং পায়), spill-এর বদলে live range ভাগ করা (splitting), আর পুরো live range নয়, শুধু ব্যস্ত অংশে register (LLVM-এর greedy allocator). প্রতিটি পদক্ষেপ heuristic, প্রতিটি আগেরটির চেয়ে গড়ে ভালো, কোনোটিই সর্বত্র সেরা নয়।
মূল উপলব্ধি: optimistic colouring Chaitin-এর একটি যথেষ্ট শর্তকে প্রয়োজনীয় শর্ত ভাবার ভুল এড়ায়; লাভ গড়ে নিশ্চিত, কিন্তু heuristic-এর জগতে “সবসময় ভালো” দাবি সাবধানে করতে হয়।
প্র ০৩JIT compiler কেন graph colouring ছেড়ে linear scan বেছে নেয়, আর এই বাছাই কি এখনো সত্য?
Ahead-of-time compiler একবার compile করে, ফল বহুবার চলে; compile-এ কয়েক সেকেন্ড বেশি লাগলে কেউ টের পায় না। JIT compile করে program চলার মাঝে, ব্যবহারকারী অপেক্ষা করছে, আর যে সময় compile-এ যায় তা program চালাতে যায় না (পর্ব ৬১)। Graph colouring-এর খরচ graph-এর মাপের ওপর: edge-এর সংখ্যা সবচেয়ে খারাপ ক্ষেত্রে নামের সংখ্যার বর্গ, আর spill হলে graph আবার বানাতে হয়। Poletto আর Sarkar ১৯৯৯ সালে দেখান যে interval সাজিয়ে একবার হাঁটলে অনেক কম সময়ে এমন কোড আসে, যা তাঁদের পরীক্ষায় colouring-এর কোডের খুব কাছাকাছি চলে।
এই পর্বের lab সেই ছবির দুই দিকই দেখায়। Linear scan সঠিক (৩,০১০/৩,০১০), কিন্তু k = ৩-এ load/store Briggs-এর চেয়ে প্রায় ৪০% বেশি, কারণ interval loop আর শাখার ফাঁক দেখে না আর spill করা নাম পুরো জীবন memory-তে থাকে। Register বেশি হলে চাপ কমে, ফাঁকও কম চোখে পড়ে; ৩২-register-এর যন্ত্রে পার্থক্য সাধারণত ছোট।
পরের প্রজন্মের কাজ এই ফাঁক কমিয়েছে। Traub ও সহকর্মীদের second-chance binpacking (১৯৯৮) একটি interval-কে মাঝপথে register বদলাতে দেয়; Wimmer আর Mössenböck-এর interval splitting (২০০৫) Java HotSpot-এর client compiler-এ গেছে; আর বিভিন্ন JavaScript JIT linear scan-এর কোনো রূপ ব্যবহার করেছে। অন্যদিকে graph colouring-ও দ্রুত হয়েছে, আর LLVM-এর greedy allocator দুই জগতের মাঝামাঝি। তাই প্রশ্নটি আজ “কোনটি” নয়, “এই compile-সময়ের বাজেটে কতটা মান”: একই engine-এ দ্রুত tier-এ সরল allocator, ধীর আর গভীর tier-এ ভারী allocator.
মূল উপলব্ধি: register allocator-এর বাছাই একটি অর্থনৈতিক সিদ্ধান্ত: compile-এর সময় বনাম চলার সময়; JIT-এর tier ব্যবস্থা দুটিকেই এক engine-এ রাখে।
প্র ০৪একটি call পেরোনো মান callee-saved register-এ রাখবেন, না call-এর আগে-পরে নিজে stack-এ রাখবেন? কোনটি সস্তা?
দুটি পথই সঠিক, দাম আলাদা জায়গায়। Callee-saved register (s1) নিলে function-এর prologue-এ একটি sd s1 আর epilogue-এ একটি ld s1: function-এ একবার ঢোকা-বেরোনোয় দুটি memory নির্দেশ, যতগুলো call-ই থাকুক। Caller-saved register (t2) নিয়ে নিজে বাঁচালে প্রতিটি call-এর আগে store আর পরে load: call-এর সংখ্যার দ্বিগুণ। bazar-এর <main>-এ t3 দুটি call পেরোয়: s1-এ দুটি নির্দেশ, নিজে বাঁচালে চারটি। Clang-এর -O2-ও first-এ s1 বেছেছে।
কিন্তু হিসাব উল্টে যায়, যখন call-টি একটি বিরল শাখায়। ধরুন একটি function সাধারণত call ছাড়াই ফেরে, কেবল ভুল ইনপুটে একটি error-লগ function ডাকে। তখন s1 নিলে প্রতিবার prologue/epilogue-এর দাম, অথচ caller-saved পথে store/load শুধু বিরল শাখায়। এজন্য আধুনিক compiler “shrink-wrapping” নামে একটি কৌশলে callee-saved register-এর সংরক্ষণ শুধু যে পথে দরকার সেখানে সরিয়ে নেয়, আর profile থাকলে শাখার সম্ভাবনা দিয়ে খরচ মাপে। Leaf function, যে কাউকে ডাকে না, তার জন্য প্রশ্নই নেই: caller-saved register বিনা খরচে, আর তাই ভালো allocator ছোট leaf function-এ আগে t আর a register ফুরিয়ে তবেই s register ছোঁয়, যাতে prologue-এ কিছু রাখতেই না হয়।
এই পর্বের allocator সহজ পথ নিয়েছে: call পেরোনো মানের জন্য শুধু s register, না পেলে spill. ABI-র এই দুই দল নিজেই একটি আপস: পর্ব ৭১-এ দেখেছেন, সব register এক দলে হলে কোনো একদিকের খরচ অনেক বেড়ে যেত। Allocator সেই আপসের ভেতরে প্রতিটি মানের জন্য সস্তা পথটি খোঁজে।
মূল উপলব্ধি: callee-saved মানে function-প্রতি স্থির দাম, caller-saved মানে call-প্রতি দাম; কোনটি সস্তা তা call-এর সংখ্যা আর কোন পথে কতবার চলে তার ওপর নির্ভর করে।
প্র ০৫Register allocator-এর একটি ভুল কেন এত বিপজ্জনক, আর বাস্তব compiler-দল কীভাবে এমন ভুল ধরে?
Allocator-এর ভুলের তিনটি বৈশিষ্ট্য তাকে ভয়ংকর করে। এক, সে চুপচাপ: compile সফল, program চলে, শুধু একটি সংখ্যা ভুল (অংশ ৭-এর -717). দুই, সে বিরল পথে লুকায়: একটি নির্দিষ্ট শাখা, একটি নির্দিষ্ট register pressure, একটি নির্দিষ্ট call-এর ক্রম মিললে তবে প্রকাশ পায়। অংশ ৪-এর lab-এ জেনেশুনে বসানো ভুল ৩,০০০টির ১,২১২টি program-এ কোনো চিহ্ন রাখেনি। তিন, তার কারণ অনেক দূরে: ভুল দেখা দেয় একটি গুণের ফলে, অথচ দোষ হয়তো liveness-এর একটি back edge-এ।
তাই compiler-দলগুলো কয়েক স্তরে পাহারা দেয়। প্রথম স্তর verifier: LLVM-এর machine code verifier আর allocator-এর পরের পরীক্ষা দেখে যে প্রতিটি ব্যবহারের আগে মানটি সত্যিই সেই register-এ আছে, অনেকটা এই পর্বের machine_check-এর মতো কিন্তু অনেক গভীর। দ্বিতীয় স্তর differential testing আর fuzzing: Csmith-এর মতো এলোমেলো C program-generator দিয়ে (২০১১ সালের প্রবন্ধে Yang ও সহকর্মীরা GCC আর LLVM-এ কয়েকশো bug-এর খবর দেন) বিভিন্ন optimization স্তরে আর বিভিন্ন compiler-এ চালিয়ে আউটপুট মেলানো, ঠিক এই পর্বের মতো। তৃতীয় স্তর প্রমাণ: CompCert (পর্ব ৪৪) register allocation-এর ফল প্রতিবার একটি যাচাই-করা checker দিয়ে পরীক্ষা করে; allocator নিজে প্রমাণিত না হলেও প্রতিটি ফল প্রমাণিত checker পাস করে (translation validation).
এই পর্বের ছোট সংস্করণেও তিনটি স্তর আছে: যন্ত্রের নিয়মের check, reference-এর সঙ্গে differential test, আর একটি বাস্তবসম্মত মডেল (clobber), যা ছাড়া ABI-র ভুল দেখাই যেত না।
মূল উপলব্ধি: চুপচাপ ভুলের জন্য দরকার স্বাধীন পরীক্ষক: ফলের ওপর check, অন্য বাস্তবায়নের সঙ্গে তুলনা, আর যতটা সম্ভব বাস্তবের কাছের পরীক্ষার মডেল।
অনুশীলন
নিজে চেষ্টা করুন, তারপর উত্তর খুলে মিলিয়ে নিন।
-
নকশা ও বাস্তবায়ন — rematerialization:
spill_codeপ্রতিটি spill করা নামের জন্য store আর load বসায়। কিন্তু যে নামের একমাত্র লেখাx = const k, তাকে memory-তে রাখার দরকার কী?haat_ra.pyনা বদলে,spill_code-কে মোড়ানো একটিremat(fn, spilled)লিখুন: এমন নামের store বাদ, আর প্রতিটি load-এর জায়গায় আবারconst k. সঠিকতা কীভাবে যাচাই করবেন?import haat_ra plain = haat_ra.spill_code def remat(fn, spilled): # const দিয়ে লেখা নাম: store/load নয়, আবার const found = {} for body in fn.blocks.values(): for i in body: if i.dst in spilled: found.setdefault(i.dst, []).append(i) k = {x: d[0].sym for x, d in found.items() if len(d) == 1 and d[0].kind == "const"} new = plain(fn, spilled) for b, body in new.blocks.items(): out = [] for i in body: if i.kind == "copy" and i.dst[0] == "$" and i.dst[1:] in k: out.pop(); continue # const আর store দুটিই বাদ if i.kind == "copy" and i.args[0][0] == "$" and i.args[0][1:] in k: i = Ins("const", i.dst, [], k[i.args[0][1:]]) out.append(i) new.blocks[b] = out return new haat_ra.spill_code = remat # allocate এখন নতুনটি ডাকেspill_codeসবসময় লেখার ঠিক পরে store বসায়, তাই store দেখলে আগের নির্দেশটিই সেই const; দুটিই বাদ। শর্ত “একটিই লেখা আর সেটি const”: দুটি আলাদা const বা একটি শাখায় লেখা হলে কোন মান আবার বানাবেন, জানা নেই। যাচাই অংশ ৪-এর মতো: লেখকের lab-এ k = ৩, Briggs, ৩,০০০টি এলোমেলো program, প্রতিটি reference-এর সঙ্গে মেলানো: ৩,০০০/৩,০০০ মিল, আর কোডে load + store ৫১,৭৮০ থেকে নেমে ৪৪,৫৮১ (সত্যিকারের গণনা)। যেমন অনুশীলন ৩-এরdisc-এ k = ২ হলে t1 (const 2) আর stack-এ যায় না; গুণের ঠিক আগেr0 = const 2. LLVM আর GCC-র allocator-ও এই কৌশল ব্যবহার করে, ধ্রুবক ছাড়াও অন্য সস্তা-বানানো মানে। -
ভুল খুঁজুন — একটি “প্রমাণ”: একজন সহপাঠী লিখলেন: “Simplify আটকে গেছে, অর্থাৎ বাকি সব node-এর degree ≥ k. উপপাদ্য ৭০.৩ অনুযায়ী তাই graph-টি k রঙে রং করা যায় না, আর spill অনিবার্য। ∎” যুক্তির কোন ধাপটি ভুল? একটি ছোট উল্টো উদাহরণ দিন, আর বলুন কোন allocator এই ভুল ধারণার ওপর দাঁড়ানো।
উপপাদ্য ৭০.৩ একটি যথেষ্ট শর্ত: “degree < k ⇒ সরানো নিরাপদ”. সহপাঠী তার বিপরীত (converse-এর contrapositive) ধরে নিয়েছেন: “কেউ সরানো যায় না ⇒ রং অসম্ভব”, যা উপপাদ্য বলে না। উল্টো উদাহরণ: চার node-এর বৃত্ত a–b–c–d–a, k = ২. প্রত্যেকের degree ২, তাই simplify শুরুতেই আটকায়, অথচ a, c এক রং আর b, d আরেক রং দিলেই হয়। অংশ ৩-এর JavaScript ব্লক চালালে Chaitin একটি spill দেয় আর Briggs শূন্য।
Chaitin-এর মূল allocator ঠিক এই সাবধানী ধারণায় চলে: আটকালে সঙ্গে সঙ্গে spill. সেটি ভুল ফল দেয় না (spill সবসময় সঠিক), শুধু অপ্রয়োজনীয় spill দেয়। Briggs-এর optimistic colouring এই ফাঁক ভরায়। আর রং সত্যিই অসম্ভব প্রমাণ করতে হলে অন্য যুক্তি লাগে, যেমন k + ১ আকারের একটি clique দেখানো (
bill-এ {p, t1, coupon, qty}, তাই k = ৩-এ spill সত্যিই অনিবার্য)। -
হিসাব করুন — interference graph আর রং: নিচের function-এর Haat IR, প্রতিটি নির্দেশের পরে live set, interference graph, তার chromatic number, আর
allocate-এর ক্রমে (তালিকার ক্রমে প্রথম degree < k node) k = ৩-এ simplify আর select বের করুন। k = ২ হলে প্রথম spill-এর প্রার্থী কে?print(disc(900, 4));কী ছাপবে?fn disc(total: Int, n: Int) -> Int { let a = total / n; let b = a * 2; let c = total - b; return c + a; }IR আর পরে live (লেখকের lab-এ
analyzeদিয়ে মেলানো):a = total / n→ {a, total};t1 = const 2→ {a, t1, total};b = a * t1→ {a, b, total};c = total - b→ {a, c};t2 = c + a→ {t2};return t2→ {}.Edge: total–n (entry), a–total, t1–a, t1–total, b–a, b–total, c–a; মোট ৭. t2 একা। {a, t1, total} একটি ত্রিভুজ, তাই χ ≥ ৩, আর তিন রঙে হয়, তাই χ = ৩. k = ৩-এ simplify-এর ক্রম: n, t1, total, a, b, c, t2 (প্রত্যেকে সরার মুহূর্তে degree < ৩)। Select উল্টো ক্রমে: t2 r0, c r0, b r0, a r1, total r2, t1 r0, n r0. ফল:
fn disc(r2, r0), কোনো spill নেই।k = ২-এ n, c, t2 সরে, তারপর আটকায় (a ৩, t1 ২, total ৩, b ২)। cost ÷ degree: a ৩/৩, t1 ২/২, total ৩/৩, b ২/২; সব সমান (১) হলে
colorনামের বর্ণানুক্রমে প্রথমটি নেয়, তাই প্রার্থী a. পুরো চক্রে চার রাউন্ড আর তিনটি spill (a, t1, total) লাগে, কারণ k = ২-এ ভাগের দুই operand আর একটি বেঁচে থাকা মান একসঙ্গে ধরা যায় না। আউটপুট: 900 / 4 = 225, b = 450, c = 450, ফল 675; reference-এর সত্যিকারের run আর k = ৩ ও k = ২ দুই allocation-ই675ছাপে। -
আউটপুট অনুমান করুন — calling convention ভুলে গেলে: bazar.haat-এর
<main>-এ (প্রথম লাইনে 996 ছাপার কথা) একটি allocator t3-কে caller-savedt2-তে রাখল, আরdeliveryফেরার পরেt1আরt2-তে -777 পড়ে আছে,t0-তে call-এর ফল।first = t3 + t7তখন কী ছাপবে? পরের দুটি লাইন (5000,3) কি বদলাবে?delivery(price(2, 520)): price(2, 520) = 1040 − 104 = 936, যা ১০০০-এর কম, তাই delivery 60 দেয়,t0-তে। t3-এর জায়গায় পড়া হয়t2= -777, তাই ছাপা হয় −777 + 60 =-717. পরের দুটি লাইন বদলায় না: loop-এর total আর rounds call-এর পরে নতুন করে লেখা হয় (t2 = const 0,t1 = const 0), কোনো call পেরোয় না। লেখকের lab-এর সত্যিকারের run:['-717', '5000', '3']. এটিও দেখায় কেন differential test-এ প্রতিটি লাইন মেলাতে হয়: শুধু শেষ লাইন দেখলে এই ভুল চোখ এড়াত।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি graph-colouring register allocator-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Liveness হিসাব করা
- Interference graph বানানো আর copy মেলানো (coalescing)
- Degree < k node সরিয়ে stack-এ রাখা (simplify)
- Stack থেকে উল্টো ক্রমে রং দেওয়া (select)
- রং না পাওয়া নামের জন্য store/load বসানো
- Spill থাকলে আবার গোড়া থেকে, না থাকলে নামগুলো register-এ বদলানো
Chaitin-এর নিয়মে দুটি নাম x আর y কখন interfere করে (graph-এ edge পায়)?
- যখন দুটি একই function-এ থাকে
- যখন একটি নির্দেশ x = y লেখে
- যখন x লেখার ঠিক পরে y live থাকে (x ≠ y, আর নির্দেশটি x = y copy নয়)
- শুধু যখন একই নির্দেশে দুটিই পড়া হয়
একটি interference graph-এ চার node-এর একটি clique আছে (চারজন পরস্পরের শত্রু)। তিনটি register দিয়ে spill ছাড়া allocation সম্ভব কি?
- হ্যাঁ, Briggs-এর optimistic colouring দিয়ে
- না, কারণ clique-এর জন্যই অন্তত ৪টি রং লাগে
- হ্যাঁ, coalescing দিয়ে দুটি node মিলিয়ে
- হ্যাঁ, linear scan দিয়ে
k = ২, আর graph হলো চার node-এর একটি বৃত্ত a–b–c–d–a. Chaitin আর Briggs কী করবেন?
- দুজনেই একটি করে spill করবেন
- দুজনেই spill ছাড়া রং করবেন
- Chaitin spill ছাড়া, Briggs একটি spill
- Chaitin একটি spill, Briggs কোনো spill নয়
Briggs-এর রক্ষণশীল coalescing-এ copy a = b-এর দুই প্রান্ত (শত্রু নয়) কখন মেলানো হয়?
- মেলানো node-এর degree ≥ k এমন প্রতিবেশী k-এর কম হলে
- শত্রু না হলেই সবসময়
- মেলানো node-এর মোট প্রতিবেশী k-এর কম হলে তবেই
- শুধু যখন দুজন আগে থেকেই একই রং পেয়েছে
Linear scan-এ সব register ভরা, আর নতুন interval আসে। Poletto–Sarkar-এর heuristic কাকে spill করে?
- যার interval সবচেয়ে ছোট
- সবসময় নতুন interval-কে
- Active-এর আর নতুনটির মধ্যে যার শেষ সবচেয়ে দূরে
- যে সবচেয়ে আগে শুরু হয়েছে
RISC-V psABI মেনে একটি মান দুটি call পেরিয়ে বাঁচবে। Allocator তাকে কোথায় রাখলে call-এর আশেপাশে কোনো বাড়তি নির্দেশ লাগে না?
t0–t6-এর একটিতেs1–s11-এর একটিতেa0–a7-এর একটিতেra-তে
একটি allocator-এর ফল পরীক্ষায় register-এর নামে লেখা কোড চালিয়ে ৩,০০০টি এলোমেলো program-এ reference-এর সঙ্গে আউটপুট মিলেছে। এ থেকে কী বলা যায়?
- ওই program-গুলোতে ভুল ধরা পড়েনি, কিন্তু allocator নির্ভুল তা প্রমাণ হয়নি
- Allocator সব program-এ নির্ভুল, প্রমাণিত
- Allocator সবচেয়ে কম spill দিয়েছে
- Calling convention-এর ভুল থাকা অসম্ভব
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Interference: x লেখার ঠিক পরে y live হলে x–y edge; copy-র উৎস বাদ; parameter-রা পরস্পরের শত্রু। k রঙে রং মানে k টি register.
- Simplify/select: degree < k node সরানো নিরাপদ; আটকে গেলে cost ÷ degree সবচেয়ে কম নামটি প্রার্থী। Briggs তাকেও আশায় রাখেন।
- Spill code: লেখার পরে store, পড়ার আগে load, নতুন খুদে নামগুলো আর spill নয়; তারপর আবার গোড়া থেকে।
- Coalescing আর linear scan: শত্রু নয় এমন copy মেলানো (Briggs-এর রক্ষণশীল নিয়ম); JIT-এ interval ধরে এক পাস, দ্রুত কিন্তু বেশি spill.
- Call আর যাচাই: call পেরোনো মান callee-saved register-এ; প্রতিটি allocation চালিয়ে reference-এর সঙ্গে মেলান, call-এর পরে caller-saved register নষ্ট করে।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৭১ · Calling convention আর ABIপরবর্তী পর্বCaller-saved আর callee-saved register-এর পুরো চুক্তি আর Haat-এর frame.
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ৬৪ · Dataflow analysisএই কোর্সেLiveness আর worklist solver, যার ওপর interference graph দাঁড়িয়ে।
- পর্ব ৬১ · JIT compilationএই কোর্সেযেখানে compile-এর সময় দামি, আর linear scan-এর জন্ম।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৬৩ · Graph coloringপাশের ট্র্যাকChromatic number, greedy colouring আর তার সীমা।
- Computer Architecture · পর্ব ৩০ · Procedure আর stackপাশের ট্র্যাকRISC-V-এর register আর stack, hardware-এর চোখে।