এই পর্বে যা শিখবেন
- SSA form কী, কেন compiler-এর middle end এটি পছন্দ করে, আর φ function-এর সঠিক অর্থ
- Dominator, immediate dominator, dominator tree আর Cooper–Harvey–Kennedy-র iterative algorithm
- Dominance frontier আর iterated frontier দিয়ে φ কোথায় বসবে, minimal আর pruned SSA-র পার্থক্য
- Dominator tree ঘুরে stack দিয়ে নাম বদল, আর SSA-র শর্ত যাচাই
- SSA থেকে ফেরা: critical edge, lost-copy আর swap সমস্যা; আর সত্যিকারের Clang-এর LLVM IR-এ φ
১ · কেন SSA — এক নাম, এক সংজ্ঞা
বাজারঘরের গুদামের খাতার কথা ভাবুন। একজন কর্মী মজুতের সংখ্যা পেনসিলে লেখেন, আর মাল এলে বা গেলে মুছে নতুন সংখ্যা বসান। দিনের শেষে হিসাব না মিললে প্রশ্ন ওঠে: “এখানে ৪০ লেখা হলো কখন, কোন চালানের পরে?” উত্তর পেতে পুরো দিনের ঘটনা আবার সাজাতে হয়। অন্য কর্মী কখনো মোছেন না; প্রতিটি বদলে নতুন একটি লাইন লেখেন, নম্বরসহ: মজুত-১, মজুত-২, মজুত-৩। এখন “মজুত-২ কোথা থেকে এল” প্রশ্নের উত্তর একটিই লাইন। Compiler-এর SSA form (static single assignment) ঠিক এই দ্বিতীয় খাতা।
পর্ব ৬২-এর Haat IR-এ একটি নামে বহুবার লেখা যায়। সেই পর্বের অনুশীলন ৩-এর bags function দেখুন: বাজারঘর প্রতি ব্যাগে ৬টি জিনিস ভরে, আর ব্যাগ ৩টির বেশি হলে একটি ব্যাগ ছাড় দেয়।
fn bags(items: Int) -> Int {
var n = 0;
var left = items;
while left > 0 {
left = left - 6;
n = n + 1;
}
if n > 3 { n = n - 1; }
return n;
}
এর Haat IR-এ n-এ লেখা হয় তিন জায়গায় (B0, B2, B4). এখন return n-এ যে n পড়া হয়, তার মান কোন নির্দেশ দিয়েছে? উত্তর “নির্ভর করে”: loop কতবার ঘুরল আর if-এর শর্ত সত্য হলো কি না। এমন প্রশ্নের উত্তর রাখার পুরোনো উপায় হলো def-use chain: প্রতিটি সংজ্ঞা (def) থেকে তার সম্ভাব্য সব ব্যবহারের (use) তালিকা, আর উল্টোটাও। d টি সংজ্ঞা আর u টি ব্যবহার থাকলে এই তালিকা d × u পর্যন্ত বড় হতে পারে। SSA-তে প্রশ্নটিই উঠে যায়: প্রতিটি নামের সংজ্ঞা একটিই, তাই একটি ব্যবহার দেখলেই সংজ্ঞা জানা।
একটি function SSA form-এ আছে যদি (১) প্রতিটি নাম লেখায় ঠিক একবার সংজ্ঞায়িত হয় (একটি নির্দেশের dst হিসেবে, বা function-এর parameter হিসেবে), আর (২) দুটি পথ যেখানে মেলে, সেখানে মান বাছাইয়ের জন্য φ নির্দেশ থাকে। সাধারণত আরেকটি শর্তও চাওয়া হয়, যাকে বলে strict SSA: (৩) প্রতিটি ব্যবহারের আগে, B0 থেকে আসা প্রতিটি পথে, সেই নামের সংজ্ঞা থাকে।
“Static” শব্দটি গুরুত্বপূর্ণ: লেখায় একবার, চলার সময় নয়। Loop-এর ভেতরের n#3 = n#2 + t4 চলার সময় বহুবার চলে, প্রতিবার n#3 নতুন মান পায়; কিন্তু program-এর লেখায় n#3-এর সংজ্ঞা একটিই নির্দেশ। ফলটি চোখে দেখুন, bags-এর SSA রূপ (অংশ ৬-এর কোডের সত্যিকারের আউটপুট থেকে আঁকা):
ছবি ৬৩.১ — bags-এর CFG, SSA রূপে
বেগুনি লাইনগুলো φ; প্রতিটি নামের সংজ্ঞা একবার
left আর n দুটিরই φ। if-এর পরের B5-এ n-এর দুই রূপ মেলে (B3 থেকে অপরিবর্তিত n#2, B4 থেকে কমানো n#4). t1, t2 বা items-এর মতো একবার লেখা নাম বদলায়নি; সেগুলো আগে থেকেই SSA.লাভ তিনটি। এক, def-use সরাসরি: নাম মেলালেই চলে। দুই, sparse বিশ্লেষণ: constant propagation (পর্ব ৬৫) প্রতিটি নামের জন্য একটি মান রাখে, প্রতিটি বিন্দুর জন্য নয়। তিন, নিরাপদ বদল: x#1 কখনো বদলায় না, তাই হিসাব সরালে “মাঝখানে কেউ x বদলাল কি না” প্রশ্ন ওঠে না। দাম: মিলনে φ লাগে, আর শেষে SSA থেকে ফিরতে হয় (অংশ ৮)।
২ · φ function — কোন পথে এলেন, সেই মান
B1-এ n-এর কোন রূপ পড়া হবে? প্রথমবার B0 থেকে এলে n#1 (০), পরে B2 থেকে ফিরলে n#3. কোনো সাধারণ নির্দেশ এটি বলতে পারে না, কারণ উত্তর নির্ভর করে কোন edge দিয়ে block-এ ঢোকা হলো তার ওপর। এই কাজের জন্য কল্পিত একটি নির্দেশ, φ function (phi):
Block B-এর শুরুতে x = phi(P1: a1, …, Pk: ak), যেখানে P1 … Pk হলো B-এর সব predecessor. চলার সময় B-তে ঢোকা হয় একটি edge Pi → B দিয়ে; তখন x পায় ai-এর মান, অর্থাৎ Pi-এর শেষে ai-এর যে মান ছিল। B-এর শুরুর সব φ একসঙ্গে মান পড়ে, তারপর একসঙ্গে লেখে (সমান্তরাল অর্থ)।
রেলস্টেশনের একটি জংশনের কথা ভাবুন। কোন লাইন দিয়ে ট্রেন এল তা দেখে স্টেশনমাস্টার ঘোষণা বাছেন; φ-ও কিছু হিসাব করে না, শুধু আগত পথ দেখে মান বাছে। “একসঙ্গে” শর্তটি জরুরি। ধরুন একটি loop-এর মাথায় a#2 = phi(B0: a#1, B2: b#2) আর b#2 = phi(B0: b#1, B2: a#2): প্রতিবার ঘুরলে a আর b অদলবদল হয়। দ্বিতীয় φ-এ a#2 মানে পুরোনো a#2, অর্থাৎ B2-এর শেষের মান, কারণ সব φ একসঙ্গে পড়ে। পরপর চালালে দ্বিতীয়টি নতুন a#2 পড়ত, আর অদলবদল ভেঙে যেত। অংশ ৮-এ ঠিক এই ভুলটি সত্যিকারের run-এ দেখবেন।
পর্ব ৬২-এর IR interpreter run_ir আগে থেকেই φ বোঝে, আর এই পর্ব সেটি অপরিবর্তিত ব্যবহার করে। Block-এ ঢোকার সময় তার enter শুরুর সব φ-এর মান আগে পড়ে, তারপর লেখে, ঠিক সংজ্ঞা ৬৩.২-এর মতো; predecessor চেনে frame-এ রাখা আগের block দেখে। লেখকের lab-এর পরীক্ষায় পাওয়া দুটি সীমা: (ক) enter শুধু লাফের সময় চলে, তাই B0-র φ function শুরুতে চলত না; entry-তে φ থাকার কথাও নয়, আর to_ssa তখন স্পষ্ট error দেয় (অনুশীলন ১)। (খ) φ চলা-নির্দেশের গণনায় আসে না।
φ কোনো সত্যিকারের নির্দেশ নয়। কোনো CPU-তে “কোন পথে এলাম দেখে মান বাছো” নির্দেশ নেই। φ হলো compiler-এর বিশ্লেষণের জন্য একটি চিহ্ন। Code generation-এর আগে প্রতিটি φ ভেঙে predecessor-গুলোর শেষে সাধারণ copy বসাতে হয় (অংশ ৮)। কেউ যদি বলে “φ মানে দুই দিক হিসাব করে একটি বেছে নেওয়া”, সেটি ভুল: φ কিছুই হিসাব করে না, শুধু আগেই হিসাব হওয়া একটি মান বাছে।
৩ · Dominator আর dominator tree
φ কোথায় লাগবে, তা বোঝার চাবি একটি সম্পর্ক। একটি গ্রামের হাটে যাওয়ার সব রাস্তা যদি একটি নির্দিষ্ট সেতু দিয়ে যায়, তবে সেই সেতু হাটের ওপর “আধিপত্য” রাখে: সেতুতে যা ঘটে, হাটে পৌঁছানো প্রত্যেকে তা পেরিয়ে আসে। CFG-তে একই কথা:
Block a dominates block b (লেখা a dom b), যদি B0 থেকে b-তে যাওয়ার প্রতিটি পথ a দিয়ে যায়। প্রতিটি block নিজেকে dominate করে। a ≠ b আর a dom b হলে a strictly dominates b. b-এর strict dominator-দের মধ্যে যেটি b-এর সবচেয়ে কাছে (বাকি সবাইকে নিজেও dominate করা হয় তার দ্বারা), সেটি b-এর immediate dominator, idom(b).
bags-এ: B0 সবাইকে dominate করে (সব পথ এখান থেকেই শুরু)। B1 (loop-এর মাথা) B2, B3, B4, B5 সবাইকে dominate করে, কারণ loop-এর পরে যেতে হলে শর্ত পেরোতেই হয়। B3 dominates B4 আর B5. কিন্তু B4 B5-কে dominate করে না: B3 থেকে সরাসরি B5-এ যাওয়ার পথ আছে, B4 বাদ দিয়ে। Dominance একটি partial order: reflexive (a dom a), antisymmetric (a dom b আর b dom a হলে a = b), transitive (a dom b, b dom c হলে a dom c); partial order-এর গণিত আছে Discrete Math কোর্সের পর্ব ৫৬-এ। আরও একটি ধর্ম আছে: b-এর সব dominator একটি সারিতে সাজানো যায় (B0 dom … dom idom(b) dom b). তাই প্রতিটি block-এর idom ঠিক একটি (B0 বাদে), আর “idom(b) → b” edge-গুলো মিলে একটি গাছ: dominator tree (অনুশীলন ৪-এ এর প্রমাণ)।
Dominator খোঁজা — সমীকরণ থেকে Cooper–Harvey–Kennedy
সংজ্ঞা থেকে সরাসরি একটি সমীকরণ আসে: Dom(B0) = {B0}, আর অন্য b-এর জন্য Dom(b) = {b} ∪ ⋂p ∈ pred(b) Dom(p). অর্থাৎ b-এর dominator হলো b নিজে, আর তারা যারা b-এর প্রতিটি predecessor-কে dominate করে। শুরুতে সবাইকে “সব block” ধরে সমীকরণ বারবার চালালে একটি fixpoint-এ থামে; এটি একটি dataflow analysis, যার সাধারণ কাঠামো পর্ব ৬৪-এর বিষয়। কিন্তু প্রতিটি block-এর জন্য পুরো set রাখা ব্যয়বহুল।
Keith Cooper, Timothy Harvey আর Ken Kennedy ২০০১ সালের দিকে প্রকাশিত “A Simple, Fast Dominance Algorithm” প্রবন্ধে একটি চতুর সংক্ষেপ দেখান: set না রেখে শুধু idom রাখুন, কারণ dominator tree-তে idom-এর শিকল ধরে ওপরে উঠলেই পুরো Dom(b) পাওয়া যায়। তখন দুটি set-এর ছেদ মানে গাছে দুটি node-এর সবচেয়ে কাছের সাধারণ পূর্বপুরুষ খোঁজা। দুই আঙুল দুই block-এ রাখুন; যে আঙুলের block DFS-এর reverse postorder (RPO)-এ পরে, সেটিকে idom ধরে ওপরে তুলুন; দুই আঙুল মিললে সেটিই উত্তর। RPO-তে প্রতিটি block তার (back edge বাদে) সব predecessor-এর পরে আসে; DFS নিজে আছে DSA কোর্সের পর্ব ৪১-এ।
১. B0 থেকে DFS করে RPO আর প্রতিটি block-এর ক্রম-নম্বর num(b). ২. idom(B0) = B0; বাকিদের idom অজানা। ৩. RPO-তে B0-এর পরের প্রতিটি b-এর জন্য: new = b-এর প্রথম predecessor যার idom জানা; বাকি প্রতিটি জানা predecessor p-এর জন্য new = meet(p, new). new আগের idom(b) থেকে আলাদা হলে বদলান। ৪. একটি পুরো pass-এ কোনো বদল না হলে থামুন। meet(a, b): যতক্ষণ a ≠ b, বড় num-ওয়ালাটিকে তার idom-এ তুলুন।
1RPO: B0 B1 B3 B4 B5 B22B0 (num 0) entry3B1 (num 1) ← B0, B24B3 (num 2) ← B15B4 (num 3) ← B36B5 (num 4) ← B3, B47B2 (num 5) ← B18tree: B0→B1→{B2,B3}
| idom | |
| meet |
- প্রস্তুতি। B0 থেকে DFS: B0 → B1 → B2 (B1-এ ফেরা back edge), তারপর B3 → B4 → B5. শেষ হওয়ার উল্টো ক্রমে RPO: B0 B1 B3 B4 B5 B2. শুধু idom(B0) = B0 জানা।
- B1. Predecessor B0 আর B2; B2-এর idom এখনো অজানা, তাই শুধু B0 গোনা হয়: idom(B1) = B0.
- B3. একমাত্র predecessor B1, তাই idom(B3) = B1. একটি predecessor থাকলে সে-ই idom.
- B4. একইভাবে idom(B4) = B3.
- B5, প্রথম আসল meet. Predecessor B3 আর B4, দুজনের idom-ই জানা। meet(B4, B3): B4-এর num 3, B3-এর 2; বড়টি B4-কে তার idom B3-এ তোলা হয়; দুই আঙুল মিলল। idom(B5) = B3.
- B2. idom(B2) = B1. এই pass-এ অনেক কিছু বদলেছে, তাই আরেকটি pass.
- Pass ২. এবার B1-এর দুই predecessor-এর idom-ই জানা: meet(B2, B0): B2(5) → B1(1) → B0(0); ফল B0, আগের মতোই। বাকি block-গুলোও বদলায় না, তাই থামা।
- ফল. Dominator tree: B0 → B1; B1 → B2, B3; B3 → B4, B5. লেখকের lab-এ ৩,০০০টি এলোমেলো program-এর ৯,০০১টি function-এর সবগুলোয় বড়জোর ২টি pass লেগেছে, আর ফল set-ভিত্তিক সমীকরণের সঙ্গে প্রতিটি block-এ মিলেছে।
দুই pass-এ থামার কারণ: Haat-এর CFG সবসময় reducible (পর্ব ২৭), তাই back edge কখনো idom বদলায় না; দ্বিতীয় pass শুধু নিশ্চিত হয়। Irreducible graph-এ বেশি pass লাগতে পারে। কোড, haat_ssa.py থেকে হুবহু:
def rpo(fn): # reverse postorder: B0 থেকে DFS, শেষ হওয়ার উল্টো ক্রম
seen, order, stack = {"B0"}, [], [("B0", iter(succs(fn, "B0")))]
while stack:
b, it = stack[-1]
for s in it:
if s not in seen: seen.add(s); stack.append((s, iter(succs(fn, s)))); break
else: order.append(b); stack.pop()
return order[::-1]
def dominators(fn, trace=None): # Cooper–Harvey–Kennedy; ফেরত idom (idom["B0"] = "B0")
order, pred = rpo(fn), preds(fn)
num, idom = {b: k for k, b in enumerate(order)}, {"B0": "B0"}
def meet(a, b): # dominator tree-তে দুই আঙুল ওপরে তুলে মেলানো
while a != b:
while num[a] > num[b]: a = idom[a]
while num[b] > num[a]: b = idom[b]
return a
changed = True
while changed: # একটি পুরো pass-এ কিছু না বদলালে থামা
changed = False
for b in order[1:]:
ps = [p for p in pred[b] if p in idom] # যাদের idom এর মধ্যেই জানা
new = ps[0]
for p in ps[1:]: new = meet(p, new)
if idom.get(b) != new: idom[b], changed = new, True
if trace is not None: trace.append(dict(idom))
return idomrpo recursion ছাড়া, explicit stack দিয়ে DFS করে। trace দিলে প্রতিটি pass-এর পরের idom জমা হয়; stepper-এর সংখ্যা এভাবেই মেলানো। dominates(idom, a, b) b থেকে idom-এর শিকল ধরে ওপরে ওঠে আর দেখে a আসে কি না। অংশ ৬-এর ব্লকে এই সবকিছু একসঙ্গে চালিয়ে দেখবেন।
৪ · Dominance frontier — আধিপত্য যেখানে শেষ
ধরুন block d-তে x-এর একটি সংজ্ঞা আছে। d যে block-গুলোকে dominate করে, সেখানে x-এর এই মানটিই একমাত্র সম্ভাব্য মান (মাঝে আর কোনো সংজ্ঞা না থাকলে), কারণ সেখানে পৌঁছানো প্রতিটি পথ d পেরিয়ে আসে। গোলমাল শুরু হয় ঠিক সেই প্রথম block-গুলোতে, যেখানে d-এর আধিপত্য শেষ: সেখানে একটি পথ d থেকে আসে, অন্য পথ d ছাড়াই। সেখানেই দুটি ভিন্ন মান মেলে, আর সেখানেই φ লাগে।
DF(d) = { b : d dominates b-এর কোনো predecessor, কিন্তু d b-কে strictly dominate করে না }. কথায়: b-তে আসা অন্তত একটি edge-এর উৎস d-এর এলাকায়, কিন্তু b নিজে d-এর এলাকার ভেতরে নয় (b = d হতে পারে, যেমন loop-এর মাথা)। আর একটি set S-এর iterated dominance frontier DF+(S) হলো DF(S), তারপর DF(S ∪ DF(S)), … যতক্ষণ না বাড়া থামে।
bags-এ: DF(B2) = {B1}, কারণ B2 থেকে B1-এ edge আছে কিন্তু B2 B1-কে dominate করে না। DF(B1) = {B1}: B1 নিজে B2-কে dominate করে, B2 থেকে B1-এ edge, আর B1 নিজেকে strictly dominate করে না; তাই loop-এর মাথা নিজের frontier-এ। DF(B4) = {B5}. B0, B3 আর B5-এর frontier ফাঁকা। এখন dominance frontier-এর সংক্ষিপ্ত হিসাব, আবার Cooper–Harvey–Kennedy-র প্রবন্ধ থেকে: শুধু মিলনের block (দুই বা বেশি predecessor; B0-র ক্ষেত্রে বাইরে থেকে প্রবেশও একটি পথ) কারও frontier-এ পড়তে পারে। এমন প্রতিটি b-এর প্রতিটি predecessor p থেকে idom-এর শিকল ধরে idom(b) পর্যন্ত উঠুন; পথের প্রতিটি block-এর DF-এ b যোগ করুন।
def frontiers(fn, idom): # DF[b]: যেখানে b-এর আধিপত্য ঠিক শেষ হয়
df, pred = {b: set() for b in idom}, preds(fn)
for b in idom:
ps = [p for p in pred[b] if p in idom]
if len(ps) + (b == "B0") < 2: continue # শুধু মিলনের block (B0-তে বাইরে থেকেও ঢোকা যায়)
for p in ps:
r, stop = p, None if b == "B0" else idom[b]
while r != stop: df[r].add(b); r = None if r == "B0" else idom[r]
return dfB1-এর জন্য: predecessor B0 নিজেই idom(B1), তাই কিছু হয় না; predecessor B2 থেকে উঠি: B2 ≠ B0, তাই DF(B2) ∋ B1; idom(B2) = B1 ≠ B0, তাই DF(B1) ∋ B1; তারপর B0-এ থামা। এটুকুই। নিচের JavaScript ব্লক যেকোনো CFG-এর edge থেকে একই দুই algorithm চালিয়ে dominator tree আর প্রতিটি block-এর frontier আঁকে। উদাহরণটি পর্ব ৬২-এর stock_days, যার loop-এর শর্তে &&:
// CFG-এর edge থেকে dominator tree আর dominance frontier (Cooper–Harvey–Kennedy)
const CFG = `B0 -> B1
B1 -> B2 B3
B2 -> B3
B3 -> B4 B5
B4 -> B1`; // stock_days-এর CFG; নিজের edge বসিয়ে আবার চালান
const succ = {}, pred = {};
for (const line of CFG.split("\n")) {
const [b, rest] = line.split("->").map(s => s.trim());
succ[b] = rest.split(/\s+/);
for (const x of [b, ...succ[b]]) { pred[x] ??= []; succ[x] ??= []; }
succ[b].forEach(s => pred[s].push(b));
}
const order = [], seen = new Set(); // reverse postorder
(function dfs(b) { seen.add(b); succ[b].forEach(s => seen.has(s) || dfs(s)); order.unshift(b); })("B0");
const num = Object.fromEntries(order.map((b, k) => [b, k])), idom = { B0: "B0" }; let passes = 0, changed = true;
while (changed) {
changed = false; passes++;
for (const b of order.slice(1)) {
let nw = null;
for (const p of pred[b].filter(p => p in idom)) {
if (nw === null) { nw = p; continue; }
let a = p, c = nw; // দুই আঙুল ওপরে তুলে মেলানো
while (a !== c) { while (num[a] > num[c]) a = idom[a]; while (num[c] > num[a]) c = idom[c]; }
nw = a;
}
if (idom[b] !== nw) { idom[b] = nw; changed = true; }
}
}
const df = Object.fromEntries(order.map(b => [b, new Set()]));
for (const b of order) if (pred[b].length > 1)
for (let r of pred[b]) while (r !== idom[b]) { df[r].add(b); r = idom[r]; }
const show = (b, pad) => { console.log(pad + b + " DF {" + [...df[b]].join(", ") + "}");
order.filter(c => c !== b && idom[c] === b).forEach(c => show(c, pad + " ")); };
console.log("RPO:", order.join(" "), "· pass:", passes); show("B0", "");আসল আউটপুট (browser-এর JavaScript):
RPO: B0 B1 B2 B3 B5 B4 · pass: 2
B0 DF {}
B1 DF {B1}
B2 DF {B3}
B3 DF {B1}
B5 DF {}
B4 DF {B1}
Dominator tree-তে ভেতরে সরানো মানে “ওপরেরটি idom”. B1 (শর্তের বাঁ দিক) dominates B2 (&&-এর ডান দিক) আর B3 (আসল সিদ্ধান্ত), কারণ B3-তে দুই পথে আসা যায়, কিন্তু দুটিই B1 পেরিয়ে। DF(B2) = {B3}: &&-এর temp t2 B1 আর B2 দুই জায়গায় লেখা হয়, আর ঠিক B3-এ দুটি মেলে, তাই B3-এ t2-এর φ লাগবে (অনুশীলন ৩)। Loop-এর শরীর B4 আর শর্তের শেষ B3 দুটির frontier-ই loop-এর মাথা B1. Python-এর frontiers লেখকের lab-এ একই CFG-এ একই ফল দিয়েছে, আর ৯,০০১টি function-এ সংজ্ঞা ৬৩.৫ থেকে সরাসরি গোনা frontier-এর সঙ্গে প্রতিটি block-এ মিলেছে। নিজের CFG বসিয়ে দেখুন, যেমন একটি if-এর ভেতরে আরেকটি if.
ছবি ৬৩.২ — bags-এর dominator tree আর frontier
কালো রেখা: idom → সন্তান; কমলা ড্যাশ: d ⇢ DF(d)-এর block
n-এর সংজ্ঞা B0, B2 আর B4-এ, তাই তার φ বসবে DF(B2) ∪ DF(B4) = {B1, B5}-এ।৫ · φ বসানো — Cytron et al.-এর পদ্ধতি
কোথায় φ লাগবে, তার উত্তর এখন এক লাইনে: x-এর সংজ্ঞাগুলো যে block-এ, তাদের iterated dominance frontier-এ। “Iterated”, কারণ একটি φ নিজেও x-এর নতুন সংজ্ঞা, তাই তার frontier-এও φ লাগতে পারে। পদ্ধতিটি Ron Cytron, Jeanne Ferrante, Barry Rosen, Mark Wegman আর Kenneth Zadeck-এর ১৯৯১ সালের ACM TOPLAS প্রবন্ধের, যাকে সাধারণত SSA তৈরির ধ্রুপদী পদ্ধতি বলা হয় (ইতিহাস: ভাবনার প্রশ্ন ১)।
কিন্তু শুধু frontier মানলে মৃত φ-ও বসে। পর্ব ৬২-এর stock_days-এ &&-এর temp t2 লেখা হয় B1 আর B2-তে; DF(B2) = {B3}, তারপর DF(B3) = {B1}. তাহলে loop-এর মাথা B1-এও t2-এর φ? সেখানে পুরোনো t2 কেউ পড়ে না, আর B0 থেকে আসা পথে t2-এর মানই নেই। তাই তিন রকমের SSA:
| রূপ | φ কোথায় | খরচ আর ফল |
|---|---|---|
| Minimal SSA | x-এর সংজ্ঞার DF+-এর প্রতিটি block-এ | শুধু frontier লাগে; কিন্তু মৃত φ থাকে |
| Semi-pruned SSA | শুধু সেই নামের, যা কোনো block-এ সংজ্ঞার আগে পড়া হয় | সস্তা ছাঁটাই; block-এর ভেতরের temp বাদ পড়ে |
| Pruned SSA | DF+-এর সেই block-এ, যার শুরুতে x live | liveness লাগে; কোনো মৃত φ নেই |
“x live at b” মানে b-এর শুরু থেকে এমন একটি পথ আছে, যেখানে x আবার লেখার আগে পড়া হয়; এর হিসাব liveness analysis, একটি backward dataflow সমীকরণ: live-in(b) = use(b) ∪ (live-out(b) − def(b)), আর live-out(b) = b-এর successor-দের live-in-এর মিলন। পর্ব ৬৪ এটিকে সাধারণ framework-এ বসাবে; live_in তার সরাসরি রূপ (একই ধাঁচের প্রথম বিশ্লেষণ পর্ব ৫৪-এ)। Haat-এ use-before-declaration static নিয়মে ধরা পড়ে (reference-এর সিদ্ধান্ত ১৬), তাই নাম যেখানে live, সেখানে পৌঁছানোর প্রতিটি পথে তার সংজ্ঞা আছে: pruned SSA-র প্রতিটি φ-argument সংজ্ঞায়িত।
প্রতিটি নাম x-এর জন্য, যার সংজ্ঞা একাধিক (parameter একটি সংজ্ঞা গোনা হয়): work = x-এর সংজ্ঞাওয়ালা block-গুলো; done = ∅. যতক্ষণ work খালি নয়: একটি d তুলুন; DF(d)-এর প্রতিটি f-এর জন্য, যদি f ∉ done: f-কে done আর work-এ যোগ করুন (φ একটি নতুন সংজ্ঞা), আর x যদি f-এর শুরুতে live হয়, তবে f-এ x-এর একটি φ বসান। যে নাম একবারই লেখা হয়, সেটি আগে থেকেই SSA, তাকে ছোঁয়া হয় না।
1n-এর সংজ্ঞা: B0, B2, B42DF(B0) = { }3DF(B1) = {B1}4DF(B2) = {B1}5DF(B4) = {B5}6DF(B5) = { }7n live: B1, B2, B3, B4, B5
| work | |
| done | |
| φ(n) |
- শুরু।
nলেখা হয় B0, B2 আর B4-এ, তাই work-এ এই তিন block. কোনো φ এখনো নেই। Worklist থেকে শেষেরটি তোলা হয়। - B4 তোলা। DF(B4) = {B5}. B5-এর শুরুতে
nlive (return nসেখানে পড়ে), তাই B5-এ φ. B5 নিজেও এখনn-এর একটি সংজ্ঞা, তাই work-এ যায়। - B5 তোলা। DF(B5) ফাঁকা: B5-এর পরে আর কোনো মিলন নেই। কিছু বদলায় না।
- B2 তোলা। DF(B2) = {B1}. B1-এর শুরুতে
nlive (B3-এn > 3পড়ার পথ আছে), তাই B1-এ φ, আর B1 work-এ। - B1 তোলা। DF(B1) = {B1}, কিন্তু B1 আগেই done; দ্বিতীয় φ বসে না।
- B0 তোলা। DF(B0) ফাঁকা। Work খালি:
n-এর φ বসল B1 আর B5-এ, ঠিক ছবি ৬৩.১-এর মতো। left. সংজ্ঞা B0 আর B2-তে; একই কাজে φ শুধু B1-এ।t1…t7আরitemsএকবার লেখা, তাই তাদের কোনো φ নেই।bags-এ minimal আর pruned SSA একই, কারণ যেখানে φ বসে সেখানে নামটি live.
def place_phis(fn, df, live): # Cytron et al.: iterated frontier, শুধু live নামের φ (pruned)
where, ndef = {}, {p: 1 for p in fn.params}
for b, body in fn.blocks.items():
for i in body:
if i.dst and i.dst[0] != "@":
where.setdefault(i.dst, set()).add(b); ndef[i.dst] = ndef.get(i.dst, 0) + 1
multi = {x for x in where if ndef[x] > 1} # একবার লেখা নাম আগে থেকেই SSA
phis = {b: [] for b in fn.blocks}
for x in sorted(multi):
work, done = sorted(where[x]), set()
while work:
for f in sorted(df.get(work.pop(), ())):
if f in done: continue
done.add(f); work.append(f) # φ নিজেও x-এর একটি নতুন সংজ্ঞা
if x in live[f]: phis[f].append(x)
return multi, phisছাঁটাই কতটা কাজে লাগে, তার সত্যিকারের মাপ লেখকের lab থেকে (CPython 3.14.4): পর্ব ৬২-এর haat_gen.py-র প্রথম ৩,০০০টি এলোমেলো program-এর ৯,০০১টি function-এ minimal SSA বসাত ৩০,০৬১টি φ, আর pruned SSA বসিয়েছে ১৫,৬৭০টি; প্রায় অর্ধেক φ ছিল মৃত।
৬ · নাম বদল — dominator tree আর stack
φ বসানো হলো; এখন প্রতিটি সংজ্ঞাকে একটি নতুন নাম দিতে হবে, আর প্রতিটি ব্যবহারকে ঠিক সেই নামটি, যার সংজ্ঞা সেখানে পৌঁছায়। কৌশলটি dominator tree-তে একটি DFS. লাইব্রেরির তাকে বই রাখার কথা ভাবুন: একটি তাকে পরপর বই রাখা হয়, সবচেয়ে ওপরেরটিই “বর্তমান”। একটি ঘরে (subtree) ঢুকে যা রাখলেন, ঘর থেকে বেরোনোর সময় তা তুলে নিন; বাইরের ঘর তখন আবার তার নিজের বইটি ওপরে দেখে। প্রতিটি নাম x-এর জন্য একটি stack, যার মাথায় x-এর বর্তমান SSA নাম।
rename(b): (১) b-এর প্রতিটি φ x = phi(…)-এর dst-কে নতুন নাম x#k দিন, stack[x]-এ ঠেলুন। (২) b-এর প্রতিটি সাধারণ নির্দেশে: প্রতিটি পড়া নাম a-কে top(stack[a]) দিয়ে বদলান; তারপর লেখা নাম x-কে নতুন x#k দিন আর ঠেলুন। (৩) b-এর প্রতিটি CFG successor s-এর প্রতিটি φ-তে, b থেকে আসা জোড়াটি ভরুন: (b: top(stack[x])). (৪) Dominator tree-তে b-এর প্রতিটি সন্তান c-এর জন্য rename(c). (৫) এই block-এ যা ঠেলেছিলেন, সব তুলে নিন। শুরু: rename(B0), আর parameter-এর stack-এ তার নিজের নাম।
ধাপ (২)-এ আগে পড়া, পরে লেখা, যাতে n = n + t4-এর ডান দিক পুরোনো নাম পায়। ধাপ (৩)-এ successor CFG-র, ধাপ (৪)-এ সন্তান dominator tree-র: b-এর সংজ্ঞা দেখা যায় শুধু b-এর subtree-তে।
1B0: n = 0; left = items2B1: φ left; φ n; t2 = …3B2: left = …; n = n + t44B3: t6 = n > t55B4: n = n - t76B5: φ n; return n7সব block শেষ
| n | |
| left | |
| নতুন |
- B0.
nআরleftনতুন নাম পায়:n#1,left#1;itemsparameter, একবার লেখা, অপরিবর্তিত। CFG successor B1-এর দুই φ-তে B0-এর জোড়া ভরা হয়। - B1 (B0-এর সন্তান). আগে φ:
left#2,n#2stack-এ ওঠে। তারপরt2 = left > t1-এleftহয়left#2. Successor B2 আর B3-এ φ নেই। - B2 (B1-এর প্রথম সন্তান).
left#3 = left#2 - t3,n#3 = n#2 + t4: ডান দিক আগে, তাই পুরোনো নাম। Successor B1-এর φ-তে B2-এর জোড়া:left#3আরn#3. B2-এর কোনো সন্তান নেই। - B2 থেকে বেরোনো, B3-এ ঢোকা। B2-এ ঠেলা দুটি নাম নামে;
n-এর মাথা আবারn#2. তাই B3-এরn > t5পড়েn#2, loop শেষে φ-এর মান, যা ঠিক। B5-এর φ পায় (B3: n#2). - B4.
n#4 = n#2 - t7; B5-এর φ পায় (B4: n#4). - B5. B4-এর নাম নেমে গেছে। B5-এর φ নতুন নাম পায়
n#5, আরreturn nহয়return n#5. - শেষ। সব subtree থেকে বেরিয়ে সব stack খালি। ফল ছবি ৬৩.১: তিনটি φ, আর প্রতিটি নামের একটিই সংজ্ঞা।
আসল কোড। to_ssa নতুন IRFunction ফেরত দেয়, মূলটি ছোঁয় না। নাম বদল recursion ছাড়া, todo stack-এ ("in", b) আর ("out", b) দিয়ে; base মনে রাখে কোন নতুন নাম কোন মূল নামের।
def to_ssa(fn): # নতুন IRFunction, SSA রূপে; fn নিজে অপরিবর্তিত
idom = dominators(fn); kids = dom_tree(idom)
multi, phis = place_phis(fn, frontiers(fn, idom), live_in(fn))
if phis["B0"]: raise ValueError("B0-তে φ লাগবে: entry-র আগে একটি নতুন block দিন")
new = IRFunction(fn.name, list(fn.params))
new.blocks = {b: [Ins("phi", x) for x in phis[b]] +
[replace(i, args=list(i.args), targets=list(i.targets)) for i in body]
for b, body in fn.blocks.items() if b in idom}
count, base = {x: 0 for x in multi}, {}
stack = {x: [x] if x in fn.params else [] for x in multi}
todo, pushed = [("in", "B0")], {}
while todo: # dominator tree-তে DFS; Python-এর recursion ছাড়া
step, b = todo.pop()
if step == "out":
for x in pushed[b]: stack[x].pop() # এই subtree শেষ: তার নামগুলো stack থেকে নামে
continue
pushed[b] = []
for i in new.blocks[b]:
if i.kind != "phi": i.args = [stack[a][-1] if a in multi else a for a in i.args]
if i.dst in multi:
x = i.dst; count[x] += 1; i.dst = f"{x}#{count[x]}"
base[i.dst] = x; stack[x].append(i.dst); pushed[b].append(x)
for s in succs(new, b): # successor-এর φ-তে এই পথের মান
for p in new.blocks[s]:
if p.kind != "phi": break
p.args.append(stack[base.get(p.dst, p.dst)][-1]); p.targets.append(b)
todo.append(("out", b)); todo += [("in", c) for c in reversed(kids[b])]
return sort_phis(new)এবার পুরো পথ এক ব্লকে: dominator, frontier, live নাম, φ কোথায়, তারপর to_ssa আর যাচাই।
# bags: dominator, frontier, কোথায় φ — তারপর to_ssa আর যাচাই (সব haat_ssa.py থেকে)
from haat_ssa import *
src = """fn bags(items: Int) -> Int {
var n = 0;
var left = items;
while left > 0 {
left = left - 6;
n = n + 1;
}
if n > 3 { n = n - 1; }
return n;
}
print(bags(20));
print(bags(6));
""" # src বদলে আবার চালান
mod = compile_ir(src); fn = mod.funcs["bags"]
passes = []; idom = dominators(fn, passes)
print("RPO:", " ".join(rpo(fn)), "· pass:", len(passes))
print("dominator tree:", {b: k for b, k in dom_tree(idom).items() if k})
print("B3 dom B5?", dominates(idom, "B3", "B5"), "· B4 dom B5?", dominates(idom, "B4", "B5"))
df, live = frontiers(fn, idom), live_in(fn)
print("DF:", {b: sorted(s) for b, s in df.items() if s})
print("live-in:", {b: sorted(s) for b, s in live.items()})
print("φ:", {b: x for b, x in place_phis(fn, df, live)[1].items() if x})
ssa = map_module(mod, to_ssa) # প্রতিটি function-এর SSA রূপ; mod অপরিবর্তিত
print(show_ir(ssa.funcs["bags"]))
print("check_ssa:", check_ssa(ssa.funcs["bags"]) or "ঠিক আছে")
print("আগে:", run_lines(mod), "· SSA:", run_lines(ssa))
print("চলা নির্দেশ:", run_ir(mod, out=lambda s: None), "→", run_ir(ssa, out=lambda s: None))
bad = to_ssa(fn); bad.blocks["B2"][3].args[0] = "n#4" # ইচ্ছাকৃত ভুল নাম
print("ভুল নামে:", check_ssa(bad))আসল আউটপুট (ব্রাউজারের Python):
RPO: B0 B1 B3 B4 B5 B2 · pass: 2
dominator tree: {'B0': ['B1'], 'B1': ['B2', 'B3'], 'B3': ['B4', 'B5']}
B3 dom B5? True · B4 dom B5? False
DF: {'B1': ['B1'], 'B4': ['B5'], 'B2': ['B1']}
live-in: {'B0': ['items'], 'B1': ['left', 'n'], 'B2': ['left', 'n'], 'B3': ['n'], 'B4': ['n'], 'B5': ['n']}
φ: {'B1': ['left', 'n'], 'B5': ['n']}
fn bags(items):
B0:
n#1 = const 0
left#1 = items
jump B1
B1:
left#2 = phi(B0: left#1, B2: left#3)
n#2 = phi(B0: n#1, B2: n#3)
t1 = const 0
t2 = left#2 > t1
branch t2 B2 B3
B2:
t3 = const 6
left#3 = left#2 - t3
t4 = const 1
n#3 = n#2 + t4
jump B1
B3:
t5 = const 3
t6 = n#2 > t5
branch t6 B4 B5
B4:
t7 = const 1
n#4 = n#2 - t7
jump B5
B5:
n#5 = phi(B3: n#2, B4: n#4)
return n#5
check_ssa: ঠিক আছে
আগে: ['3', '1'] · SSA: ['3', '1']
চলা নির্দেশ: 71 → 71
ভুল নামে: ['B2: n#4-এর সংজ্ঞা ব্যবহারকে dominate করে না']
প্রথম লাইনগুলো অংশ ৩–৫-এর stepper-এর সঙ্গে মেলে: RPO, ২টি pass, dominator tree, frontier, আর তিনটি φ-এর জায়গা। B5-এর idom-শিকল B5 → B3 → B1 → B0, তাতে B3 আছে, B4 নেই। SSA রূপটি নাম বদলের stepper-এর সঙ্গে হুবহু মেলে। আউটপুট আগে আর পরে একই (3 আর 1), আর reference-এর haat.py run-ও তাই ছাপে। চলা-নির্দেশ ৭১-ই থাকল: φ গোনা হয় না, আর নাম বদলে কোনো নির্দেশ যোগ বা বাদ হয় না। শেষ লাইনটি ইচ্ছাকৃত ভুল: B2-এ n#3 = n#2 + t4-কে n#4 + t4 বানানো হয়েছে, আর n#4-এর সংজ্ঞা B4-এ, যা B2-কে dominate করে না। check_ssa (অংশ ৭) সেটি ধরে।
৭ · SSA ঠিক আছে কি না — শর্ত, যুক্তি আর differential test
একটি SSA রূপ দুই দিক থেকে যাচাই করা যায়: গঠন (সংজ্ঞা ৬৩.১-এর শর্ত মানে কি?) আর অর্থ (চালালে কি একই আউটপুট?)। গঠনের জন্য check_ssa: প্রতিটি নামের সংজ্ঞা একবার, আর প্রতিটি ব্যবহারকে তার সংজ্ঞা dominate করে। φ-এর argument-এর ব্যবহার ধরা হয় predecessor-এর শেষে, কারণ মানটি সেখানে পড়া হয়।
def check_ssa(fn): # SSA-র দুই শর্ত: এক নামে এক সংজ্ঞা, আর সংজ্ঞা ব্যবহারকে dominate করে
idom, where, bad = dominators(fn), {p: ("B0", -1) for p in fn.params}, []
for b, body in fn.blocks.items():
for k, i in enumerate(body):
if i.dst and i.dst[0] != "@":
if i.dst in where: bad.append(f"{i.dst}: একাধিক সংজ্ঞা")
where[i.dst] = (b, k)
for b, body in fn.blocks.items():
for k, i in enumerate(body):
for n, a in enumerate(i.args):
if a[0] == "@": continue
if a not in where: bad.append(f"{b}: {a}-এর সংজ্ঞা নেই"); continue
db, dk = where[a]
ub, uk = (i.targets[n], len(fn.blocks[i.targets[n]])) if i.kind == "phi" else (b, k)
if not (dominates(idom, db, ub) and (db != ub or dk < uk)):
bad.append(f"{b}: {a}-এর সংজ্ঞা ব্যবহারকে dominate করে না")
return badদাবি: অ্যালগরিদম ৬৩.৭-এর পরে প্রতিটি সাধারণ নির্দেশের প্রতিটি ব্যবহার a#k-এর সংজ্ঞা সেই ব্যবহারকে dominate করে, আর চলার সময় a#k-এর মান মূল program-এ সেই বিন্দুতে a-এর মানের সমান।
- Rename(b) চলার সময় stack[a]-তে আছে ঠিক সেই নামগুলো, যাদের সংজ্ঞা dominator tree-তে B0 থেকে b পর্যন্ত পথের block-গুলোতে (ধাপ ৫ বেরোনোর সময় বাকিগুলো নামিয়ে দেয়)। তাই top(stack[a])-এর সংজ্ঞা b-কে dominate করে, বা b-এর ভেতরেই আগে আছে।
- ধরুন b-এর একটি বিন্দুতে মূল program-এ a-এর মান এসেছে সংজ্ঞা d থেকে। d যদি b-এর dominator-শিকলে না থাকে, তবে d থেকে b পর্যন্ত কোনো পথে প্রথম যে block-এ d-এর আধিপত্য শেষ হয়, সেটি DF(d)-এ; সেখানে a live (b-তে a পড়া হয়), তাই অ্যালগরিদম ৬৩.৬ সেখানে a-এর একটি φ বসিয়েছে, যা নিজেও একটি সংজ্ঞা। এভাবে iterated frontier ধরে এগোলে b-এর ঠিক আগের শেষ সংজ্ঞাটি b-এর dominator-শিকলে পড়ে, আর সেটিই stack-এর মাথা।
- φ-এর জোড়া (p: top(stack[a])) ভরা হয় rename(p)-এর শেষে, যখন stack-এ p-এর শেষের মান; সংজ্ঞা ৬৩.২-এর “Pi-এর শেষে ai-এর মান” ঠিক এটিই। ∎
যুক্তির পাশাপাশি এই মডিউলের স্থায়ী নিয়ম: চালিয়ে মেলানো। নিচের ব্লক পর্ব ৬২-এর একই উদাহরণ আর এলোমেলো program নিয়ে প্রতিটির তিনটি রূপ চালায়: মূল IR, SSA, আর SSA থেকে ফেরা IR (অংশ ৮)। দুটি closure-ওয়ালা উদাহরণ (counter, nested) Haat IR v1-এর বাইরে, পর্ব ৬২-তেই বাদ, তাই এখানে ৮টি।
# ধাপ ৪: SSA আর SSA থেকে ফেরা IR — reference-এর `haat.py run`-এর সঙ্গে হুবহু?
import hashlib
from haat_ssa import * # to_ssa, out_of_ssa, check_ssa, map_module …
from haat_gen import gen_program
def digest(lines): return hashlib.sha256("\n".join(lines).encode()).hexdigest()[:10]
def three(src): # একই program-এর তিন রূপ: IR, SSA, SSA থেকে ফেরা
mod = compile_ir(src); ssa = map_module(mod, to_ssa)
return mod, ssa, map_module(ssa, out_of_ssa)
def phis(m): return sum(i.kind == "phi" for f in m.funcs.values() for b in f.blocks.values() for i in b)
def errs(m): return sum(len(check_ssa(f)) for f in m.funcs.values())
same, bad, nphi = [0, 0], 0, 0
for name in ("bazar", "recursion", "mutual", "shadowing", "shortcircuit", "strings", "loops", "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, ssa, back = three(src)
same[0] += run_lines(ssa) == want; same[1] += run_lines(back) == want; bad += errs(ssa)
print(f"উদাহরণ ৮টি: SSA {same[0]}টি, ফেরা {same[1]}টি হুবহু")
ref = open("random_ref.txt", encoding="utf-8").read().split()
ok = [0, 0]
for s in range(len(ref)):
mod, ssa, back = three(gen_program(s))
ok[0] += digest(run_lines(ssa)) == ref[s]; ok[1] += digest(run_lines(back)) == ref[s]
bad += errs(ssa); nphi += phis(ssa); assert phis(back) == 0
print(f"এলোমেলো {len(ref)}টি: SSA {ok[0]}, ফেরা {ok[1]} হুবহু · φ {nphi}টি · check_ssa-র আপত্তি {bad}")
mod, ssa, back = three(open("examples/bazar.haat", encoding="utf-8").read())
print("bazar-এর <main>, B1:", *ssa.funcs["<main>"].blocks["B1"], sep="\n ")
print("bazar চলা নির্দেশ (IR, SSA, ফেরা):", [run_ir(m, out=lambda s: None) for m in (mod, ssa, back)])আসল আউটপুট (ব্রাউজারের Python):
উদাহরণ ৮টি: SSA 8টি, ফেরা 8টি হুবহু
এলোমেলো 200টি: SSA 200, ফেরা 200 হুবহু · φ 999টি · check_ssa-র আপত্তি 0
bazar-এর <main>, B1:
rounds#2 = phi(B0: rounds#1, B2: rounds#3)
total#2 = phi(B0: total#1, B2: total#3)
t8 = const 5000
t9 = total#2 < t8
branch t9 B2 B3
bazar চলা নির্দেশ (IR, SSA, ফেরা): [74, 74, 84]
৮টি উদাহরণ আর ২০০টি এলোমেলো program-এ SSA আর ফেরা IR দুটিই reference-এর run-এর সঙ্গে অক্ষরে অক্ষরে এক, err_divzero-এর 3:18: runtime error: division by zero-সহ: নাম বদলে নির্দেশের pos হারায় না। bazar.haat-এর <main>-এ loop-এর মাথায় rounds আর total-এর দুটি φ. চলা-নির্দেশ ৭৪ থেকে ৭৪ (φ গোনা হয় না), আর SSA থেকে ফিরলে ৮৪: প্রতিটি φ-এর জায়গায় copy এসেছে। লেখকের lab-এ বড় পরীক্ষা: প্রথম ৩,০০০টি seed-এর সবগুলোয় (২,৬৭৫টি স্বাভাবিক শেষ, ৩২৫টি division by zero) SSA আর ফেরা IR দুটিই reference-এর run-এর সঙ্গে হুবহু; ৯,০০১টি function-এর ৪,৬২৯টিতে অন্তত একটি φ; check_ssa-র আপত্তি শূন্য; আর হাতে লেখা ১০টি কিনারার program (শুরুতেই while, খালি then/else, nested loop, loop-এ let আর shadowing, global, loop-এ শূন্য দিয়ে ভাগ ইত্যাদি) সবগুলো মিলেছে।
৮ · SSA থেকে ফেরা — copy, critical edge, lost copy আর swap
যন্ত্রে φ নেই, তাই code generation-এর আগে SSA থেকে ফেরা (out-of-SSA, SSA destruction) লাগে। মূল ধারণা সরল: x = phi(P1: a1, …, Pk: ak) মানে “Pi থেকে এলে x = ai”; তাই প্রতিটি Pi-এর শেষে, terminator-এর ঠিক আগে, একটি copy x = ai বসান, আর φ মুছে দিন। দুটি জায়গায় এই সরল পদ্ধতি ভাঙে।
এক, critical edge. যে edge-এর উৎসের একাধিক successor আর লক্ষ্যের একাধিক predecessor, সেটি critical. উৎসের শেষে copy বসালে সেটি অন্য successor-এর পথেও চলে (bags-এ B3 → B5). সমাধান: edge ভাগ করে মাঝে নতুন block, copy সেখানে। out_of_ssa branch-এ শেষ হওয়া প্রতিটি predecessor-এর edge ভাগ করে, যাতে copy শর্তের নামও না বদলায়।
দুই, সমান্তরাল copy. একটি block-এর সব φ একসঙ্গে মান নেয় (সংজ্ঞা ৬৩.২), তাই একটি predecessor-এর copy-গুলোও একটি parallel copy: সব ডান দিক আগে পড়া, তারপর সব বাম দিক লেখা। পরপর চালানোর জন্য একটি নিরাপদ ক্রম লাগে: যে d এখনো বাকি কোনো copy-র উৎস নয়, তাকে আগে লেখা যায়; আর শুধু চক্র বাকি থাকলে (a ← b, b ← a) একটি মান নতুন temp-এ বাঁচিয়ে রাখতে হয়।
def sequentialize(copies, fresh): # সমান্তরাল copy (সব d ← s একসঙ্গে) -> পরপর copy
todo, out = [(d, s) for d, s in copies if d != s], []
while todo:
for k, (d, s) in enumerate(todo):
if all(s2 != d for _, s2 in todo): # d আর কারও উৎস নয়: এখনই লেখা নিরাপদ
out.append(Ins("copy", d, [s])); del todo[k]; break
else: # বাকি শুধু চক্র (a ← b, b ← a): d-এর মান temp-এ বাঁচানো
d, t = todo[0][0], fresh(); out.append(Ins("copy", t, [d]))
todo = [(d2, t if s2 == d else s2) for d2, s2 in todo]
return out
def out_of_ssa(fn): # φ সরিয়ে predecessor-এ copy; নতুন IRFunction
new = IRFunction(fn.name, list(fn.params), blocks={b: [replace(i, args=list(i.args),
targets=list(i.targets)) for i in body] for b, body in fn.blocks.items()})
names = [i.dst for body in new.blocks.values() for i in body if i.dst]
nt = [max([int(x[1:]) for x in names if is_temp(x)] + [0])]
nb = max(int(b[1:]) for b in new.blocks)
def fresh(): nt[0] += 1; return f"t{nt[0]}"
for s in list(new.blocks):
phis = [i for i in new.blocks[s] if i.kind == "phi"]
for p in (list(dict.fromkeys(phis[0].targets)) if phis else []):
last = new.blocks[p][-1]
if last.kind == "branch": # critical edge p -> s: মাঝে নতুন block, copy সেখানে
nb += 1; m = f"B{nb}"; new.blocks[m] = [Ins("jump", targets=[s])]
last.targets = [m if t == s else t for t in last.targets]
for i in phis: i.targets = [m if t == p else t for t in i.targets]
p = m
copies = [(i.dst, i.args[i.targets.index(p)]) for i in phis]
new.blocks[p][-1:-1] = sequentialize(copies, fresh) # terminator-এর ঠিক আগে
new.blocks[s] = new.blocks[s][len(phis):]
return newbags-এর SSA থেকে ফেরা রূপ, লেখকের lab-এ সত্যিকারের run. B3 → B5 critical edge ভাগ হয়ে নতুন B6 এসেছে, আর B0 আর B2-এর শেষে loop-এর φ-গুলোর copy:
fn bags(items):
B0:
n#1 = const 0
left#1 = items
left#2 = left#1
n#2 = n#1
jump B1
B1:
t1 = const 0
t2 = left#2 > t1
branch t2 B2 B3
B2:
t3 = const 6
left#3 = left#2 - t3
t4 = const 1
n#3 = n#2 + t4
left#2 = left#3
n#2 = n#3
jump B1
B3:
t5 = const 3
t6 = n#2 > t5
branch t6 B4 B6
B4:
t7 = const 1
n#4 = n#2 - t7
n#5 = n#4
jump B5
B5:
return n#5
B6:
n#5 = n#2
jump B5
left#2 = left#3-এর মতো copy পরের ঘোরার মান বয়ে নেয়; register allocator দুটিকে একই register দিলে (coalescing) copy উধাও। এবার দুটি বিখ্যাত বিপদ, যা Preston Briggs, Keith Cooper, Timothy Harvey আর Taylor Simpson-এর ১৯৯৮ সালের প্রবন্ধে নাম পায়: lost-copy problem আর swap problem. দুটিই আসে SSA-র ওপর optimization চলার পরে, বিশেষত copy propagation (x = y থাকলে x-এর ব্যবহারে সরাসরি y; পর্ব ৬৫)। নিচের ব্লকে সরল পদ্ধতি আর out_of_ssa পাশাপাশি:
from haat_ssa import *
def naive(fn): # ভুল সরল পদ্ধতি: φ-এর প্রতিটি জোড়ার জন্য predecessor-এ একটি copy
new = IRFunction(fn.name, fn.params, blocks={b: [replace(i, args=list(i.args)) for i in body] for b, body in fn.blocks.items()})
for s, body in new.blocks.items():
for i in [i for i in body if i.kind == "phi"]:
for p, a in zip(i.targets, i.args): new.blocks[p].insert(-1, Ins("copy", i.dst, [a]))
new.blocks[s] = [i for i in body if i.kind != "phi"]
return new
def copyprop(fn): # SSA-তে x = y হলে x-এর সব ব্যবহারে y (পর্ব ৬৫-এর একটি pass)
sub = {i.dst: i.args[0] for b in fn.blocks.values() for i in b if i.kind == "copy" and "@" not in i.dst + i.args[0]}
def root(a): return root(sub[a]) if a in sub else a
for body in fn.blocks.values():
for i in body: i.args = [root(a) for a in i.args]
body[:] = [i for i in body if i.dst not in sub]
return fn
src = "var a = 1; var b = 2; var k = 0; while k < 3 { let t = a; a = b; b = t; k = k + 1; } print(a); print(b);"
swap = map_module(map_module(compile_ir(src), to_ssa), copyprop)
print(*swap.funcs["<main>"].blocks["B1"][:2], sep="\n")
lost = IRModule({"<main>": parse_ir("""fn <main>():
B0:
i#1 = const 0
n = const 3
one = const 1
jump B1
B1:
i#2 = phi(B0: i#1, B1: i#3)
i#3 = i#2 + one
t1 = i#3 < n
branch t1 B1 B2
B2:
print i#2
return one""")}, [])
for name, m in (("swap", swap), ("lost", lost)):
print(name, "· SSA:", run_lines(m), "· সরল:", run_lines(map_module(m, naive)), "· out_of_ssa:", run_lines(map_module(m, out_of_ssa)))
print(*out_of_ssa(swap.funcs["<main>"]).blocks["B2"], sep="\n")আসল আউটপুট (ব্রাউজারের Python):
a#2 = phi(B0: a#1, B2: b#2)
b#2 = phi(B0: b#1, B2: a#2)
swap · SSA: ['2', '1'] · সরল: ['2', '2'] · out_of_ssa: ['2', '1']
lost · SSA: ['2'] · সরল: ['3'] · out_of_ssa: ['2']
t3 = const 1
k#3 = k#2 + t3
k#2 = k#3
t5 = a#2
a#2 = b#2
b#2 = t5
jump B1
Swap: তিনবার অদলবদলের পরে a = 2, b = 1 (reference-এর run-ও তাই)। Copy propagation-এর পরে loop-এর মাথার দুটি φ একে অপরকে পড়ে। সরল পদ্ধতি B2-এর শেষে লেখে a#2 = b#2, তারপর b#2 = a#2; দ্বিতীয়টি নতুন a#2 পড়ে, তাই 2, 2. out_of_ssa-এর শেষ সাতটি লাইন B2: আগে চক্রের বাইরের k#2 = k#3, তারপর t5 = a#2 দিয়ে চক্র ভাঙা। Lost copy: হাতে লেখা SSA, যেখানে B1 একই সঙ্গে loop-এর মাথা আর শেষ (do-while-এর মতো), আর loop-এর পরে পুরোনো i#2 পড়া হয়। সরল পদ্ধতি B1-এর শেষে i#2 = i#3 বসায়, যা loop থেকে বেরোনোর পথেও চলে, তাই 3; সঠিক উত্তর 2. B1 → B1 edge critical; ভাগ করে copy মাঝের block-এ রাখলে পুরোনো মান বাঁচে।
1a#2 ← b#22b#2 ← a#23k#2 ← k#3
| বাকি | |
| লেখা হলো |
- সমান্তরাল copy. Loop-এর মাথার তিনটি φ থেকে B2-এর শেষে তিনটি copy, যারা একসঙ্গে ঘটার কথা: a আর b অদলবদল, k এক ধাপ বাড়ে।
- নিরাপদটি আগে।
a#2বাকি একটি copy-র উৎস (b#2 ← a#2),b#2-ও তাই; কিন্তুk#2কারও উৎস নয়, তাইk#2 = k#3এখনই লেখা যায়। - চক্র। বাকি দুটি একে অপরের উৎস; কোনোটিই আগে লেখা নিরাপদ নয়। নতুন temp
t5 = a#2পুরোনো a বাঁচায়, আর বাকি copy-তে উৎস a#2 বদলে হয় t5. - এবার a#2. a#2 আর কারও উৎস নয়:
a#2 = b#2. - শেষ।
b#2 = t5. চারটি copy, ফল সমান্তরাল অর্থের সমান। Temp-এর নম্বর ৫, কারণ function-এ t1 … t4 আগেই আছে।
লেখকের lab-এর একটি সৎ ফল: ৩,০০০টি এলোমেলো program-এ সরল পদ্ধতিও প্রতিটিতে সঠিক, copyprop-এর পরেও, কারণ Haat-এর loop-এর শর্ত সবসময় মাথায় আর generator অদলবদল বানায় না (out_of_ssa সেখানে ১০,০২২টি edge ভাগ করেছে)। তাই এলোমেলো test-এর পাশে প্রতিটি পরিচিত বিপদের জন্য বাছাই করা উদাহরণ রাখুন।
৯ · বাস্তব compiler-এ SSA — সত্যিকারের Clang
পর্ব ৬২-এ Clang-এর -O2 IR-এ একটি phi দেখেছিলেন। LLVM IR শুরু থেকেই SSA: প্রতিটি %নাম একবার সংজ্ঞায়িত। কিন্তু Clang-এর front end প্রথমে SSA লেখে না; সে প্রতিটি local variable-কে memory-তে রাখে (alloca, load, store), কারণ memory-তে বহুবার লেখা SSA ভাঙে না। তারপর একটি pass memory-কে register-এ তুলে φ বসায়: ধ্রুপদী pass-টির নাম mem2reg, আর SROA pass-ও একই কাজ করে। bags-এর C রূপ (long bags(long items), একই দেহ) PyPI-র ziglang 0.17.1-এর ভেতরের Clang 22.1.8 দিয়ে, SROA-র ঠিক পরের IR, লেখকের lab-এ সত্যিকারের run:
~/ssa $ python -m ziglang cc -O1 -g0 -fno-sanitize=undefined -fno-discard-value-names \
-S -emit-llvm --target=x86_64-linux-gnu bags.c -o bags.ll \
-mllvm -print-after=sroa -mllvm -filter-print-funcs=bags 2> sroa.txt
; *** IR Dump After SROAPass on bags ***
; Function Attrs: nounwind uwtable
define i64 @bags(i64 noundef %items) #0 {
entry:
br label %while.cond
while.cond: ; preds = %while.body, %entry
%n.0 = phi i64 [ 0, %entry ], [ %add, %while.body ]
%left.0 = phi i64 [ %items, %entry ], [ %sub, %while.body ]
%cmp = icmp sgt i64 %left.0, 0
br i1 %cmp, label %while.body, label %while.end
while.body: ; preds = %while.cond
%sub = sub nsw i64 %left.0, 6
%add = add nsw i64 %n.0, 1
br label %while.cond, !llvm.loop !10
while.end: ; preds = %while.cond
%cmp1 = icmp sgt i64 %n.0, 3
br i1 %cmp1, label %if.then, label %if.end
if.then: ; preds = %while.end
%sub2 = sub nsw i64 %n.0, 1
br label %if.end
if.end: ; preds = %if.then, %while.end
%n.1 = phi i64 [ %sub2, %if.then ], [ %n.0, %while.end ]
ret i64 %n.1
}
ছবি ৬৩.১-এর পাশে রাখুন: loop-এর মাথায় দুটি φ (%n.0, %left.0), if-এর পরে একটি (%n.1), ঠিক Haat-এর তিনটির জায়গায়। পার্থক্য: LLVM-এ φ-এর argument সরাসরি ধ্রুবক হতে পারে ([ 0, %entry ]), আর জোড়ার ক্রম [ মান, %block ]. পুরো pipeline-এর শেষের IR-এ (-O1 আর -O2 দুটিতেই, সত্যিকারের run) loop-টিই উধাও: Clang loop-এর ঘোরার সংখ্যা একটি সূত্রে (udiv দিয়ে ৬-এ ভাগ) হিসাব করেছে, আর শুধু একটি φ রয়ে গেছে। কীভাবে, তা loop optimization-এর বিষয় (পর্ব ৬৬)। আর sub nsw-এর nsw পতাকা Haat-এর অনুবাদে চলবে না কেন, তা পর্ব ৬৮-এ।
GCC-ও তার middle end-এর বেশির ভাগ কাজ SSA-তে করে: GIMPLE-এর SSA রূপ, যা “tree SSA” প্রকল্পের অংশ হিসেবে মোটামুটি GCC ৪.০ (২০০৫) থেকে মূল ধারায় এসেছে বলে সাধারণত বলা হয়। Dominator tree বানাতে LLVM-এর সাম্প্রতিক কোডে Cooper–Harvey–Kennedy নয়, Semi-NCA নামের একটি algorithm (Loukas Georgiadis-এর ২০০৫ সালের গবেষণাপত্রে বর্ণিত, Lengauer–Tarjan-এর একটি রূপ) ব্যবহার হয়, যা worst case-এ quadratic হলেও বাস্তবে দ্রুত বলে LLVM-এর নিজের source-এর মন্তব্যে লেখা আছে।
আরও গভীরে: Cytron et al.-এর পদ্ধতিতে আগে পুরো CFG, dominator আর frontier লাগে। Matthias Braun আর সহলেখকদের ২০১৩ সালের CC সম্মেলনের প্রবন্ধ “Simple and Efficient Construction of Static Single Assignment Form” দেখায় যে AST বা bytecode থেকে সরাসরি, dominator ছাড়াই, ব্যবহারের জায়গা থেকে পেছনে খুঁজে SSA বানানো যায়, আর reducible CFG-তে ফল minimal; libFirm compiler এটি ব্যবহার করে। আরেকটি ধারা φ-কে একেবারে বাদ দেয়: MLIR আর Swift-এর SIL-এ block-এর নিজস্ব argument থাকে, আর লাফ দেওয়ার সময় predecessor মান পাঠায়, যেন block একটি ছোট function. গণিতের দিক থেকে দুটি একই কথা (ভাবনার প্রশ্ন ২)।
পরীক্ষা ও ইন্টারভিউতে: এই প্রশ্নগুলো প্রায়ই আসে, বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায়। SSA-তে φ কেন লাগে? → দুই পথে একই variable-এর ভিন্ন সংজ্ঞা মেলে, আর একটি নামে একবারই লেখা যায়। Dominance frontier কী? → যে block-গুলোর কোনো predecessor-কে d dominate করে কিন্তু block-টিকে strictly নয়; d-এর সংজ্ঞার φ সেখানেই। CFG দিয়ে φ বসান আর নাম বদলান → iterated frontier, তারপর dominator tree-তে stack দিয়ে নাম; অনুশীলন ৩-এর মতো। SSA থেকে ফেরার সমস্যা? → critical edge (lost copy) আর সমান্তরাল copy-র চক্র (swap). Pruned আর minimal SSA-র পার্থক্য? → pruned শুধু live নামের φ রাখে।
১০ · AI-এর যুগে SSA
AI assistant SSA-র পাঠ্যবইয়ের সংজ্ঞা নির্ভুল বলতে পারে, আর ছোট উদাহরণে φ-ও বসায়। ভুলগুলো আসে algorithm-এর সূক্ষ্ম জায়গায়, আর সেগুলো প্রায়ই সাধারণ test পেরিয়ে যায় (অনুশীলন ২ দেখুন)।
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| প্রতিটি মিলনের block-এ সব variable-এর φ বসানো, বা শুধু সরাসরি frontier (iterated নয়) | φ-সংখ্যা গুনে iterated frontier-এর সঙ্গে মেলানো; minimal আর pruned আলাদা করে গোনা |
| নাম বদল block-এর নম্বরের ক্রমে, stack ছাড়া একটি “বর্তমান নাম”-এর map দিয়ে | check_ssa-এর মতো dominance পরীক্ষা; loop একবারও না ঘোরে এমন input (যেমন bags(0)) |
| φ-কে পরপর চলা নির্দেশ ধরে নেওয়া, বা SSA থেকে ফেরায় copy পরপর বসানো | অদলবদলের loop আর do-while আকারের loop দিয়ে আগে-পরে চালানো |
| Dominator আর post-dominator গুলিয়ে ফেলা; “a dom b মানে a থেকে b-তে পথ আছে” বলা | সংজ্ঞায় ফেরা: B0 থেকে b-এর প্রতিটি পথ a দিয়ে কি না; ছোট CFG-এ set-সমীকরণে মেলানো |
| বানানো clang flag বা LLVM pass-এর নাম, বা অন্য version-এর IR | নিজের যন্ত্রে সেই version-এ -emit-llvm আর -mllvm -print-after=… চালিয়ে দেখা |
AI-কে কাজে লাগাতে নিয়ম আর যাচাইয়ের পথ নিজেই বলে দিন:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১SSA-র ধারণা ১৯৮০-এর দশকের শেষে এল, কিন্তু GCC-র মতো বড় compiler-এ মূল ধারায় এল প্রায় পনেরো বছর পরে। কেন এত সময় লাগল, আর শেষে কেন সবাই এটি নিল?
SSA-র জন্ম IBM-এর গবেষণাগারে। ১৯৮৮ সালের POPL সম্মেলনে দুটি প্রবন্ধ, একটি Bowen Alpern, Mark Wegman আর Kenneth Zadeck-এর (দুটি variable-এর মান সবসময় সমান কি না, তা খোঁজা), আরেকটি Barry Rosen, Wegman আর Zadeck-এর (global value numbering আর একই হিসাব দুবার হওয়া খোঁজা), প্রথম “প্রতিটি নামে একবার লেখা” রূপ ব্যবহার করে বলে সাধারণত ধরা হয়। কিন্তু সেখানে φ বসানোর কার্যকর পদ্ধতি ছিল না। ১৯৯১ সালে Cytron, Ferrante, Rosen, Wegman আর Zadeck ACM TOPLAS-এ dominance frontier দিয়ে সেই পদ্ধতি দেন, যা আজও পাঠ্যবইয়ের মানদণ্ড।
তবু বড় শিল্প-compiler দ্রুত বদলায়নি। কারণগুলো প্রকৌশলের: পুরোনো compiler-এর শত শত optimization pass পুরোনো IR-এর ওপর লেখা, আর IR বদলানো মানে প্রায় সব নতুন করে লেখা। SSA-তে প্রতিটি বদলের পরে SSA-র শর্ত বজায় রাখতে হয়, যা শুরুতে কঠিন লাগে; আর memory, pointer আর array-কে SSA-তে কীভাবে আনা হবে, সেই প্রশ্নও খোলা ছিল। GCC-তে “tree SSA” প্রকল্প বহু বছর আলাদা শাখায় চলে, আর মোটামুটি GCC ৪.০-তে (২০০৫) মূল ধারায় আসে বলে সাধারণত বলা হয়। অন্যদিকে LLVM (Chris Lattner আর Vikram Adve, কাজ শুরু ২০০০ সালের দিকে) শুরু থেকেই SSA-ভিত্তিক, কারণ নতুন কাঠামো পুরোনো বোঝা ছাড়াই শুরু হয়েছিল।
শেষে সবাই কেন নিল? কারণ লাভগুলো জমতে থাকে। Sparse conditional constant propagation, global value numbering, dead code elimination আর loop-এর অনেক optimization SSA-তে ছোট আর দ্রুত হয়: প্রতিটি নামের জন্য একটি তথ্য, প্রতিটি বিন্দুর জন্য নয়। একবার IR SSA হলে নতুন optimization লেখা সস্তা হয়, আর সেই সুবিধাই পুরোনো খরচ ছাপিয়ে যায়।
মূল উপলব্ধি: একটি ভালো IR-এর মূল্য একটি optimization-এ দেখা যায় না, দেখা যায় পঞ্চাশটিতে; আর বড় সফটওয়্যারে ভালো ধারণার পথ খোলে প্রায়ই নতুন কাঠামো দিয়ে, পুরোনোটি সারিয়ে নয়।
প্র ০২বলা হয় “SSA আসলে functional programming”. একটি imperative IR-এর রূপ কীভাবে functional হতে পারে, আর MLIR-এর block argument এই কথার সঙ্গে কোথায় মেলে?
SSA-তে প্রতিটি নাম একবার মান পায় আর কখনো বদলায় না: ঠিক functional ভাষার let-এর মতো, Haat-এর let-এর মতোও। বাকি থাকে φ. Richard Kelsey ১৯৯৫ সালের একটি প্রবন্ধে দেখান যে SSA আর continuation-passing style (CPS)-এর মধ্যে একটি সরাসরি অনুবাদ আছে, আর Andrew Appel ১৯৯৮ সালে “SSA is Functional Programming” শিরোনামে একটি ছোট প্রবন্ধে কথাটি জনপ্রিয় করেন। মূল যুক্তি: প্রতিটি basic block-কে একটি ছোট local function ভাবুন। Block-এর φ-গুলো তার parameter; আর একটি block থেকে আরেকটিতে লাফ মানে সেই function-কে ডাকা, argument হিসেবে φ-এর সেই predecessor-এর মান দিয়ে। Loop তখন একটি recursive function, আর মাথার φ তার parameter: bags-এর loop হয় loop(left, n), যা নিজেকে loop(left - 6, n + 1) দিয়ে ডাকে। ডাকগুলো সব tail call, তাই কোনো stack বাড়ে না (পর্ব ৩২)।
এই দৃষ্টিভঙ্গি শুধু তত্ত্ব নয়। MLIR আর Swift-এর SIL φ নির্দেশ রাখে না; তাদের block-এর নিজস্ব argument থাকে, আর br ^bb1(%x, %y)-এর মতো লাফ argument পাঠায়। এতে কয়েকটি সুবিধা: φ-এর অদ্ভুত “block-এর শুরুতে সমান্তরাল” নিয়মটি আর আলাদা করে মনে রাখতে হয় না, function call-এর নিয়মই কাজ করে; আর “কোন predecessor থেকে কোন মান” তথ্যটি থাকে লাফের নির্দেশেই, তাই predecessor-এর তালিকা বদলালে φ-এর জোড়া মেলানোর ঝামেলা নেই। অন্যদিকে, functional ভাষার compiler (যেমন ML পরিবারের কিছু compiler) বহুদিন CPS-কেই IR হিসেবে ব্যবহার করেছে, যা SSA-র বোন।
এই মিল Haat-এর গল্পেও খাটে: পর্ব ৫৭-এর interpreter-এ প্রতিটি call নতুন environment পায়, আর পর্ব ৬২-এর run_ir-এর enter φ-গুলো ঠিক function-এর parameter বাঁধার মতো একসঙ্গে বাঁধে।
মূল উপলব্ধি: φ হলো block-কে function ভাবলে তার parameter; SSA, CPS আর block argument একই ধারণার তিন পোশাক, আর একটি বুঝলে বাকিগুলো সহজ।
প্র ০৩Dominator খোঁজার প্রায়-রৈখিক Lengauer–Tarjan algorithm ১৯৭৯ সালেই ছিল। তাহলে ২০০১ সালের দিকে একটি “ধীর” iterative পদ্ধতি কেন জনপ্রিয় হলো, আর বাস্তব compiler কোনটি ব্যবহার করে?
Dominator-এর ধারণা compiler-এর চেয়েও পুরোনো: ১৯৫৯ সালে Reese Prosser flow diagram বিশ্লেষণের একটি প্রবন্ধে এটি ব্যবহার করেন বলে সাধারণত উল্লেখ করা হয়, আর ১৯৭০-এর দশকে Frances Allen-এর control flow analysis-এর কাজে এটি optimization-এর কেন্দ্রে আসে। ১৯৭৯ সালে Thomas Lengauer আর Robert Tarjan ACM TOPLAS-এ একটি algorithm দেন, যার সময় প্রায় রৈখিক (inverse Ackermann ফাংশনের গুণিতক)। তাত্ত্বিকভাবে এটিই সেরা, কিন্তু কোডটি জটিল: semidominator, একটি বিশেষ forest আর path compression, আর ছোট ভুল ধরা কঠিন।
Cooper, Harvey আর Kennedy-র ২০০১ সালের দিকের প্রবন্ধের দাবি ছিল ব্যবহারিক: compiler-এর বাস্তব CFG ছোট আর প্রায় সবসময় reducible, আর RPO-তে iterative পদ্ধতি সেখানে দুই-তিন pass-এই থামে। তাদের মাপে এই সরল পদ্ধতি অনেক বাস্তব graph-এ Lengauer–Tarjan-এর চেয়ে দ্রুত চলেছে, কারণ ধ্রুবক খরচ কম আর memory-তে ডেটা সাজানো সহজ। এই পর্বের lab-এর মাপও সেই কথা বলে: ৯,০০১টি function-এর কোনোটিতেই দুটির বেশি pass লাগেনি। তবে worst case-এ (বিশেষ irreducible graph) iterative পদ্ধতি quadratic হতে পারে।
বাস্তবে কী? LLVM-এর সাম্প্রতিক source-এর GenericDomTreeConstruction.h বলে, পুরো dominator tree বানাতে সেখানে Semi-NCA ব্যবহার হয়, যা Loukas Georgiadis-এর ২০০৫ সালের গবেষণাপত্রে বর্ণিত Lengauer–Tarjan-এর একটি সরল রূপ; worst case-এ quadratic, কিন্তু মন্তব্য অনুযায়ী বাস্তবে সাধারণত দ্রুত। Tree বদলালে পুরোটা আবার না বানিয়ে ছোট ছোট update-এর আলাদা পদ্ধতিও আছে। অর্থাৎ শিল্পের পছন্দ তাত্ত্বিক সেরা নয়, মাপা সেরা।
মূল উপলব্ধি: asymptotic জটিলতা একটি মাপকাঠি মাত্র; compiler-এর ইনপুট কেমন, তা জেনে সরল algorithm বেছে নেওয়া প্রায়ই ভালো প্রকৌশল, যদি worst case-এর ঝুঁকিও জানা থাকে।
প্র ০৪SSA থেকে ফেরা এত সূক্ষ্ম কেন, আর আধুনিক register allocator কেন SSA-তে থেকেই কাজ করতে চায়?
শুরুর SSA-র পরে ফেরা সহজই ছিল: φ মুছে predecessor-এ copy, কারণ নাম বদলের ঠিক পরে প্রতিটি φ-এর argument আর ফল একই মূল variable-এর রূপ, একসঙ্গে বেঁচে থাকে না। সমস্যা শুরু হয় optimization-এর পরে। Copy propagation আর global value numbering একই variable-এর ভিন্ন রূপকে একসঙ্গে বাঁচিয়ে রাখে, তখন একটি φ-এর ফল আর তার argument একই সময়ে দরকারি হতে পারে। Briggs, Cooper, Harvey আর Simpson ১৯৯৮ সালের একটি প্রবন্ধে এর দুটি নমুনার নাম দেন: lost copy (critical edge-এ বসানো copy অন্য পথেও চলে) আর swap (একই block-এর φ-গুলো একে অপরকে পড়ে)। এই পর্বের lab-এ দুটিই সত্যিকারের run-এ ভুল আউটপুট দিয়েছে: ৩-এর জায়গায় ২ নয়, ২-এর জায়গায় ৩, আর ২, ১-এর জায়গায় ২, ২।
পরের গবেষণা আরও এগোয়। Vugranam Sreedhar ও সহলেখকেরা ১৯৯৯ সালে copy কম রেখে ফেরার পদ্ধতি দেন; Benoit Boissinot ও সহলেখকেরা ২০০৯ সালের দিকে সঠিকতা, কোডের মান আর গতি একসঙ্গে বিচার করে পদ্ধতিটি নতুন করে সাজান বলে উল্লেখ পাওয়া যায়। আরেকটি আবিষ্কার পুরো ছবি বদলায়: strict SSA program-এর interference graph সবসময় chordal, যা ২০০৫–২০০৬ সালের দিকে কয়েকটি দল (যেমন Sebastian Hack ও সহকর্মীরা, আর স্বাধীনভাবে আরও কয়েকজন) দেখান। Chordal graph-এ ন্যূনতম রং বহুপদী সময়ে করা যায়, অথচ সাধারণ graph coloring NP-hard (পর্ব ৭০)।
তাই কিছু আধুনিক allocator আগে SSA-তে থেকেই register বেছে নেয়, আর φ ভাঙে register বরাদ্দের পরে, যখন copy-গুলো register-এর মধ্যে অদলবদল মাত্র। এই অংশ ৮-এর sequentialize ঠিক সেই অদলবদলের সমস্যাই সমাধান করে: চক্রে একটি বাড়তি জায়গা লাগে, অথবা যন্ত্রে swap নির্দেশ থাকলে সেটি।
মূল উপলব্ধি: SSA-তে ঢোকা সহজ, বেরোনো কঠিন, কারণ optimization মাঝখানে নামগুলোর সম্পর্ক বদলে দেয়; ফেরার পদ্ধতি তাই optimization-এর পরের অবস্থা ধরে লিখতে হয়, শুরুর অবস্থা ধরে নয়।
প্র ০৫Haat-এর @x global, C-এর pointer আর closure-এ ধরা variable SSA-তে আসে না কেন? Memory-কে SSA-তে আনার কী উপায় আছে?
SSA-র নাম বদল একটি অনুমানের ওপর দাঁড়িয়ে: কোনো নামের সব লেখা আর পড়া compiler নির্দেশ দেখেই জানে। Haat-এর local variable-এ এটি সত্য। কিন্তু @x global-এ লেখে অন্য function, call-এর ভেতরে; bump() ডাকলে @g বদলায়, অথচ caller-এর নির্দেশে তার কোনো চিহ্ন নেই। তাই haat_ssa.py @-ওয়ালা নাম ছোঁয় না; সেগুলো memory-তে থাকে, আর পর্ব ৬২-এর সিদ্ধান্ত ১৮-এর পরীক্ষাও তাই অক্ষত থাকে। C-তে একই সমস্যা pointer দিয়ে: p = &x হলে *p = 5 x বদলায়, নামে কোনো চিহ্ন ছাড়াই। এজন্য Clang সব local আগে alloca-তে রাখে, আর mem2reg বা SROA শুধু সেই alloca-গুলোকে register-এ তোলে, যাদের ঠিকানা বাইরে যায় না। আর Haat-এর closure reference দিয়ে variable ধরে (পর্ব ১৭, বাস্তবায়ন পর্ব ৫৭): ধরা variable একটি shared environment-এ থাকে, যা অন্য function বদলাতে পারে, তাই Haat IR v1 closure-কে বাইরেই রেখেছে।
Memory-কে পুরোপুরি বাদ দেওয়া যায় না, তাই তার জন্যও SSA-ধাঁচের রূপ এসেছে। একটি ধারণা: পুরো memory-কে একটি variable ধরুন, প্রতিটি store তার নতুন “version” বানায়, আর মিলনে memory-র φ. LLVM-এ MemorySSA নামে এমন একটি বিশ্লেষণ আছে, যা load আর store-কে এভাবে যুক্ত করে। Array-এর জন্য Kathleen Knobe আর Vivek Sarkar-এর ১৯৯৮ সালের দিকের “Array SSA” প্রস্তাব উল্লেখযোগ্য। এগুলো সবই অনুমাননির্ভর: দুটি pointer একই জায়গা দেখায় কি না (alias analysis), তা সাধারণভাবে undecidable (গণনার তত্ত্ব, পর্ব ৭৮), তাই compiler সাবধানী উত্তর নেয়।
মূল উপলব্ধি: SSA-র শক্তি আসে “সব লেখা চোখে দেখা যায়” অনুমান থেকে; যেখানে এই অনুমান ভাঙে (global, pointer, closure), সেখানে compiler হয় memory-তে রাখে, নয় আলাদা, আরও সাবধানী বিশ্লেষণ চালায়।
অনুশীলন
প্রথমে নিজে হিসাব করুন বা লিখুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর সত্যিকারের run দিয়ে যাচাই করা।
-
নকশা ও বাস্তবায়ন — entry block যোগ করা:
to_ssaerror দেয় যদি B0-তেই φ লাগে, যা ঘটে যখন B0 নিজে একটি loop-এর মাথা আর loop-এর ভেতরে একটি parameter-এ লেখা হয়। Haat-এ parameter immutable (reference-এর সিদ্ধান্ত ১৯), কিন্তু হাতে লেখা বা অন্য ভাষা থেকে আসা IR-এ এমন হতে পারে। একটিadd_entry(fn)লিখুন, যা B0-এর কোনো predecessor থাকলে পুরোনো B0-কে নতুন নাম দেয় আর একটি খালি নতুন B0 বসায়, যাতে নিয়ম “B0 = entry” টিকে থাকে। নিচের IR-এ পরীক্ষা করুন (parse_irদিয়ে পড়া যায়;<main>down(3)ডেকে ফল ছাপে):fn down(n): B0: t1 = const 0 t2 = n > t1 branch t2 B1 B2 B1: print n t3 = const 1 n = n - t3 jump B0 B2: return ndef add_entry(fn): # B0-তে কেউ লাফালে: পুরোনো B0 নতুন নামে, নতুন খালি B0 if not preds(fn)["B0"]: return fn old = f"B{max(int(b[1:]) for b in fn.blocks) + 1}" ren = lambda t: old if t == "B0" else t blocks = {"B0": [Ins("jump", targets=[old])]} for b, body in fn.blocks.items(): for i in body: i.targets = [ren(t) for t in i.targets] blocks[ren(b)] = body fn.blocks = blocks return fnলেখকের lab-এ সত্যিকারের run:
to_ssa(down)থামেValueError: B0-তে φ লাগবে: entry-র আগে একটি নতুন block দিনদিয়ে।add_entry-এর পরে পুরোনো B0 হয় B3, আর SSA রূপ:fn down(n): B0: jump B3 B3: n#1 = phi(B0: n, B1: n#2) t1 = const 0 t2 = n#1 > t1 branch t2 B1 B2 B1: print n#1 t3 = const 1 n#2 = n#1 - t3 jump B3 B2: return n#1check_ssaকোনো আপত্তি দেয় না, আর মূল, SSA আর SSA থেকে ফেরা তিন রূপই ছাপে3,2,1,0. φ-এর B0-জোড়ায় parameter-এর নিজের নামn, কারণ নাম বদলের শুরুতে parameter-এর stack-এ তার নাম থাকে। এই নতুন entry block-টিই পর্ব ৬৬-এ loop-এর preheader-এর ধারণার কাছাকাছি: loop-এর আগে একটি জায়গা, যেখানে loop থেকে তুলে আনা কোড রাখা যায়। -
ভুল খুঁজুন: একজন সহকর্মী নাম বদল “সরল” করলেন: dominator tree আর stack বাদ; block-গুলো নম্বরের ক্রমে (B0, B1, …) ঘোরেন, আর প্রতিটি নামের একটি “বর্তমান নাম” রাখেন, যা নতুন সংজ্ঞায় বদলায় আর কখনো ফেরে না।
bags-এ (bags(20),bags(6)) এটি কী দেয়, আর কোথায় ভুল? ৩,০০০টি এলোমেলো program কী বলবে?নম্বরের ক্রমে B2 আগে আসে, তাই B2-এর
n#3 = n#2 + t4-এর পরে “বর্তমান” n হয়ে থাকেn#3. B3 তখন পড়েt6 = n#3 > t5, B4 পড়েn#4 = n#3 - t7, আর B5-এর φ পায়(B3: n#3); ঠিক হতোn#2. লেখকের lab-এ সত্যিকারের run:bags(20)আরbags(6)তবু সঠিক,3আর1, কারণ loop অন্তত একবার ঘোরে, আর loop শেষেn#3-এর শেষ মানn#2-এর সমান। কিন্তুbags(0)বাbags(-5)-এ loop একবারও ঘোরে না,n#3কখনো মান পায় না, আরrun_irথামেKeyError: 'n#3'দিয়ে; reference ছাপে0. ৩,০০০টি এলোমেলো program-এ: ২,৬৭৫টিতে আউটপুট হুবহু ঠিক, ৩২৫টিতেKeyError, চুপচাপ ভুল আউটপুট শূন্য।check_ssaকিন্তু ১,৫৪৮টি program-এ আপত্তি তোলে,bags-এ তিনটি: “B3: n#3-এর সংজ্ঞা ব্যবহারকে dominate করে না” আর একই কথা B4 আর B5-এর জন্য। শিক্ষা: আউটপুট মেলা যথেষ্ট নয়; গঠনের শর্তও আলাদা করে যাচাই করুন, আর loop শূন্যবার ঘোরা input রাখুন। -
হিসাব ও trace: পর্ব ৬২-এর
stock_days-এর CFG নিচে। (ক) idom আর dominance frontier বের করুন; (খ) minimal আর pruned SSA-তে কোন নামের φ কোথায়; (গ) SSA রূপ লিখুন; (ঘ) SSA থেকে ফেরায় কোন edge ভাগ হবে?fn stock_days(stock, daily): B0: days = const 0 left = stock jump B1 B1: t1 = const 0 t2 = left > t1 branch t2 B2 B3 B2: t3 = const 30 t2 = days < t3 jump B3 B3: branch t2 B4 B5 B4: left = left - daily t4 = const 1 days = days + t4 jump B1 B5: return days(ক) RPO: B0 B1 B2 B3 B5 B4. idom: B1 → B0, B2 → B1, B3 → B1, B4 → B3, B5 → B3. DF(B1) = {B1}, DF(B2) = {B3}, DF(B3) = {B1}, DF(B4) = {B1}, বাকিগুলো ফাঁকা (অংশ ৪-এর JavaScript ব্লকের আউটপুটের মতো)। (খ)
days,left: সংজ্ঞা B0, B4 → DF+ = {B1}, দুটিই সেখানে live, তাই B1-এ φ.t2: সংজ্ঞা B1, B2 → DF+ = {B3, B1}। Minimal SSA দুই জায়গাতেই φ বসাত; pruned শুধু B3-এ, কারণ B1-এর শুরুতেt2live নয় (B1 নিজেই আগে লেখে), আর B0 থেকে আসা পথেt2-এর কোনো মানই নেই। (গ)haat_ssa.py-র সত্যিকারের আউটপুট:fn stock_days(stock, daily): B0: days#1 = const 0 left#1 = stock jump B1 B1: days#2 = phi(B0: days#1, B4: days#3) left#2 = phi(B0: left#1, B4: left#3) t1 = const 0 t2#1 = left#2 > t1 branch t2#1 B2 B3 B2: t3 = const 30 t2#2 = days#2 < t3 jump B3 B3: t2#3 = phi(B1: t2#1, B2: t2#2) branch t2#3 B4 B5 B4: left#3 = left#2 - daily t4 = const 1 days#3 = days#2 + t4 jump B1 B5: return days#2(ঘ) B1 → B3: B1 branch-এ শেষ (দুই successor) আর B3-এর দুই predecessor, তাই critical; ফেরার সময় নতুন B6 আসে, তাতে
t2#3 = t2#1, আর B2-এর শেষেt2#3 = t2#2. B0 আর B4-এর শেষে loop-এর φ-এর copy. Reference আর তিন রূপই ছাপে7আর30. -
প্রমাণ — dominator tree সত্যিই একটি গাছ: প্রমাণ করুন: (ক) dom একটি partial order; (খ) b ≠ B0 হলে b-এর strict dominator-রা একটি সারিতে সাজানো যায়, অর্থাৎ যেকোনো দুটি a, c-এর জন্য a dom c অথবা c dom a; তাই idom(b) একটিই, আর idom-এর edge-গুলো B0-মূলের একটি গাছ। ধরে নিন সব block B0 থেকে পৌঁছানো যায়।
- Reflexive: b-তে যাওয়ার প্রতিটি পথ b-তে শেষ, তাই b দিয়ে যায়: b dom b.
- Transitive: a dom b আর b dom c. c-তে যাওয়ার যেকোনো পথ b দিয়ে যায়; সেই পথের B0 থেকে b পর্যন্ত অংশটি b-তে যাওয়ার একটি পথ, তাই a দিয়ে যায়। অতএব a dom c.
- Antisymmetric: a dom b, b dom a, আর a ≠ b ধরুন। B0 থেকে b-তে একটি সরল পথ নিন (কোনো block দুবার নয়; পৌঁছানো যায় বলে আছে)। এতে a আছে; a-এর আগের অংশটি a-তে যাওয়ার একটি পথ, তাই সেখানে b আছে, অর্থাৎ b পথে দুবার: a-এর আগে আর শেষে। সরল পথে তা অসম্ভব। তাই a = b. (ক) শেষ।
- সারি: a আর c দুটিই b-কে strictly dominate করে। B0 থেকে b-তে একটি সরল পথ নিন; দুটিই এতে আছে। ধরুন a আগে আসে। দাবি: a dom c. না হলে B0 থেকে c-তে a-বিহীন একটি পথ আছে; তার সঙ্গে আমাদের পথের c থেকে b পর্যন্ত অংশ জুড়লে (যা a-এর পরে, তাই a-বিহীন) B0 থেকে b-তে a-বিহীন পথ, যা a dom b-এর বিরোধী।
- গাছ: strict dominator-রা একটি সারি, আর B0 সবার আগে; সারির শেষেরটি, অর্থাৎ b-এর সবচেয়ে কাছেরটি, idom(b), আর তা একটিই। প্রতিটি b ≠ B0-এর ঠিক একটি বাবা, আর idom(b)-এর strict dominator b-এর strict dominator-দের উপসেট, তাই idom-এর শিকল চক্র ছাড়াই B0-তে পৌঁছায়: B0-মূলের গাছ। ∎
পরীক্ষাও করা হয়েছে: লেখকের lab-এ ৯,০০১টি function-এর প্রতিটি block-এ, idom-এর শিকল থেকে পাওয়া dominator-এর set সমীকরণ Dom(b) = {b} ∪ ⋂ Dom(p) থেকে গোনা set-এর সমান।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি function-এর CFG থেকে SSA হয়ে আবার copy-ওয়ালা IR পর্যন্ত ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- B0 থেকে DFS করে reverse postorder
- Iterative পদ্ধতিতে প্রতিটি block-এর immediate dominator
- idom থেকে প্রতিটি block-এর dominance frontier
- Liveness আর iterated frontier দিয়ে φ বসানো
- Dominator tree ঘুরে stack দিয়ে নাম বদল
- Critical edge ভাগ করে φ-এর জায়গায় সমান্তরাল copy
Block B3-এর শুরুতে x3 = phi(B1: x1, B2: x2). চলার সময় B2 থেকে লাফ দিয়ে B3-এ ঢোকা হলো, আর তখন x1 = 5, x2 = 9. x3-এর মান কত?
- 5
- 9
- 14
- অনির্দিষ্ট
একটি CFG-তে edge: B0→B1, B0→B2, B1→B3, B2→B3 (if/else আর মিলন)। idom(B3) কোনটি?
- B0
- B1
- B2
- B3 নিজে
একই CFG-তে (B0→B1, B0→B2, B1→B3, B2→B3) x লেখা হয় শুধু B1-এ আর B0-তে। x-এর φ কোথায় বসবে?
- B1-এ
- কোথাও না
- B3-এ
- B0-তে
Minimal SSA আর pruned SSA-র পার্থক্য কোনটি?
- Pruned SSA-তে একটি নাম একাধিকবার লেখা যায়
- Minimal SSA-তে φ সবসময় কম
- Pruned SSA dominator ছাড়াই বানানো হয়
- Pruned SSA শুধু সেই φ রাখে, যার নাম সেখানে live
SSA থেকে ফেরার সময় একটি φ-এর copy predecessor P-এর শেষে বসানো হলো, যেখানে P-এর দুটি successor আর লক্ষ্য block-এর দুটি predecessor. কোন সমস্যার ঝুঁকি?
- Swap problem
- Lost-copy problem
- Dominator tree ভেঙে যাওয়া
- φ-এর সংখ্যা বেড়ে যাওয়া
Clang C-এর local variable-কে LLVM IR-এর SSA রূপে আনে কীভাবে?
- Front end সরাসরি প্রতিটি variable-এর φ লেখে
- LLVM IR SSA নয়, তাই কিছু লাগে না
- আগে memory-তে (alloca, load, store), পরে একটি pass তুলে φ বসায়
- Linker φ বসায়
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- SSA: প্রতিটি নামের লেখায় একটিই সংজ্ঞা; def-use সরাসরি, বিশ্লেষণ sparse, বদল নিরাপদ।
- φ: মিলনের block-এর শুরুতে, আগত edge দেখে মান বাছে; সব φ একসঙ্গে, সমান্তরালভাবে।
- Dominator: B0 থেকে প্রতিটি পথে থাকা block; idom-গুলো একটি গাছ; Cooper–Harvey–Kennedy RPO-তে দুই আঙুলের meet দিয়ে, Haat-এ বড়জোর ২টি pass.
- তৈরি: সংজ্ঞার iterated frontier-এ φ, liveness দিয়ে ছাঁটা (pruned); তারপর dominator tree-তে stack দিয়ে নাম বদল।
- ফেরা: predecessor-এ copy, critical edge ভাগ করে (lost copy), আর সমান্তরাল copy-র নিরাপদ ক্রম, চক্রে একটি temp (swap).
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৬৪ · Dataflow analysis — liveness, reaching definition আর fixpointপরবর্তী পর্বSSA-র পাশে বিশ্লেষণের সাধারণ কাঠামো।
- পর্ব ৬২ · Intermediate representationআগের পর্বHaat IR, CFG আর এই পর্বের ব্যবহার করা IR interpreter.
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ৫৪ · অন্য semantic checkএই কোর্সেLiveness-ধাঁচের প্রথম বিশ্লেষণ: অব্যবহৃত variable আর unreachable code.
- DFS — গ্রাফের গভীরে আগেপাশের ট্র্যাকReverse postorder আর back edge-এর ভিত্তি।
- Partial order আর latticeপাশের ট্র্যাকDominance-এর partial order আর পরের পর্বের lattice-এর গণিত।