এই পর্বে যা শিখবেন
- Maximal munch-এ token ভাগ, Pratt parser-এর binding-power সিদ্ধান্ত আর AST-এর S-expression হাতে লেখা
- কোনো বিন্দুতে কোন নাম কোন ঘোষণায় যায়, আর কোন ধাপ কোন error আগে দেয়, তা বলা
- একটি function-এর bytecode পড়ে VM stack ধাপে ধাপে লেখা আর নির্দেশ গোনা
- Three-address code, quadruple, triple, leader, basic block, CFG, dominator, dominance frontier আর φ বসানো
- Liveness আর reaching definitions-এর ছক, constant folding, CSE, DCE, LICM আর strength reduction হাতে করা
- Interference graph রং করা, spill বাছা, RISC-V frame-এর offset আর call sequence লেখা, mark-sweep আর Cheney trace করা
১ · পাতার নিয়ম, ভাগের মানচিত্র আর উত্তরের পাঁচ ধাপ
রেলস্টেশনের পার্সেল অফিসে একটি বাক্স কয়েকটি টেবিল ঘুরে যায়: ওজন, লেবেল, গন্তব্য, তারপর কোন বগিতে যাবে। প্রতিটি টেবিলের নিজস্ব খাতা আছে, আর ভুল হলে কোন টেবিলে হলো, খাতা দেখেই ধরা যায়। Compiler-এর সমস্যাও এভাবে পড়ুন: প্রশ্নটি pipeline-এর কোন ধাপের, সেই ধাপের “খাতা” কী (token-এর তালিকা, গাছ, ছক, graph, frame), আর সেটি কীভাবে মেলাবেন। Pipeline-এর ধাপগুলো শেখানো হয়েছে পর্ব ০৫-এ; এখানে প্রতিটি ধাপের খাতা লেখার অনুশীলন।
- ধাপ চেনা: token? গাছ? IR? graph? frame? ভুল ধাপের নিয়ম খাটালে পুরো উত্তর ভুল হয়।
- ইনপুট নকল: program বা IR হুবহু খাতায় তুলুন, সারি বা block-এর নম্বরসহ। পরের সব উত্তর এই নম্বর ধরে লেখা হয় (B2.5 মানে block B2-এর পঞ্চম অবস্থানের নির্দেশ, গোনা শূন্য থেকে)।
- নিয়ম ধরে হিসাব: binding power, leader-এর তিন নিয়ম, dominance frontier, transfer function, colouring-এর simplify/select: প্রতিটি লাইনের পাশে নিয়মের নাম।
- ছক বা graph: liveness-এর ছক, interference graph, frame-এর offset: পরীক্ষক এগুলোতেই নম্বর দেন।
- মেলানো: Haat হলে reference-এর
tokens,ast,check,dis,run; IR হলে পাতার Python block. আগের আর পরের program একই আউটপুট দিলে তবেই রূপান্তর গ্রহণযোগ্য।
ছবি ৮২.১ — Pipeline-এর কোন ধাপে কোন ধরনের প্রশ্ন
বাঁয়ে ধাপ, ডানে সেই ধাপের খাতা আর এই পাতার অংশ
| অংশ | প্রশ্নের ধরন | মূল পর্ব | প্রশ্ন |
|---|---|---|---|
| ২ | Token, lexer-এর error, Pratt trace, S-expression, FIRST আর lookahead | ৪৬–৪৯ | ২.১–২.৫ |
| ৩ | নাম-সমাধান, slot, কোন ধাপের error আগে | ৫১, ৫২ | ৩.১–৩.৩ |
| ৪ | Bytecode লেখা, VM stack, closure-এর opcode | ৫৮, ৫৯ | ৪.১–৪.৪ |
| ৫ | Three-address code, quadruple, triple, ||-এর lowering, CFG | ৬২ | ৫.১–৫.৪ |
| ৬ | Dominator, frontier, φ বসানো, renaming, SSA থেকে ফেরা | ৬৩ | ৬.১–৬.৪ |
| ৭ | Liveness, reaching definitions, folding, CSE, DCE | ৬৪, ৬৫ | ৭.১–৭.৪ |
| ৮ | Back edge, natural loop, LICM, strength reduction | ৬৬ | ৮.১–৮.৩ |
| ৯ | Interference graph, রং, spill, frame, call sequence, GC | ৭০, ৭১, ৭৫ | ৯.১–৯.৫ |
| ১০ | মিশ্র: অনুবাদ করুন, যাচাই করুন | ৫৮–৭১ | ১০.১–১০.২ |
Typing derivation আর semantics-এর প্রমাণের অনুশীলন আছে পর্ব ৮৫-এ, আর তুলনামূলক লিখিত প্রশ্ন পর্ব ৮৪-এ; এখানে সেগুলো আবার নেই। প্রতিটি প্রশ্নে যে program বা IR লাগে, প্রশ্নের ভেতরেই দেওয়া।
২ · Front end — token, Pratt trace আর S-expression
ঝালিয়ে নিন: পর্ব ৪৬ · হাতে লেখা lexer (৩৭টি token kind, maximal munch: দুই অক্ষরের operator আগে), পর্ব ৪৮ · Pratt parsing (binding power: || ১০, && ২০, == != ৩০, < <= > >= ৪০, + - ৫০, * / % ৬০, prefix ৭০, call ৮০; rbp = lbp + ১), পর্ব ৪৯ · AST নকশা (S-expression-এর রূপ)।
২.১Haat-এর এই লাইনটি (লাইন ৩) token-এ ভাঙুন, অবস্থান line:col-সহ: while q>=10&&!done{q=q--2-5;}. কয়টি token? -- কেন একটি token নয়? q = 25 থেকে শুরু হলে loop শেষে q কত? — ৫ নম্বর (সহজ)
Lexer প্রতিবার সবচেয়ে লম্বা মেলানো অংশ নেয় (maximal munch), কিন্তু শুধু ভাষায় থাকা operator থেকে। >= আর && দুই অক্ষরের operator, তাই একটি করে token; Haat-এ -- নেই, তাই দুটি আলাদা MINUS. মোট ১৮টি token. Reference-এর tokens-এর সত্যিকারের run (প্রাসঙ্গিক অংশ):
3:1 WHILE while 3:19 LBRACE {
3:7 IDENT q 3:20 IDENT q
3:8 GT_EQ >= 3:21 EQ =
3:10 INT 10 3:22 IDENT q
3:12 AND_AND && 3:23 MINUS -
3:14 BANG ! 3:24 MINUS -
3:15 IDENT done 3:25 INT 2
3:26 MINUS -
3:27 INT 5
3:28 SEMI ;
3:29 RBRACE }
Parser দ্বিতীয় --কে prefix ধরে: ast দেয় (set q (- (- q (- 2)) 5)), অর্থাৎ q = q + 2 − 5 = q − 3. ২৫ থেকে ২২, ১৯, ১৬, ১৩, ১০, ৭; ৭ < ১০ হলে থামে। Reference-এর run: 7. নম্বর-ভাগ: token-গুলো (২), ---এর কারণ (১), গাছ (১), ফল (১)। যেখানে নম্বর কাটে: q---কে C-র decrement ভাবা; Haat-এ তা নেই।
২.২প্রতিটির lexer বা parser কী বলে, অবস্থানসহ? (ক) let c = a-->b; (লাইন ৫) (খ) let x = 3 & 4; (গ) let s = "ab\tc"; (ঘ) let n = 99999999999999999999; — ৫ নম্বর (সহজ)
- (ক) Maximal munch:
a, তারপর-(কারণ--নেই), তারপর->একটিARROW, তারপরb. Lexer খুশি, parser নয়:--এর ডান পাশে expression চাই, এসেছে->. সত্যিকারের run:5:11: error: expected expression. - (খ) একা
&কোনো token নয় (README-এর spec decision ২):1:11: error: unexpected character '&'. - (গ) Haat-এ শুধু
\" \\ \nescape:1:12: error: unknown escape sequence '\t'. - (ঘ) Literal-এর সীমা 9223372036854775807 (decision ৩):
1:9: error: integer literal too large.
যেখানে নম্বর কাটে: (ক)-কে lexer error বলা। Token-এ ভাঙা সফল; ভুলটি ব্যাকরণের।
২.৩Pratt parser-এ a - b - c * 2 >= x && ok parse করুন: প্রতিটি infix operator-এ lbp আর min_bp তুলনা লিখুন, শেষে S-expression দিন। — ১০ নম্বর (মাঝারি)
নিয়ম: operator-এর lbp ≥ min_bp হলে সে বাঁ পাশের গাছ নিজের বাঁ সন্তান করে, আর ডান পাশ পড়ে min_bp = lbp + ১ দিয়ে; নইলে থেমে বাঁ গাছ ফেরত দেয়। ৯টি সিদ্ধান্ত (নিচের stepper আর Python block একই ক্রম দেখায়):
- : 50 ≥ 0 বাঁধে (ডান পাশ min_bp 51)
- : 50 < 51 থামে → (- a b)
- : 50 ≥ 0 বাঁধে
* : 60 ≥ 51 বাঁধে
>= : 40 < 61 থামে → (* c 2)
>= : 40 < 51 থামে → (- (- a b) (* c 2))
>= : 40 ≥ 0 বাঁধে
&& : 20 < 41 থামে
&& : 20 ≥ 0 বাঁধে → গোড়া
ফল (&& (>= (- (- a b) (* c 2)) x) ok), reference-এর ast-এর সঙ্গে হুবহু। a = 9, b = 4, c = 2, x = 1, ok = true হলে 9 − 4 − 4 = 1 ≥ 1, তাই true (সত্যিকারের run). নম্বর-ভাগ: প্রথম --এর বাঁ-সংযোগ (৩), *-এর আগে বাঁধা (২), তুলনা আর && (৩), S-expression (২)। যেখানে নম্বর কাটে: rbp = lbp ধরা, তখন a - b - c ডান-সংযোগী হয়ে (- a (- b c)).
| পড়া token | |
| সিদ্ধান্ত | |
| এ পর্যন্ত গাছ |
- প্রথম বিয়োগ।
aprefix অবস্থানে পড়া হলো।--এর lbp ৫০ ≥ ০, তাই সেa-কে বাঁ সন্তান করে; ডান পাশ পড়া শুরু হয় min_bp ৫১ দিয়ে। - বাঁ-সংযোগ আর গুণ। ডান পাশে
b-এর পরে আবার-: ৫০ < ৫১, তাই থামে, গাছ(- a b). বাইরের স্তরে একই-৫০ ≥ ০, বাঁধে। এবার ডানেc-এর পরে*: ৬০ ≥ ৫১, তাই গুণ আগে বাঁধে। - তুলনা।
2-এর পরে>=: গুণের ভেতরে ৪০ < ৬১, বিয়োগের ভেতরে ৪০ < ৫১, দুই স্তরই থামে। সবচেয়ে বাইরের স্তরে ৪০ ≥ ০, বাঁধে; ডান পাশ min_bp ৪১. &&.x-এর পরে&&: ২০ < ৪১, তুলনার ডান পাশ শেষ। বাইরে ২০ ≥ ০, বাঁধে।- শেষ।
okপড়া হলো, আর কোনো operator নেই। গোড়া&&: সবচেয়ে কম binding power-এর operator-ই গাছের মাথায় যায়। মোট ৯টি তুলনা।
২.৪S-expression লিখুন, বা error বলুন: (ক) -a * b + c % 3 == x || !ok (খ) a < b == c < d (গ) a < b < c (লাইন ৪, প্রথম < কলাম ১১-এ, দ্বিতীয়টি ১৩-এ)। — ৫ নম্বর (মাঝারি)
- (ক) Prefix
--এর rbp ৭০, তাই সে শুধুaনেয়:(|| (== (+ (* (- a) b) (% c 3)) x) (! ok)). - (খ) আলাদা স্তরের তুলনা মেশানো চলে (decision ১০):
(== (< a b) (< c d)); a, b, c, d = 1, 2, 3, 4 হলেtrue. - (গ) একই স্তরের তুলনা পরপর:
4:13: error: comparison operators cannot be chained, দ্বিতীয় operator-এ।
তিনটিই reference-এর ast/check-এর সত্যিকারের run. যেখানে নম্বর কাটে: (ক)-তে (- (* a b)) লেখা; (গ)-তে C-র মতো (a < b) < c ধরা।
২.৫Haat-এর statement-এর FIRST set-এ FN আর IDENT দুবার আসে কেন? এক token দেখে (LL(1)) recursive descent parser কোন statement বাছতে পারে না, আর হাতে লেখা parser কী করে? f(1) = 2; (লাইন ৩) কী বার্তা দেয়? — ৫ নম্বর (মাঝারি)
FIRST set-এর তত্ত্ব আর LL(1) ছক গণনার তত্ত্ব · পর্ব ৩৮-এ; এখানে শুধু প্রয়োগ। FIRST(statement)-এ আছে let var fn if while return print { আর FIRST(expression)-এর সব: IDENT INT STRING true false ( - ! fn.
fn: function ঘোষণাfn name(…), আবার anonymous function-এর expression statementfn(…) …;. Reference parser একটি token বেশি দেখে:fn-এর পরেIDENTহলে ঘোষণা (দুই token-এর lookahead).IDENT: assignmentx = e;আর expression statementx + 1;. Parser আগে পুরো expression পড়ে, তারপর=দেখলে বাঁ পাশ একা নাম কি না যাচাই করে (decision ৯)। তাইf(1) = 2;দেয়3:6: error: invalid assignment target,=-এর অবস্থানে (সত্যিকারের run).
FOLLOW set-এর একটি কাজের তথ্য: expression-এর পরে ঠিক এই পাঁচটি token আসতে পারে: ; ) , { = (statement শেষ, call-এর argument বা বন্ধনী, if/while-এর শর্ত, assignment); reference-এর parser.py-তে যেখানে যেখানে expression পড়া হয়, তার পরের token মিলিয়ে দেখা। যেখানে নম্বর কাটে: “Haat LL(1) নয়, তাই recursive descent চলে না” লেখা; সামান্য বেশি lookahead বা পরে-যাচাই দিয়েই চলে।
import re # Pratt parser: binding power README-র ছক থেকে (পর্ব ৪৮)
LBP = {"||": 10, "&&": 20, "==": 30, "!=": 30, "<": 40, "<=": 40, ">": 40, ">=": 40,
"+": 50, "-": 50, "*": 60, "/": 60, "%": 60}
def lex(s): # maximal munch: দুই অক্ষরের operator আগে
return re.findall(r"[A-Za-z_]\w*|\d+|&&|\|\||==|!=|<=|>=|[-+*/%<>!()]", s) + ["$"]
def parse(s, trace):
toks, i = lex(s), 0
def expr(min_bp, depth):
nonlocal i
t = toks[i]; i += 1
if t in "-!": left = f"({t} {expr(70, depth + 1)})" # prefix: rbp 70
elif t == "(": left = expr(0, depth + 1); i += 1 # ")" বাদ
else: left = t
last = None
while toks[i] in LBP:
op = toks[i]; lbp = LBP[op]
ok = lbp >= min_bp
trace.append(f"{' ' * depth}{op}: lbp {lbp} {'≥' if ok else '<'} min_bp {min_bp} → {'বাঁধে' if ok else 'থামে'}")
if not ok: break
if last == lbp and lbp in (30, 40): raise SyntaxError("comparison operators cannot be chained")
i += 1; left = f"({op} {left} {expr(lbp + 1, depth + 1)})"; last = lbp
return left
return expr(0, 0)
for s in ["a - b - c * 2 >= x && ok", "-a * b + c % 3 == x || !ok", "a < b < c"]:
tr = []
try: print(s, "⇒", parse(s, tr))
except SyntaxError as e: print(s, "⇒ error:", e)
print("\n".join(tr) if s.startswith("a -") else f" ({len(tr)}টি সিদ্ধান্ত)")আসল আউটপুট (লেখকের যন্ত্রে CPython 3.14.4-এ, ব্রাউজারের Pyodide-এ একই):
a - b - c * 2 >= x && ok ⇒ (&& (>= (- (- a b) (* c 2)) x) ok)
-: lbp 50 ≥ min_bp 0 → বাঁধে
-: lbp 50 < min_bp 51 → থামে
-: lbp 50 ≥ min_bp 0 → বাঁধে
*: lbp 60 ≥ min_bp 51 → বাঁধে
>=: lbp 40 < min_bp 61 → থামে
>=: lbp 40 < min_bp 51 → থামে
>=: lbp 40 ≥ min_bp 0 → বাঁধে
&&: lbp 20 < min_bp 41 → থামে
&&: lbp 20 ≥ min_bp 0 → বাঁধে
-a * b + c % 3 == x || !ok ⇒ (|| (== (+ (* (- a) b) (% c 3)) x) (! ok))
(10টি সিদ্ধান্ত)
a < b < c ⇒ error: comparison operators cannot be chained
(3টি সিদ্ধান্ত)
দুটি S-expression reference-এর ast-এর সঙ্গে অক্ষরে অক্ষরে মেলে, আর তৃতীয়টি একই বার্তায় থামে। প্রথম expression-এর ৯টি সিদ্ধান্ত ২.৩-এর উত্তর আর stepper-এর ক্রমেই। এই ছোট parser শুধু চেকার; পূর্ণ parser reference-এর parser.py-তে।
৩ · Semantic analysis — কোন নাম কোথায়, কোন error আগে
ঝালিয়ে নিন: পর্ব ৫১ · Symbol table আর name resolution (block scope, shadowing, slot), পর্ব ৫২ · Type checker বাস্তবায়ন. Typing derivation-এর পূর্ণ অনুশীলন পর্ব ৮৫-এ।
৩.১নিচের program-এ লাইন ৬ আর ৮-এর প্রতিটি নাম কোন ঘোষণায় যায়? প্রতিটির ধরন (global/local), symbol table-এর slot আর আউটপুট লিখুন।
1 var total = 0; 2 fn add(n: Int) -> Int { 3 let k = 2; 4 { 5 let k = n * 3; 6 total = total + k; 7 } 8 return total + k; 9 } 10 let k = add(5); 11 print(k); 12 print(total); — ১০ নম্বর (মাঝারি)
| লাইন | নাম | ঘোষণা | ধরন আর slot |
|---|---|---|---|
| ৬ | total (দুবার) | লাইন ১ | global 1 |
| ৬ | k | লাইন ৫ (ভেতরের block) | local 2 |
| ৮ | total | লাইন ১ | global 1 |
| ৮ | k | লাইন ৩ (ভেতরের k-এর scope শেষ) | local 1 |
Local slot ঘোষণার ক্রমে, পুনর্ব্যবহার ছাড়া: n 0, বাইরের k 1, ভেতরের k 2. Global-এ hoisted function আগে: add 0, total 1, top-level k 2. প্রমাণ reference-এর dis: লাইন ৬-এ LOAD_GLOBAL 1 ; total, LOAD_LOCAL 2 ; k, লাইন ৮-এ LOAD_LOCAL 1 ; k, আর main-এ DEFINE_GLOBAL 2 ; k. ফল: k = 2, ভেতরের k = 15, total = 15, ফেরত 15 + 2; সত্যিকারের run 17, তারপর 15. লাইন ১০-এর top-level k function-এর ভেতরের k-কে ছোঁয় না: function ঘোষণার পরে লেখা global function থেকে দেখা যায় না (decision ১৮)। যেখানে নম্বর কাটে: লাইন ৮-এর k-কে ১৫ ধরা।
৩.২1 fn fee(w: Int) -> Int { 2 let base = 40; 3 if w > 5 { return base + extra; } 4 return base + w * "2"; 5 } 6 print(fee(3)); — check কয়টি error দেখাবে, কোনগুলো? লাইন ১-এর আগে let extra = 10; যোগ করলে কী দেখাবে? — ৫ নম্বর (সহজ)
দুটি ভুল আছে, কিন্তু প্রথম run-এ একটিই দেখা যায়: resolver কোনো error পেলে type checker চলেই না (decision ২)। সত্যিকারের run:
3:30: error: undefined variable 'extra'
extra যোগ করলে সব লাইন এক ধাপ নামে; এবার type checker চলে আর w * "2"-এর ডান operand ধরে (অবস্থান expression-এর শুরুতে, decision ২৪):
5:23: error: type mismatch: expected Int, found Str
যেখানে নম্বর কাটে: প্রথম run-এ দুটি বার্তাই লেখা।
৩.৩Resolver-এর সব error অবস্থানসহ লিখুন: 1 fn fee(w: Int) -> Int { 2 let base = 40; 3 if w > 5 { return base + w; } 4 let w2 = w * 2; 5 let w2 = base + w2; 6 { 7 print(cut); 8 let cut = 5; 9 } 10 w = 3; 11 } 12 print(fee(3)); তিনটি ভুল সারালে আর কোন error বাকি থাকে? — ১০ নম্বর (মাঝারি)
5:9: error: 'w2' is already declared in this scope
7:15: error: 'cut' is used before its declaration
10:5: error: cannot assign to parameter 'w'
- লাইন ৫: একই scope-এ আবার ঘোষণা (decision ১৫); shadowing চলে শুধু ভেতরের block-এ।
- লাইন ৭: block-টি নিজেই
cutঘোষণা করে, তাই ঘোষণার আগের ব্যবহার error, বাইরে কোনোcutথাকলেও (decision ১৬)। - লাইন ১০: parameter অপরিবর্তনীয় (decision ১৯)।
তিনটি সারালে (লাইন ৫-এ w3, লাইন ৭ আর ৮ অদলবদল, লাইন ১০ মুছে) type checker চলে আর একটি নতুন error দেখায়, কারণ শেষ return নেই (decision ২১, সত্যিকারের run):
1:4: error: missing return: not every path of function 'fee' returns Int
নম্বর-ভাগ: প্রতিটি error আর কারণ (৩ × ২), ধাপের নিয়ম (২), শেষ error (২)।
৪ · Bytecode আর stack VM — listing লেখা, stack ধরা
ঝালিয়ে নিন: পর্ব ৫৮ · Bytecode নকশা (৩১টি opcode, offset মানে নির্দেশের ক্রমিক নম্বর, decision ২৮; a && b = a; JUMP_IF_FALSE L1; b; JUMP L2; L1: CONST false; L2:), পর্ব ৫৯ · Stack-based virtual machine (operand stack, frame-এর slot).
৪.১fn tax(amount: Int, vip: Bool) -> Int { var t = 0; if amount > 500 && !vip { t = amount / 20; } return t; }-এর bytecode লিখুন (slot: amount 0, vip 1, t 2; constant: 0 → #0, 500 → #1, false → #2, 20 → #3). — ১০ নম্বর (মাঝারি)
Reference-এর dis-এর সত্যিকারের run:
== tax (arity 2, locals 3) ==
0 CONST 0 ; 0
1 STORE_LOCAL 2 ; t
2 LOAD_LOCAL 0 ; amount
3 CONST 1 ; 500
4 GT
5 JUMP_IF_FALSE 9
6 LOAD_LOCAL 1 ; vip
7 NOT
8 JUMP 10
9 CONST 2 ; false
10 JUMP_IF_FALSE 15
11 LOAD_LOCAL 0 ; amount
12 CONST 3 ; 20
13 DIV
14 STORE_LOCAL 2 ; t
15 LOAD_LOCAL 2 ; t
16 RETURN
পড়ার কৌশল: ২–৯ হলো &&-এর ছাঁচ, যার ফল (Bool) ১০-এ if-এর JUMP_IF_FALSE খায়। if-এর then-অংশ return করে না, তাই else-এর ওপর দিয়ে আলাদা JUMP নেই, লক্ষ্য সরাসরি ১৫. ১৭টি নির্দেশ। নম্বর-ভাগ: &&-এর jump (৪), NOT (১), if-এর লক্ষ্য (২), ভাগ আর store (২), return (১)। যেখানে নম্বর কাটে: label-এর নাম লেখা; এখানে jump-এর লক্ষ্য নির্দেশের সংখ্যা।
৪.২৪.১-এর listing ধরে tax(800, false)-এ প্রতিটি নির্দেশের পরে operand stack লিখুন। কয়টি নির্দেশ চলে? tax(800, true)-এ কয়টি? — ১০ নম্বর (মাঝারি)
নিচের stepper আর Python block-এ পুরো trace. সারাংশ: ০–৮ পর্যন্ত টানা (৯টি), ৮-এর JUMP ৯ লাফিয়ে ১০-এ, ১০-এ শর্ত true বলে পড়ে যায়, ১১–১৬ (৬টি)। মোট ১৬, ফল ৪০. vip = true-এ NOT false দেয়, ১০-এ লাফিয়ে ১৫: ০–৮ (৯) + ১০ + ১৫, ১৬ = ১২, ফল ০. Reference VM-এর গোনা (তার নিজের instrs তালিকা গুনে, VM অপরিবর্তিত): দুই ডাক মিলিয়ে tax ২৮ = ১৬ + ১২ ✓. যেখানে নম্বর কাটে: JUMP_IF_FALSE-এর পরে শর্তটি stack-এ রেখে দেওয়া; সে pop করে।
| নির্দেশ | |
| stack (শেষে) | |
| slot | |
| চলা নির্দেশ |
- t = 0. Constant #0 stack-এ, তারপর slot 2-এ। Stack আবার খালি।
- amount > 500. 800 আর 500 ঢোকে,
GTদুটি তুলে true রাখে।JUMP_IF_FALSE 9true তুলে নেয়, লাফ দেয় না। - !vip. false ঢোকে,
NOTতাকে true করে। এই true-ই&&-এর ফল, তাইJUMP 10constant false-এর সারি (৯) ডিঙিয়ে যায়। - if-এর শর্ত। ১০-এ
JUMP_IF_FALSE 15true তুলে নেয়; then-অংশে ঢোকা। - t = amount / 20. 800 / 20 = 40, slot 2-এ রাখা।
- return t. 40 stack-এ,
RETURNframe শেষ করে, মানটি caller-এর জন্য stack-এ থাকে। মোট ১৬টি নির্দেশ।
৪.৩fn sum_to(n: Int) -> Int { var s = 0; var i = 1; while i <= n { s = s + i; i = i + 1; } return s; }. Bytecode-এ loop-এর শর্ত ৪ থেকে ৭ পর্যন্ত (৪টি নির্দেশ), দেহ ৮ থেকে ১৬ (৯টি, শেষে JUMP 4), আগে ৪টি, পরে ২টি। sum_to(3)-এ কয়টি নির্দেশ চলে? সাধারণ সূত্র? — ৫ নম্বর (মাঝারি)
শর্ত চলে n + 1 বার (শেষবার মিথ্যা হয়ে বেরোয়), দেহ n বার: মোট ৪ + ৪(n + 1) + ৯n + ২ = ১৩n + ১০. n = 3: ৪৯. Reference VM-এর গোনা আর পাতার Python block, দুটিই ৪৯ দেয়। যেখানে নম্বর কাটে: শর্তকে n বার গোনা।
৪.৪fn make(step: Int) -> () -> Int { var c = 0; return fn() -> Int { c = c + step; return c; }; }. make-এর bytecode-এ কোন কোন opcode আসবে, আর ভেতরের function কোন opcode-এ c পড়ে? let next = make(5); next(); print(next()); কী ছাপে? — ৫ নম্বর (মাঝারি–কঠিন)
c আর step দুটিই ভেতরের function ব্যবহার করে, তাই দুটিই cell-এ যায়। Reference-এর dis:
== make (arity 1, locals 2) ==
0 LOAD_LOCAL 0 ; step
1 MAKE_CELL 0 ; step
2 CONST 0 ; 0
3 MAKE_CELL 1 ; c
4 MAKE_CLOSURE 1 ; <fn lambda@3:12> captures c, step
5 RETURN
Captured parameter ঢুকেই cell-এ সরে (LOAD_LOCAL 0; MAKE_CELL 0). ভেতরের function পড়ে-লেখে LOAD_FREE 0/STORE_FREE 0 দিয়ে, ফলে প্রতিটি ডাক একই cell বদলায় (closure by reference): প্রথম ডাকে 5, দ্বিতীয়তে 10 (VM-এর সত্যিকারের run). যেখানে নম্বর কাটে: c-কে সাধারণ STORE_LOCAL ধরা; তখন প্রতি ডাকে 5 আসত।
import re # reference-এর `dis` listing পড়ে একটি function চালায়, stack দেখায় (পর্ব ৫৯)
OPS = {"ADD": lambda a, b: a + b, "SUB": lambda a, b: a - b, "MUL": lambda a, b: a * b,
"DIV": lambda a, b: abs(a) // abs(b) * (-1 if (a < 0) != (b < 0) else 1), # C-র মতো
"GT": lambda a, b: a > b, "LE": lambda a, b: a <= b}
def load(path): # প্রতি সারি: (opcode, arg, মন্তব্য)
rows = re.findall(r"^\s+\d+\s+(\w+)\s*(\d*)\s*(?:; (.*))?$", open(path).read(), re.M)
return [(op, int(a) if a else None, c) for op, a, c in rows]
def run(code, args, nlocals, show=False):
slots = list(args) + [None] * (nlocals - len(args)); st, ip, n = [], 0, 0
while True:
at = ip; op, a, c = code[ip]; ip += 1; n += 1
if op == "CONST": st.append(int(c) if c.isdigit() else c == "true")
elif op == "LOAD_LOCAL": st.append(slots[a])
elif op == "STORE_LOCAL": slots[a] = st.pop()
elif op == "NOT": st.append(not st.pop())
elif op in OPS: b = st.pop(); st.append(OPS[op](st.pop(), b))
elif op == "JUMP": ip = a
elif op == "JUMP_IF_FALSE": ip = a if not st.pop() else ip
elif op == "RETURN": return st.pop(), n
if show: print(f"{at:>3} {op:<14}{'' if a is None else a:<3} stack = {st}")
tax = load("tax.dis")
print("tax(800, false) =", run(tax, [800, False], 3, show=True))
print("tax(800, true) =", run(tax, [800, True], 3))
print("sum_to(3) =", run(load("sum_to.dis"), [3], 3))আসল আউটপুট (tax.dis আর sum_to.dis reference-এর dis-এর হুবহু আউটপুট, পাতায় ফাইল হিসেবে রাখা):
0 CONST 0 stack = [0]
1 STORE_LOCAL 2 stack = []
2 LOAD_LOCAL 0 stack = [800]
3 CONST 1 stack = [800, 500]
4 GT stack = [True]
5 JUMP_IF_FALSE 9 stack = []
6 LOAD_LOCAL 1 stack = [False]
7 NOT stack = [True]
8 JUMP 10 stack = [True]
10 JUMP_IF_FALSE 15 stack = []
11 LOAD_LOCAL 0 stack = [800]
12 CONST 3 stack = [800, 20]
13 DIV stack = [40]
14 STORE_LOCAL 2 stack = []
15 LOAD_LOCAL 2 stack = [40]
tax(800, false) = (40, 16)
tax(800, true) = (0, 12)
sum_to(3) = (6, 49)
প্রতিটি সারি নির্দেশটি চলার পরের stack; RETURN-এর সারি ছাপা হয়নি, কিন্তু গোনায় আছে। ১৬, ১২ আর ৪৯: তিনটিই reference VM-এর গোনার সঙ্গে মেলে। এই ছোট VM শুধু এই কয়টি opcode বোঝে; পূর্ণ VM পর্ব ৫৯-এ।
৫ · Three-address code, quadruple, triple আর CFG
ঝালিয়ে নিন: পর্ব ৬২ · Intermediate representation. Haat IR-এর রীতি: operand শুধু নাম, constant আসে t = const k দিয়ে, temp t1, t2 … ফাঁক ছাড়া, label L1 …, block B0 …; &&/|| নামে branch দিয়ে, একটি temp দুই block-এ লেখা হয়। Leader-এর তিন নিয়ম: প্রথম নির্দেশ, jump-এর লক্ষ্য, jump বা branch-এর ঠিক পরের নির্দেশ।
৫.১fn mix(a: Int, b: Int, c: Int) -> Int { let d = (a + b) * (a - b) / c; return d + a * b; }-এর three-address code (Haat IR) লিখুন, তারপর একই কাজ quadruple আর triple-এ। mix(7, 3, 4) কত? — ৫ নম্বর (সহজ)
Post-order-এ গাছ ঘুরে প্রতিটি operator-এর জন্য একটি নির্দেশ; শেষ ফলের নিজের নাম থাকলে (d) temp লাগে না। Python block-এর আসল আউটপুট:
fn mix(a, b, c): quadruple triple
t1 = a + b 0│+│a│b│t1 (0)│+│a│b
t2 = a - b 1│-│a│b│t2 (1)│-│a│b
t3 = t1 * t2 2│*│t1│t2│t3 (2)│*│(0)│(1)
d = t3 / c 3│/│t3│c│d (3)│/│(2)│c
t4 = a * b 4│*│a│b│t4 (4)│*│a│b
t5 = d + t4 5│+│d│t4│t5 (5)│+│(3)│(4)
return t5 6│ret│t5│ │ (6)│ret│(5)│
(10 · 4) / 4 + 21 = 31, reference-এর run-এও 31. Triple-এ ফলের নাম নেই, তাই d-ও সারি (3). পাঠ্যবইয়ের triple-এ d = …-র জন্য আলাদা =-সারি থাকতে পারে (পর্ব ৬২-এর stepper সেভাবেই দেখায়); দুটোই গ্রহণযোগ্য, শুধু রীতিটি লিখে দিন। যেখানে নম্বর কাটে: a * b-কে আগের a + b-এর সঙ্গে গুলিয়ে এক temp দেওয়া।
৫.২fn ship(w: Int, far: Bool) -> Int { var fee = 40; if w > 5 || far { fee = fee + 30; } return fee; }-এর রৈখিক Haat IR লিখুন। ||-এর ফল কোন temp-এ, আর সেটি কয় জায়গায় লেখা হয়? — ১০ নম্বর (মাঝারি)
fn ship(w, far):
fee = const 40
t1 = const 5
t2 = w > t1
branch t2 L2 L1 ; বাঁ পাশ সত্য: ডান পাশ না দেখেই L2
label L1
t2 = far ; একই t2 দ্বিতীয়বার লেখা
label L2
branch t2 L3 L4
label L3
t3 = const 30
fee = fee + t3
label L4
return fee
t2 দুই জায়গায় লেখা হয়: তুলনায় আর far-এর copy-তে। এটিই short-circuit; SSA-তে এখানেই একটি φ লাগবে (৬.২)। Reference-এর run: ship(2, true) = 70, ship(2, false) = 40, IR-এর interpreter-এও একই। নম্বর-ভাগ: branch-এর লক্ষ্যের ক্রম (৪), দ্বিতীয় লেখা (৩), বাকি (৩)। যেখানে নম্বর কাটে: t2 = t1 || far লেখা; Haat IR-এ || কোনো operator নয়, আর তাতে short-circuit হারায়।
৫.৩৫.২-এর IR-এ leader চিহ্নিত করুন, basic block আর CFG-এর edge লিখুন। — ৫ নম্বর (সহজ)
Leader: প্রথম নির্দেশ fee = const 40 (নিয়ম ১), আর চারটি label L1, L2, L3, L4 (নিয়ম ২; প্রতিটি branch-এর পরের নির্দেশও এদেরই একটি, নিয়ম ৩)। পাঁচটি block: B0 (প্রথম চার নির্দেশ), B1 (t2 = far), B2 (দ্বিতীয় branch), B3 (fee = fee + t3), B4 (return). Fall-through-এর জায়গায় build_cfg স্পষ্ট jump বসায়। Edge: B0 → B2, B0 → B1, B1 → B2, B2 → B3, B2 → B4, B3 → B4. Predecessor: B2-এর {B0, B1}, B4-এর {B2, B3}; Python block-এর preds একই দেখায়। যেখানে নম্বর কাটে: label-কে আলাদা নির্দেশ ধরে block গোনা।
৫.৪এই loop-এর IR-এর leader আর block লিখুন: fn points(n: Int, rate: Int) -> Int { var i = 0; var p = 0; while i < n { let bonus = rate * 2; p = p + i * 4 + bonus; if p > 100 { p = p - 50; } i = i + 1; } return p; } — ১০ নম্বর (মাঝারি)
B0: i = const 0; p = const 0; jump B1
B1: t1 = i < n; branch t1 B2 B5 ; loop-এর শর্ত (L1)
B2: t2 = const 2; bonus = rate * t2; t3 = const 4; t4 = i * t3
t5 = p + t4; p = t5 + bonus; t6 = const 100; t7 = p > t6
branch t7 B3 B4 ; দেহ (L2)
B3: t8 = const 50; p = p - t8; jump B4 ; if-এর then (L4)
B4: t9 = const 1; i = i + t9; jump B1 ; if-এর পরে (L5)
B5: return p ; loop-এর পরে (L3)
লক্ষ করুন, block-এর নাম leader-এর ক্রমে, label-এর নম্বরে নয়: L3 (loop-এর বাইরে) সবশেষে আসে বলে B5. Edge: B0→B1, B1→B2, B1→B5, B2→B3, B2→B4, B3→B4, B4→B1 (পেছনের দিকে)। আসল IR পাতার block-গুলো থেকে; points(5, 3) = 70, points(6, 10) = 80, reference-এ একই। যেখানে নম্বর কাটে: t1 = i < n-কে B0-তে রাখা; সেটি jump-এর লক্ষ্য, তাই নতুন block.
from haat_ir import * # পর্ব ৬২-এর haat_front.py আর haat_ir.py, হুবহু
mod = lower_program(parse(open("mix.haat").read()))
fn = mod.funcs["mix"]
print(show_ir(fn)) # Haat IR = নামওয়ালা three-address code
print("\nquadruple (op, arg1, arg2, result):")
for k, i in enumerate(fn.code):
if i.kind == "bin": print(f" {k}│{i.sym}│{i.args[0]}│{i.args[1]}│{i.dst}")
if i.kind == "return": print(f" {k}│ret│{i.args[0]}│ │")
print("\ntriple (op, arg1, arg2) — temp-এর বদলে সারির নম্বর:")
row = {} # temp বা d -> সারি
for k, i in enumerate(fn.code):
ref = lambda x: f"({row[x]})" if x in row else x
if i.kind == "bin": row[i.dst] = k; print(f" ({k})│{i.sym}│{ref(i.args[0])}│{ref(i.args[1])}")
if i.kind == "return": print(f" ({k})│ret│{ref(i.args[0])}│")
build_cfg(fn)
for f in mod.funcs.values():
if f is not fn: build_cfg(f)
print("\nrun_lines:", run_lines(mod), "∣ নির্দেশ চলল:", run_ir(mod, lambda s: None))আসল আউটপুট (পর্ব ৬২-এর haat_front.py আর haat_ir.py পাতার শেষে হুবহু রাখা; quadruple আর triple-এর ছাপা এই পাতার নিজের কোড):
fn mix(a, b, c):
t1 = a + b
t2 = a - b
t3 = t1 * t2
d = t3 / c
t4 = a * b
t5 = d + t4
return t5
quadruple (op, arg1, arg2, result):
0│+│a│b│t1
1│-│a│b│t2
2│*│t1│t2│t3
3│/│t3│c│d
4│*│a│b│t4
5│+│d│t4│t5
6│ret│t5│ │
triple (op, arg1, arg2) — temp-এর বদলে সারির নম্বর:
(0)│+│a│b
(1)│-│a│b
(2)│*│(0)│(1)
(3)│/│(2)│c
(4)│*│a│b
(5)│+│(3)│(4)
(6)│ret│(5)│
run_lines: ['31'] ∣ নির্দেশ চলল: 14
IR-এর interpreter-ও 31 দেয়, reference-এর মতো। ১৪টি নির্দেশ চলে: main-এর ৭টি আর mix-এর ৭টি।
৬ · Dominator, dominance frontier আর SSA
ঝালিয়ে নিন: পর্ব ৬৩ · SSA form. idom(b): b-এর সবচেয়ে কাছের কড়া dominator; DF(x): যেখানে x-এর আধিপত্য ঠিক শেষ হয় (x কোনো predecessor-কে dominate করে, কিন্তু block-টিকে কড়াভাবে নয়); একাধিকবার লেখা নামের জন্য তার সংজ্ঞার block-গুলোর iterated DF-এ φ, আর শুধু যেখানে নামটি live (pruned SSA). নামকরণ x#1, x#2 ….
৬.১৫.৩-এর CFG (edge B0→B1, B0→B2, B1→B2, B2→B3, B2→B4, B3→B4)-এর idom, dominator tree আর প্রতিটি block-এর DF লিখুন। — ৫ নম্বর (সহজ)
idom: B1 → B0, B2 → B0 (B2-তে B0 থেকে সরাসরিও যাওয়া যায়, তাই B1 তাকে dominate করে না), B3 → B2, B4 → B2. Tree: B0-এর সন্তান B1, B2; B2-এর সন্তান B3, B4. DF: B1 → {B2}, B3 → {B4}, বাকিগুলো ফাঁকা। কারণ: B1 B2-এর একটি predecessor-কে (নিজেকে) dominate করে, কিন্তু B2-কে নয়; B0 আর B2 তাদের মিলনের block-কে নিজেরাই dominate করে, তাই তাদের DF ফাঁকা। যেখানে নম্বর কাটে: idom(B2) = B1 লেখা।
৬.২৫.২-এর IR-এ কোন নামের φ কোন block-এ বসবে? তারপর নাম বদলে SSA লিখুন। — ১০ নম্বর (মাঝারি)
একাধিকবার লেখা: t2 (B0, B1) আর fee (B0, B3). DF(B1) = {B2} ⇒ B2-তে t2-এর φ; DF(B3) = {B4} ⇒ B4-তে fee-এর φ. B0-এর DF ফাঁকা, তাই সেখান থেকে কিছু যোগ হয় না। দুটি জায়গাতেই নামটি live, তাই pruned SSA-তেও থাকে।
B0: fee#1 = const 40; t1 = const 5; t2#1 = w > t1; branch t2#1 B2 B1
B1: t2#2 = far; jump B2
B2: t2#3 = phi(B0: t2#1, B1: t2#2); branch t2#3 B3 B4
B3: t3 = const 30; fee#2 = fee#1 + t3; jump B4
B4: fee#3 = phi(B2: fee#1, B3: fee#2); return fee#3
একবার লেখা নাম (t1, t3, parameter) বদলায় না। to_ssa হুবহু এটি দেয়, আর check_ssa কোনো সমস্যা পায় না। নম্বর-ভাগ: multi-def নাম (২), DF থেকে জায়গা (৩), φ-এর argument-এ predecessor-এর ক্রম (২), renaming (৩)। যেখানে নম্বর কাটে: B4-এর φ-এ B0 লেখা; B4-এর predecessor B2 আর B3.
৬.৩৫.৪-এর points-এ (B1 ← B0, B4; B4 ← B2, B3) idom, DF আর φ-গুলো লিখুন। কেন B1-এর DF-এ B1 নিজেই? — ১০ নম্বর (মাঝারি–কঠিন)
idom: B1 → B0, B2 → B1, B5 → B1, B3 → B2, B4 → B2. DF: B1 → {B1}, B2 → {B1}, B3 → {B4}, B4 → {B1}. B1 তার predecessor B4-কে dominate করে, কিন্তু নিজেকে কড়াভাবে নয়, তাই নিজের frontier-এ নিজে: loop-এর header-এ এভাবেই φ আসে। i-এর সংজ্ঞা B0, B4 ⇒ DF(B4) = {B1}; p-এর B0, B2, B3 ⇒ DF(B3) = {B4}, আর B4-এ নতুন φ থেকে DF(B4) = {B1}. ফল তিনটি φ:
B1: i#2 = phi(B0: i#1, B4: i#3)
p#2 = phi(B0: p#1, B4: p#5)
B4: p#5 = phi(B2: p#3, B3: p#4)
পুরো SSA Python block-এ। আসল IR, SSA আর SSA থেকে ফেরা, তিনটিই 70, 80 ছাপে। যেখানে নম্বর কাটে: B4-এ i-এর φ বসানো; B2 বা B3-এ i লেখা হয় না।
৬.৪৬.২-এর SSA থেকে বেরিয়ে আসুন (out of SSA): φ সরিয়ে কোথায় কোন copy বসবে? B0 → B2 edge-এ copy সরাসরি B0-র শেষে বসানো যায় না কেন? — ৫ নম্বর (কঠিন)
B0 একটি branch দিয়ে শেষ হয়, দুই দিকে যায়: B0-র শেষে t2#3 = t2#1 বসালে B1-এর পথেও চলবে। তাই এমন edge (critical edge-এর মতো) ভেঙে নতুন block বসে। out_of_ssa-এর আসল ফল:
B0: fee#1 = const 40; t1 = const 5; t2#1 = w > t1; branch t2#1 B5 B1
B1: t2#2 = far; t2#3 = t2#2; jump B2
B2: branch t2#3 B3 B6
B3: t3 = const 30; fee#2 = fee#1 + t3; fee#3 = fee#2; jump B4
B4: return fee#3
B5: t2#3 = t2#1; jump B2
B6: fee#3 = fee#1; jump B4
B1 আর B3 jump দিয়ে শেষ, তাই copy সেখানেই। চালালে 70, 40, আগের মতো। যেখানে নম্বর কাটে: copy-কে φ-এর block-এর (B2, B4) শুরুতে বসানো; তখন কোন পথে এলেন সেই তথ্য হারায়।
from haat_ssa import * # পর্ব ৬২-এর haat_ir.py আর ৬৩-এর haat_ssa.py, হুবহু
for name, f in [("ship.haat", "ship"), ("points.haat", "points")]:
mod = lower_program(parse(open(name).read()))
fn = mod.funcs[f]
lead = [k for k, i in enumerate(fn.code) if k == 0 or i.kind == "label"
or fn.code[k - 1].kind in ("jump", "branch", "return")]
build_cfg(fn)
print(f"== {f}: leader", [str(fn.code[k]) for k in lead])
print(" preds:", preds(fn))
idom = dominators(fn); df = frontiers(fn, idom)
print(" idom: ", {b: d for b, d in idom.items() if b != "B0"})
print(" DF: ", {b: sorted(s) for b, s in df.items() if s})
multi, phis = place_phis(fn, df, live_in(fn))
print(" একাধিক সংজ্ঞা:", sorted(multi), "∣ φ:", {b: x for b, x in phis.items() if x})আসল আউটপুট (পর্ব ৬৩-এর haat_ssa.py হুবহু):
== ship: leader ['fee = const 40', 'label L1', 'label L2', 'label L3', 'label L4']
preds: {'B0': [], 'B1': ['B0'], 'B2': ['B0', 'B1'], 'B3': ['B2'], 'B4': ['B2', 'B3']}
idom: {'B1': 'B0', 'B2': 'B0', 'B3': 'B2', 'B4': 'B2'}
DF: {'B1': ['B2'], 'B3': ['B4']}
একাধিক সংজ্ঞা: ['fee', 't2'] ∣ φ: {'B2': ['t2'], 'B4': ['fee']}
== points: leader ['i = const 0', 'label L1', 'label L2', 'label L4', 'label L5', 'label L3']
preds: {'B0': [], 'B1': ['B0', 'B4'], 'B2': ['B1'], 'B3': ['B2'], 'B4': ['B2', 'B3'], 'B5': ['B1']}
idom: {'B1': 'B0', 'B5': 'B1', 'B2': 'B1', 'B3': 'B2', 'B4': 'B2'}
DF: {'B1': ['B1'], 'B2': ['B1'], 'B3': ['B4'], 'B4': ['B1']}
একাধিক সংজ্ঞা: ['i', 'p'] ∣ φ: {'B1': ['i', 'p'], 'B4': ['p']}
৫.৩, ৬.১, ৬.২ আর ৬.৩-এর প্রতিটি সংখ্যা এখানে: leader-এর তালিকা, predecessor, idom, DF আর φ-এর জায়গা। points-এ leader-এর ক্রম L1, L2, L4, L5, L3: এটিই B1–B5.
from haat_ssa import * # পর্ব ৬২-এর haat_ir.py আর ৬৩-এর haat_ssa.py, হুবহু
mod = compile_ir(open("points.haat").read())
ssa = to_ssa(mod.funcs["points"])
print(show_ir(ssa))
print("check_ssa:", check_ssa(ssa))
ssa_mod = map_module(mod, to_ssa)
back = map_module(ssa_mod, out_of_ssa)
for label, m in [("আসল IR", mod), ("SSA", ssa_mod), ("SSA থেকে ফেরা", back)]:
print(f"{label:>13}: {run_lines(m)}")আসল আউটপুট:
fn points(n, rate):
B0:
i#1 = const 0
p#1 = const 0
jump B1
B1:
i#2 = phi(B0: i#1, B4: i#3)
p#2 = phi(B0: p#1, B4: p#5)
t1 = i#2 < n
branch t1 B2 B5
B2:
t2 = const 2
bonus = rate * t2
t3 = const 4
t4 = i#2 * t3
t5 = p#2 + t4
p#3 = t5 + bonus
t6 = const 100
t7 = p#3 > t6
branch t7 B3 B4
B3:
t8 = const 50
p#4 = p#3 - t8
jump B4
B4:
p#5 = phi(B2: p#3, B3: p#4)
t9 = const 1
i#3 = i#2 + t9
jump B1
B5:
return p#2
check_ssa: []
আসল IR: ['70', '80']
SSA: ['70', '80']
SSA থেকে ফেরা: ['70', '80']
তিনটি φ, প্রতিটি নামের একটিই সংজ্ঞা (check_ssa ফাঁকা), আর তিন রূপেই একই আউটপুট। SSA-র পরীক্ষা এভাবেই দিন: শর্ত দুটি (এক নামে এক সংজ্ঞা, সংজ্ঞা ব্যবহারকে dominate করে) আর চালিয়ে মেলানো।
৭ · Liveness, reaching definitions আর হাতে optimization
ঝালিয়ে নিন: পর্ব ৬৪ · Dataflow analysis (liveness: backward, IN = use ∪ (OUT − def); reaching definitions: forward, OUT = gen ∪ (IN − kill); সংজ্ঞার নাম B2.5, parameter in), পর্ব ৬৫ · Optimization (constant folding, LVN, DCE; ভাগ শূন্যে ভাগ করতে পারলে মোছে না)।
৭.১৫.৪-এর points-এর প্রতিটি block-এর live-in আর live-out লিখুন। B3-এ n কেন live, যদিও B3 n পড়ে না? — ১০ নম্বর (মাঝারি)
| block | live-in | live-out |
|---|---|---|
| B0 | n rate | i n p rate |
| B1 | i n p rate | i n p rate |
| B2 | i n p rate | i n p rate |
| B3 | i n p rate | i n p rate |
| B4 | i n p rate | i n p rate |
| B5 | p | — |
B3-এর পরে B4, তারপর B1, যেখানে t1 = i < n পড়ে: পরের কোনো পথে পড়া হবে, তাই live. Temp-গুলো (t1–t9) একই block-এ লেখা আর পড়া, তাই কোনো block-এর সীমানায় live নয়। B0-তে i, p লেখা হয় বলে live-in-এ নেই। যেখানে নম্বর কাটে: live-out(B5)-এ p লেখা; return-এর পরে কিছু নেই।
৭.২একই function-এ i-এর সংজ্ঞা B0.0, B4.1 আর p-এর সংজ্ঞা B0.1, B2.5, B3.1. প্রতিটি block-এর শুরুতে কোনগুলো পৌঁছায়? B5-এর return p-এর use-def chain কী? — ১০ নম্বর (মাঝারি)
| block | reaching-in (i, p) |
|---|---|
| B0 | — |
| B1, B2, B5 | i@B0.0 i@B4.1 p@B0.1 p@B2.5 p@B3.1 |
| B3 | i@B0.0 i@B4.1 p@B2.5 |
| B4 | i@B0.0 i@B4.1 p@B2.5 p@B3.1 |
B3-এ শুধু p@B2.5: B2-র ভেতরে p = t5 + bonus আগের সব p-কে kill করে, আর B3-এ আসার পথ একটিই। B4-এ p@B0.1 নেই একই কারণে। B5-এ সব পৌঁছায় (শূন্যবার ঘোরা হলে B0.1-ও), তাই return p-এর ud-chain {B0.1, B2.5, B3.1}: SSA-তে এই তিনটি একটি φ (p#2)-তে এসে মেলে। যেখানে নম্বর কাটে: B5-এ B0.1 বাদ দেওয়া।
৭.৩হাতে optimize করুন (constant folding, LVN/CSE, copy propagation, DCE), প্রতিটি pass আলাদা: fn cart(q: Int) -> Int { let unit = 25; let base = unit * 4; let a = q * base; let b = q * base; let unused = a - b; return a + b + base; }. IR-এর আকার কত থেকে কত? — ১০ নম্বর (মাঝারি)
আসল (৯): unit = const 25; t1 = const 4; base = unit * t1; a = q * base
b = q * base; unused = a - b; t2 = a + b; t3 = t2 + base; return t3
fold: base = unit * t1 → base = const 100 (১ বদল)
lvn: b = q * base → b = a (১ বদল)
copy_prop: unused = a - a; t2 = a + a (২ বদল)
dce: unit, t1, b, unused মোছা (৪ বদল)
ফল (৫): base = const 100; a = q * base; t2 = a + a; t3 = t2 + base; return t3
পর্ব ৬৫-এর optimize-এর লগ হুবহু: (1, 'fold', 1, 9), (1, 'lvn', 1, 9), (1, 'copy_prop', 2, 9), (1, 'dce', 4, 5). cart(3) আগে-পরে 700. লক্ষ করুন: unused = a - a-কে কেউ 0 বানায়নি, তবু মুছে গেছে, কারণ কেউ পড়ে না (dead_stores-ও শুধু unused-কে দেখায়)। যেখানে নম্বর কাটে: t2 = a + a-কে a * 2-এ বদলানো আর বলা যে pass-টি এটি করেছে; এটি strength-এর বিপরীত দিক, আর এই pipeline তা করে না।
৭.৪ভুল ধরুন। একজন লিখলেন: “fn trap(a: Int, b: Int) -> Int { var x = a; let m = x * b; x = x + 1; let n = x * b; return m + n; }-এ x * b দুবার আছে, তাই CSE করে n = m.” — ৫ নম্বর (মাঝারি)
ভুল: দুই x * b-এর মাঝে x বদলেছে, তাই দুটি আলাদা মান। LVN-এ x = x + 1-এর পরে x নতুন value number পায়, তাই key মেলে না। পর্ব ৬৫-এর pipeline-এর আসল ফল: m = a * b, x = a + t1, n = x * b (copy propagation x-কে a দিয়ে বদলেছে, DCE x = a মুছেছে), আর trap(4, 5) আগে-পরে 45 = 20 + 25. ভুল CSE-তে আসত 40. নম্বর-ভাগ: ভুল চিহ্নিত (২), কারণ (২), সঠিক ফল (১)।
from haat_dfa import * # পর্ব ৬২-এর haat_ir.py আর ৬৪-এর haat_dfa.py, হুবহু
fn = compile_ir(open("points.haat").read()).funcs["points"]
live = solve(LIVENESS, fn)
rd = solve(REACHING, fn)
pick = lambda s: sorted(d for d in s if d[0] in ("i", "p")) # শুধু i আর p-এর সংজ্ঞা
print("block │ live-in │ live-out │ reaching-in (i, p)")
for b in fn.blocks:
print(f"{b:5} │ {' '.join(sorted(live.IN[b])):18} │ {' '.join(sorted(live.OUT[b])):18} │",
" ".join(f"{x}@{w}" for x, w in pick(rd.IN[b])))
print("\nfee: প্রতিটি নির্দেশের পরে live")
fee = compile_ir(open("fee.haat").read()).funcs["fee"]
_, pts = analyze(fee, LIVENESS)
for i, ins in enumerate(fee.blocks["B0"]):
print(f" {str(ins):12} │ আগে {sorted(pts['B0', i][0])} │ পরে {sorted(pts['B0', i][1])}")
print("dead_stores(cart):", dead_stores(compile_ir(open("cart.haat").read()).funcs["cart"]))আসল আউটপুট (পর্ব ৬৪-এর haat_dfa.py হুবহু):
block │ live-in │ live-out │ reaching-in (i, p)
B0 │ n rate │ i n p rate │
B1 │ i n p rate │ i n p rate │ i@B0.0 i@B4.1 p@B0.1 p@B2.5 p@B3.1
B2 │ i n p rate │ i n p rate │ i@B0.0 i@B4.1 p@B0.1 p@B2.5 p@B3.1
B3 │ i n p rate │ i n p rate │ i@B0.0 i@B4.1 p@B2.5
B4 │ i n p rate │ i n p rate │ i@B0.0 i@B4.1 p@B2.5 p@B3.1
B5 │ p │ │ i@B0.0 i@B4.1 p@B0.1 p@B2.5 p@B3.1
fee: প্রতিটি নির্দেশের পরে live
x = a + b │ আগে ['a', 'b'] │ পরে ['a', 'b', 'x']
y = a * x │ আগে ['a', 'b', 'x'] │ পরে ['b', 'x', 'y']
z = x - b │ আগে ['b', 'x', 'y'] │ পরে ['y', 'z']
t1 = y + z │ আগে ['y', 'z'] │ পরে ['t1']
return t1 │ আগে ['t1'] │ পরে []
dead_stores(cart): [('B0', 5, 'unused')]
উপরের ছক ৭.১ আর ৭.২-এর উত্তর। নিচের অংশটি অংশ ৯-এর জন্য: fee-এর প্রতিটি নির্দেশের আগে-পরে live নাম। একটি নাম লেখার মুহূর্তে যারা live, তারাই তার শত্রু (interference).
from haat_opt import * # পর্ব ৬২, ৬৪ আর ৬৫-এর ফাইল, হুবহু
import copy
mod = compile_ir(open("cart.haat").read())
before = run_lines(mod)
for name in ("cart", "trap"):
fn = mod.funcs[name]; old = size(fn); log = []
optimize(fn, log=log)
print(show_ir(fn))
print(f" আকার {old} → {size(fn)}; pass-এর লগ (রাউন্ড, pass, বদল, আকার):", log)
print("আগে:", before, "∣ পরে:", run_lines(mod))আসল আউটপুট (পর্ব ৬৫-এর haat_opt.py হুবহু):
fn cart(q):
B0:
base = const 100
a = q * base
t2 = a + a
t3 = t2 + base
return t3
আকার 9 → 5; pass-এর লগ (রাউন্ড, pass, বদল, আকার): [(1, 'fold', 1, 9), (1, 'lvn', 1, 9), (1, 'copy_prop', 2, 9), (1, 'dce', 4, 5)]
fn trap(a, b):
B0:
m = a * b
t1 = const 1
x = a + t1
n = x * b
t2 = m + n
return t2
আকার 7 → 6; pass-এর লগ (রাউন্ড, pass, বদল, আকার): [(1, 'copy_prop', 2, 7), (1, 'dce', 1, 6)]
আগে: ['700', '45'] ∣ পরে: ['700', '45']
৭.৩ আর ৭.৪-এর উত্তর। trap-এ দুটি গুণই রয়ে গেছে, আর দুই program-এর আউটপুট আগে-পরে এক।
৮ · Natural loop, LICM আর strength reduction
ঝালিয়ে নিন: পর্ব ৬৬ · Loop optimization. Back edge b → h: h, b-কে dominate করে; natural loop = h আর যারা h না ছুঁয়ে b-তে পৌঁছায়; preheader-এ সরে loop-invariant নির্দেশ, যদি তার নাম loop-এ একবারই লেখা, operand loop-এ বদলায় না, header-এ পুরোনো মান লাগে না, আর আগে চালালে নতুন error হয় না।
৮.১points-এর (৫.৪) back edge, loop-এর দেহ আর exit edge লিখুন। Preheader কোনটি? — ৫ নম্বর (সহজ)
B4 → B1 back edge (idom শৃঙ্খলে B1 B4-কে dominate করে)। দেহ: B4 থেকে পেছনে predecessor ধরে, B1-এ থেমে: {B1, B2, B3, B4}. Exit: B1 → B5. B1-এর বাইরের predecessor একটিই, B0, আর সেটি jump দিয়ে শেষ, তাই B0-ই preheader; নতুন block লাগে না। যেখানে নম্বর কাটে: B5-কে দেহে ধরা।
৮.২fn avg_all(n: Int, k: Int) -> Int { var i = 0; var s = 0; while i < n { let share = 100 / k; let step = n * 2; s = s + share + step; i = i + 1; } return s; }. Loop-এর কোন নির্দেশ preheader-এ যায়, কোনটি যায় না? share সরালে avg_all(0, 0)-এ কী হয়? — ১০ নম্বর (মাঝারি–কঠিন)
সরে: t2 = const 100, t3 = const 2, step = n * t3, t5 = const 1 (চারটি)। সরে না: share = t2 / k, যদিও তার operand loop-এ বদলায় না। কারণ: ভাজক k শূন্য হতে পারে। n = 0 হলে loop একবারও চলে না, আসল program কখনো ভাগ করে না আর 0 ছাপে; সরানো program ভাগটি আগেই করে। এটি দেখানো হয়েছে ইচ্ছা করে নিয়ম ভেঙে (unsafe=True), আসল আউটপুট:
ঠিক LICM: ['93', '0']
ভুল LICM: ['93', '5:25: runtime error: division by zero']
Reference-এর run: 93, 0. s আর i loop-এ লেখা হয়, তাই কোনোটির নির্দেশ সরে না। নম্বর-ভাগ: সরা নির্দেশ (৩), ভাগের নিষেধ আর কারণ (৪), counterexample (৩)। যেখানে নম্বর কাটে: “operand invariant, তাই সরানো যায়” বলে থামা; নিরাপত্তার শর্ত আলাদা।
৮.৩points-এ LICM-এর পরে t4 = i * t3 (t3 = 4) আর i = i + t9 (t9 = 1). Strength reduction করুন: কোন নতুন temp, কোথায় কোন নির্দেশ? — ১০ নম্বর (কঠিন)
i একটি basic induction variable (loop-এ একবার লেখা, i = i + 1), আর t4 = i * 4 তার থেকে derived. গুণের বদলে যোগ চালু রাখা:
preheader B0: t10 = i * t3 ; শুরুর মান 0 · 4
t11 = t9 * t3 ; প্রতি ঘোরায় বাড়ে 1 · 4
B2: t4 = t10 ; গুণ নেই
B4: i = i + t9
t10 = t10 + t11 ; i-এর ঠিক পরে
পর্ব ৬৬-এর strength_reduce-এর লগ হুবহু এই তিনটি নির্দেশ দেয়। পুরো program (দুই ডাক) চলা IR নির্দেশ ১৮২ থেকে ১৫২ (LICM আর strength reduction মিলিয়ে); আউটপুট 70, 80 অপরিবর্তিত। যেখানে নম্বর কাটে: t10-এর হালনাগাদ B2-তে বসানো; তখন i বাড়ার আগেই সে বাড়ে।
from haat_loop import * # পর্ব ৬২, ৬৩, ৬৪ আর ৬৬-এর ফাইল, হুবহু
mod = compile_ir(open("share.haat").read())
fn = mod.funcs["avg_all"]
idom = dominators(fn)
print("back edge:", back_edges(fn, idom))
for L in natural_loops(fn): print("loop:", L.header, sorted(L.body), "exit:", L.exits)
before = run_ir(mod, lambda s: None); log = []
print("LICM সরাল:", licm(fn, log=log))
for b, ins, why in log: print(f" {b}: {ins:16} {why}")
print("avg_all ফল:", run_lines(mod), f"∣ চলা নির্দেশ {before} → {run_ir(mod, lambda s: None)}")
bad = compile_ir(open("share.haat").read())
licm(bad.funcs["avg_all"], unsafe=True) # ইচ্ছা করে ভাগের নিয়ম ভাঙা
print("ভুল LICM-এর পরে:", run_lines(bad))
pm = compile_ir(open("points.haat").read())
p = pm.funcs["points"]; n0 = run_ir(pm, lambda s: None)
licm(p); log = []
print("strength reduction:", strength_reduce(p, log=log), log)
print("points ফল:", run_lines(pm), f"∣ চলা নির্দেশ {n0} → {run_ir(pm, lambda s: None)}")
print(show_ir(p).split("B1:")[0] + "B4:", *map(str, p.blocks["B4"]), sep=chr(10) + " ")আসল আউটপুট (পর্ব ৬৬-এর haat_loop.py, সঙ্গে ৬৩ আর ৬৪-এর ফাইল, হুবহু):
back edge: [('B2', 'B1')]
loop: B1 ['B1', 'B2'] exit: [('B1', 'B3')]
LICM সরাল: 4
B2: t2 = const 100 → B0
B2: share = t2 / k ভাজক শূন্য হতে পারে
B2: t3 = const 2 → B0
B2: step = n * t3 → B0
B2: t5 = const 1 → B0
B2: share = t2 / k ভাজক শূন্য হতে পারে
avg_all ফল: ['93', '0'] ∣ চলা নির্দেশ 55 → 51
ভুল LICM-এর পরে: ['93', '5:25: runtime error: division by zero']
strength reduction: 1 [('B0', 't10 = i * t3', 't11 = t9 * t3', 't10 = t10 + t11')]
points ফল: ['70', '80'] ∣ চলা নির্দেশ 182 → 152
fn points(n, rate):
B0:
i = const 0
p = const 0
t2 = const 2
bonus = rate * t2
t3 = const 4
t6 = const 100
t8 = const 50
t9 = const 1
t10 = i * t3
t11 = t9 * t3
jump B1
B4:
i = i + t9
t10 = t10 + t11
jump B1
LICM-এর লগে share-এর প্রত্যাখ্যান দুবার, কারণ একটি নির্দেশ সরলে pass আবার পুরো loop দেখে। avg_all-এ চলা নির্দেশ মাত্র ৫৫ থেকে ৫১: প্রতি ডাকে preheader-এ চারটি নির্দেশ যোগ হয়, আর দ্বিতীয় ডাকে loop চলেই না।
৯ · Register allocation, stack frame আর GC trace
ঝালিয়ে নিন: পর্ব ৭০ · Register allocation (interference graph, Chaitin/Briggs-এর simplify–select, spill), পর্ব ৭১ · Calling convention আর ABI (Haat ABI v1: প্রতিটি IR নাম ৮ byte-এর slot, প্রথম লেখার ক্রমে s0 - 24 থেকে নিচে; ra -8, s0 -16; frame ১৬-এর গুণিতক; ৮টির বেশি argument caller-এর sp+0, sp+8 …-এ), পর্ব ৭৫ · Garbage collection.
৯.১fn fee(a: Int, b: Int) -> Int { let x = a + b; let y = a * x; let z = x - b; return y + z; }-এর IR: x = a + b; y = a * x; z = x - b; t1 = y + z; return t1. Liveness থেকে interference graph আঁকুন, প্রতিটি node-এর degree লিখুন। — ১০ নম্বর (মাঝারি)
নিয়ম: যে নাম লেখা হচ্ছে, লেখার ঠিক পরে যারা live, তাদের সঙ্গে edge; আর function-এর শুরুতে সব parameter একসঙ্গে live.
শুরু : a, b একসঙ্গে → a–b
x = a + b পরে live {a, b, x} → x–a, x–b
y = a * x পরে live {b, x, y} → y–b, y–x
z = x - b পরে live {y, z} → z–y
t1 = y + z পরে live {t1} → কোনো edge নেই
Edge: a–b, a–x, b–x, b–y, x–y, y–z (৬টি)। Degree: a 2, b 3, x 3, y 3, z 1, t1 0. b আর y শত্রু, কারণ y লেখার পরেও z = x - b-এর জন্য b লাগবে। যেখানে নম্বর কাটে: a–y edge দেওয়া; y = a * x-এর পরে a আর live নয়।
৯.২৯.১-এর graph k = 3 register (r0, r1, r2)-এ রং করুন: simplify-এর ক্রম, তারপর select, প্রতিবেশীর না-নেওয়া প্রথম register. k = 2-এ কী হয়? — ১০ নম্বর (মাঝারি–কঠিন)
k = 3: simplify a (2 < 3), তারপর b, x, y, z, t1, প্রতিবার degree k-এর কম। Select উল্টো ক্রমে: t1 r0, z r0, y r1, x r0, b r2, a r1. কোনো spill নেই (নিচের stepper).
k = 2: a, b, x একটি ত্রিভুজ, তাই দুই রঙে অসম্ভব। Simplify z আর t1 সরানোর পরে সবার degree ≥ 2, তাই spill-এর প্রার্থী বাছা হয় খরচ ÷ degree দেখে: b. Briggs-এর আশাবাদী select-এও b রং পায় না, তাই spill. পর্ব ৭০-এর পূর্ণ allocate spill code বসিয়ে graph নতুন করে বানায়, শেষে b আর y stack-এ (৩ রাউন্ড), আর register-এর নামে লেখা কোডও 24 দেয় (fee(3, 4) = 21 + 3). যেখানে নম্বর কাটে: select-এ সাধারণ ক্রমে (a আগে) রং দেওয়া; stack থেকে উল্টো ক্রমে নিতে হয়।
| কাজ | |
| degree বা stack | |
| রং |
- শুরু। ছয়টি node. b, x, y-এর degree ৩, k-এর সমান, তাই এরা এখনই সরতে পারে না।
- simplify a. a-এর degree ২ < ৩: সরিয়ে stack-এ। তার প্রতিবেশী b আর x-এর degree এক করে কমে ২।
- বাকিরা। এখন সবাই < ৩: b, x, y, z, t1 পরপর stack-এ। কোনো spill-প্রার্থী লাগেনি।
- select শুরু। শেষে ঢোকা আগে বেরোয়: t1 r0 (প্রতিবেশী নেই), z r0 (y এখনো রঙহীন), y r1 (প্রতিবেশী z r0).
- select শেষ। x: প্রতিবেশী y r1 ⇒ r0. b: x r0, y r1 ⇒ r2. a: b r2, x r0 ⇒ r1. তিন রঙে সম্পূর্ণ।
- k = 2. ত্রিভুজ দুই রঙে হয় না: b spill. পূর্ণ allocator spill code বসিয়ে আবার চালায়; শেষে b আর y stack-এ, আর কোডটি চালালে 24.
৯.৩Haat ABI v1-এ fn total(qty: Int, unit: Int, d: Int) -> Int { let p = price(qty, unit); return p + d; } (IR: p = call price(qty, unit); t1 = p + d; return t1)-এর activation record আঁকুন: প্রতিটি slot-এর s0-সাপেক্ষ offset, frame-এর আকার, prologue, call sequence আর epilogue. — ১০ নম্বর (মাঝারি)
Saved: ra −8, s0 −16. Slot প্রথম লেখার ক্রমে (parameter আগে): qty −24, unit −32, d −40, p −48, t1 −56. মোট ৫৬ byte, ১৬-এর গুণিতকে ৬৪. ৮টির বেশি argument-এর কোনো ডাক নেই, তাই out_args 0. পর্ব ৭১-এর prologue, call_seq আর epilogue-এর আসল আউটপুট:
haat_total:
addi sp, sp, -64
sd ra, 56(sp)
sd s0, 48(sp)
addi s0, sp, 64
sd a0, -24(s0) # qty
sd a1, -32(s0) # unit
sd a2, -40(s0) # d
ld a0, -24(s0) ; call sequence
ld a1, -32(s0)
call haat_price
sd a0, -48(s0) ; p
... ; t1 = p + d, ফল a0-তে (পর্ব ৭২-এর কাজ)
ld ra, 56(sp)
ld s0, 48(sp)
addi sp, sp, 64
ret
sd ra, 56(sp) আর “ra s0 − 8-এ” একই জায়গা, কারণ s0 = sp + 64. নম্বর-ভাগ: slot-এর offset (৪), আকার আর গোল করা (২), prologue/epilogue (২), call sequence (২)। যেখানে নম্বর কাটে: ৫৬-কে frame-এর আকার বলা; RISC-V psABI-তে sp ১৬-এ সাজানো থাকতে হয়।
৯.৪১০টি parameter-এর fn sum10(a: Int, b: Int, c: Int, d: Int, e: Int, f: Int, g: Int, h: Int, i: Int, j: Int) -> Int { return a + j; } আর তাকে ডাকা fn caller(x: Int) -> Int { let r = sum10(x, 2, 3, 4, 5, 6, 7, 8, 9, 10); return r; }. i আর j কোথায় থাকে? দুই frame-এর আকার কত? — ১০ নম্বর (কঠিন)
- Caller-এর দিক: প্রথম ৮টি a0–a7-এ; ৯ম আর ১০ম caller-এর frame-এর তলায়:
ld t0, -88(s0); sd t0, 0(sp); ld t0, -96(s0); sd t0, 8(sp), তারপরcall haat_sum10. তাই caller-এর out_args ১৬. Caller-এর IR নাম ১১টি (x, t1–t9, r): 16 + 88 + 16 = ১২০ → ১২৮. - Callee-র দিক:
sum10-এর s0 = caller-এর sp, তাইi0(s0)-এ,j8(s0)-এ; এদের নিজস্ব slot নেই। নিজের slot: a–h আর t1, নয়টি: 16 + 72 = ৮৮ → ৯৬.
frame_layout-এর আসল আউটপুট: sum10 size 96, i → 0, j → 8; caller size 128, out_args 16. Program-টি চালালে 11 (1 + 10). যেখানে নম্বর কাটে: i, j-কে callee-র ঋণাত্মক offset-এ রাখা।
৯.৫Heap: A → [B, C], B → [E], C → [E, A], D → [ ], E → [ ], F → [G], G → [F], H → [B]. Root: cart → A, tmp → D. (ক) প্রতিটি object-এর reference count (খ) Mark-sweep-এ mark-এর ক্রম (root-এর তালিকা stack, শেষেরটি আগে) আর sweep-এ মোছা (গ) Cheney copying-এর to-space (ঘ) tmp সরালে reference counting কী মুক্ত করে, কী পারে না? — ১০ নম্বর (মাঝারি–কঠিন)
- (ক) A 2 (cart, C), B 2 (A, H), C 1, D 1, E 2, F 1, G 1, H 0.
- (খ) Stack [A, D] থেকে D আগে: mark D, A, তারপর A-এর ref [B, C] stack-এ, C আগে: C, E, B. ক্রম D, A, C, E, B; A আবার এলে বাদ। Sweep পুরো heap ঘুরে মোছে F, G, H.
- (গ) Root আগে কপি: to[0] A, to[1] D. Scan A: B → to[2], C → to[3]; scan B: E → to[4]; scan C: E আগেই আছে (forwarding), A → 0. ফল A → [2, 3], D → [ ], B → [4], C → [4, 0], E → [ ]. ৫টি জীবিত কপি, garbage ছোঁয়াই হয়নি।
- (ঘ) H-এর গণনা ০, তাই RC তাকে আগেই মুক্ত করে আর B কমে ১-এ।
tmpসরালে D ০, মুক্ত। F আর G পরস্পরকে ধরে রাখে (১, ১): RC কখনো মুক্ত করে না, cycle-এর leak. Tracing-এ সরানোর পরে mark A, C, E, B; মোছে D, F, G, H. A ↔ C cycle-টিও আছে, কিন্তু সে root থেকে পৌঁছানো যায়, তাই জীবিত।
সব সংখ্যা নিচের Python block-এর আসল run. Mark-এ stack আর Cheney-তে scan pointer, পর্ব ৭৫-এর simulator-এর নিয়মেই। যেখানে নম্বর কাটে: Cheney-কে DFS ক্রমে লেখা; সে BFS.
from haat_ra import * # পর্ব ৬২, ৬৪ আর ৭০-এর ফাইল, হুবহু
mod = compile_ir(open("fee.haat").read())
fn = mod.funcs["fee"]
G, moves = interference(fn)
edges = sorted({tuple(sorted((a, b))) for a in G for b in G[a]})
print("edge:", " ".join(f"{a}–{b}" for a, b in edges), "∣ degree:", {x: len(n) for x, n in G.items()})
for k in (3, 2):
tr = []
colour, spill = color(G, k, spill_cost(fn), [f"r{i}" for i in range(k)], trace=tr)
print(f"k = {k}:", " ".join(f"{t[0]}:{t[1]}" + (f"={t[2]}" if len(t) > 2 else "") for t in tr))
print(" রং:", colour, "∣ spill:", spill)
A = allocate(fn, ["r0", "r1"])
print(f"allocate(k = 2): spill {A.spilled}, রাউন্ড {A.rounds}")
print(show_ir(A.fn))
mod.funcs["fee"] = A.fn
print("ফল:", run_lines(mod))আসল আউটপুট (পর্ব ৭০-এর haat_ra.py হুবহু; register-এর নাম এখানে r0, r1, r2):
edge: a–b a–x b–x b–y x–y y–z ∣ degree: {'a': 2, 'b': 3, 'x': 3, 'y': 3, 'z': 1, 't1': 0}
k = 3: simplify:a simplify:b simplify:x simplify:y simplify:z simplify:t1 select:t1=r0 select:z=r0 select:y=r1 select:x=r0 select:b=r2 select:a=r1
রং: {'t1': 'r0', 'z': 'r0', 'y': 'r1', 'x': 'r0', 'b': 'r2', 'a': 'r1'} ∣ spill: []
k = 2: simplify:z simplify:t1 spill?:b simplify:a simplify:x simplify:y select:y=r0 select:x=r1 select:a=r0 select:b=spill select:t1=r0 select:z=r1
রং: {'y': 'r0', 'x': 'r1', 'a': 'r0', 't1': 'r0', 'z': 'r1'} ∣ spill: ['b']
allocate(k = 2): spill ['b', 'y'], রাউন্ড 3
fn fee(r0, r1):
B0:
$b = r1
r1 = $b
r1 = r0 + r1
r0 = r0 * r1
$y = r0
r0 = $b
r1 = r1 - r0
r0 = $y
r0 = r0 + r1
return r0
ফল: ['24']
৯.১-এর ছয়টি edge আর degree, ৯.২-এর দুই রং-করা। $b আর $y stack slot, ~-চিহ্নের ছোট temp গুলো spill code-এর। শেষ লাইন: রং-করা কোড চালিয়েও 24.
from haat_abi import * # পর্ব ৬২-এর haat_ir.py আর ৭১-এর haat_abi.py, হুবহু
mod = compile_ir(open("total.haat").read())
fn = mod.funcs["total"]; fr = frame_layout(fn)
print("total: size", fr.size, "∣ saved", fr.saved, "∣ slots", fr.slots)
call = next(i for i in fn.blocks["B0"] if i.kind == "call")
print("\n".join(prologue(fr) + call_seq(fr, call) + epilogue(fr)))
many = compile_ir(open("many.haat").read())
for name in ("sum10", "caller"):
f = frame_layout(many.funcs[name])
print(f"\n{name}: size {f.size}, out_args {f.out_args}, i → {f.slots.get('i')}, j → {f.slots.get('j')}")
c = next(i for i in many.funcs["caller"].blocks["B0"] if i.kind == "call")
print("\n".join(call_seq(frame_layout(many.funcs["caller"]), c)[-6:]))
print("চালানো:", run_lines(mod), run_lines(many))আসল আউটপুট (পর্ব ৭১-এর haat_abi.py হুবহু):
total: size 64 ∣ saved {'ra': -8, 's0': -16} ∣ slots {'qty': -24, 'unit': -32, 'd': -40, 'p': -48, 't1': -56}
haat_total:
addi sp, sp, -64
sd ra, 56(sp)
sd s0, 48(sp)
addi s0, sp, 64
sd a0, -24(s0) # qty
sd a1, -32(s0) # unit
sd a2, -40(s0) # d
ld a0, -24(s0)
ld a1, -32(s0)
call haat_price
sd a0, -48(s0)
ld ra, 56(sp)
ld s0, 48(sp)
addi sp, sp, 64
ret
sum10: size 96, out_args 0, i → 0, j → 8
caller: size 128, out_args 16, i → None, j → None
ld t0, -88(s0)
sd t0, 0(sp)
ld t0, -96(s0)
sd t0, 8(sp)
call haat_sum10
sd a0, -104(s0)
চালানো: ['996'] ['11']
৯.৩ আর ৯.৪-এর offset, আকার আর call sequence. caller-এর i/j None, কারণ ওই নাম caller-এর নয়।
# heap: object -> যাদের দিকে pointer (ক্রম গুরুত্বপূর্ণ); root: global আর frame-এর slot (পর্ব ৭৫-এর নিয়মে)
heap = {"A": ["B", "C"], "B": ["E"], "C": ["E", "A"], "D": [], "E": [],
"F": ["G"], "G": ["F"], "H": ["B"]}
roots = {"cart": "A", "tmp": "D"}
def mark_sweep(roots):
marked, grey, order = set(), list(roots.values()), []
while grey: # stack: শেষেরটি আগে (DFS)
o = grey.pop()
if o in marked: continue
marked.add(o); order.append(o); grey += heap[o]
return order, [o for o in heap if o not in marked]
def cheney(roots):
to, fwd = [], {}
def copy(o):
if o not in fwd: fwd[o] = len(to); to.append([o, list(heap[o])])
return fwd[o]
for r in roots.values(): copy(r)
scan = 0
while scan < len(to): # scan ধরে ধরে পরের object-গুলো কপি (BFS)
to[scan][1] = [copy(r) for r in to[scan][1]]; scan += 1
return to
def rc_counts():
rc = {o: 0 for o in heap}
for o in [*roots.values(), *(r for refs in heap.values() for r in refs)]: rc[o] += 1
return rc
print("rc:", rc_counts())
print("mark-sweep:", mark_sweep(roots))
for i, (o, refs) in enumerate(cheney(roots)): print(f" to[{i}] {o} → {refs}")
del roots["tmp"] # frame ফিরে গেল
print("tmp-এর পরে rc:", rc_counts(), "∣ mark-sweep:", mark_sweep(roots))আসল আউটপুট:
rc: {'A': 2, 'B': 2, 'C': 1, 'D': 1, 'E': 2, 'F': 1, 'G': 1, 'H': 0}
mark-sweep: (['D', 'A', 'C', 'E', 'B'], ['F', 'G', 'H'])
to[0] A → [2, 3]
to[1] D → []
to[2] B → [4]
to[3] C → [4, 0]
to[4] E → []
tmp-এর পরে rc: {'A': 2, 'B': 2, 'C': 1, 'D': 0, 'E': 2, 'F': 1, 'G': 1, 'H': 0} ∣ mark-sweep: (['A', 'C', 'E', 'B'], ['D', 'F', 'G', 'H'])
এখানে reference count প্রতিবার pointer থেকে নতুন করে গোনা হয়েছে, তাই H-এর ০ দেখায় যে RC তাকে এখনই মুক্ত করত। পর্ব ৭৫-এর simulator গণনা চলতে চলতে রাখে; প্রশ্নের উত্তর একই।
১০ · মিশ্র সমস্যা — অনুবাদ করুন, যাচাই করুন
বড় প্রশ্নে কয়েকটি ধাপ পরপর আসে, আর প্রতিটি ধাপের পরে একটি যাচাই চাওয়া হয়। কৌশল একটাই: প্রতিটি রূপান্তরের পরে চালিয়ে আউটপুট মেলান, আর গোনার প্রশ্নে কী গোনা হচ্ছে (static না dynamic, কোন function), প্রথম লাইনেই লিখুন।
১০.১fn tax(amount: Int, vip: Bool) -> Int { var t = 0; if amount > 500 && !vip { t = amount / 20; } return t; }, ডাক print(tax(800, false));. (ক) Haat IR-এর CFG (খ) SSA (গ) tax-এর ভেতরে কয়টি IR নির্দেশ চলে, আর ৪.২-এর bytecode-এ কয়টি? পার্থক্যের কারণ? — ১৫ নম্বর (কঠিন)
B0: t = const 0; t1 = const 500; t2 = amount > t1; branch t2 B1 B2
B1: t2 = ! vip; jump B2
B2: branch t2 B3 B4
B3: t3 = const 20; t = amount / t3; jump B4
B4: return t
(খ) t2 (B0, B1) আর t (B0, B3) দুবার লেখা: t2#3 = phi(B0: t2#1, B1: t2#2) B2-তে, t#3 = phi(B2: t#1, B3: t#2) B4-এ, ৬.২-এর ship-এর মতোই। (গ) IR: B0 ৪ + B1 ২ + B2 ১ + B3 ৩ + B4 ১ = ১১ (IR interpreter পুরো program-এ ১৭ গোনে, তার ৬টি main-এর)। Bytecode: ১৬ (reference VM). কারণ: stack VM-এ প্রতিটি operand আলাদা LOAD_LOCAL/CONST, আর ফল রাখতে STORE_LOCAL; three-address code একটি নির্দেশে দুই operand আর ফলের নাম দেয়। নম্বর-ভাগ: CFG (৫), φ দুটি (৪), দুই গোনা (৪), কারণ (২)। যেখানে নম্বর কাটে: দুই গোনার একটিতে main-এর নির্দেশ মেশানো।
১০.২এক লাইনের সিদ্ধান্ত, প্রতিটিতে কারণ: (ক) x * b দুবার, মাঝে x বদল: CSE চলে? (খ) let share = 100 / k; loop-এ: সরানো চলে? (গ) ৯.১-এর graph তিন রঙে হয়? (ঘ) Haat ABI v1-এ ৯ম argument callee-র কোথায়? (ঙ) A ↔ C cycle root থেকে পৌঁছায়: RC আর tracing কী করে? — ৫ নম্বর (মাঝারি)
(ক) না: দুই মান আলাদা; LVN নতুন value number দেয় (৭.৪)
(খ) না: k = 0 আর শূন্যবার ঘোরা হলে নতুন runtime error (৮.২)
(গ) হ্যাঁ, কিন্তু দুই রঙে নয়: a, b, x ত্রিভুজ (৯.২)
(ঘ) 0(s0): caller-এর sp+0, নিজের slot নেই (৯.৪)
(ঙ) দুজনেই রাখে: পৌঁছানো যায়, তাই জীবিত; সমস্যা হয় শুধু
পৌঁছানো যায় না এমন cycle-এ RC-র (৯.৫)
শেষ মুহূর্তের নিয়ম-তালিকা আর সাধারণ ভুল
| বিষয় | নিয়ম | সাধারণ ভুল | পর্ব |
|---|---|---|---|
| Token | সবচেয়ে লম্বা বৈধ operator | -- বা ->-এর ভাগ ভুল | ৪৬ |
| Pratt | lbp ≥ min_bp হলে বাঁধে; rbp = lbp + ১ | rbp = lbp, ফলে ডান-সংযোগ | ৪৮ |
| নাম-সমাধান | ভেতরের block আগে; slot ঘোষণার ক্রমে | scope শেষের পরেও ভেতরের নাম ধরা | ৫১ |
| Bytecode | jump-এর লক্ষ্য নির্দেশের নম্বর | JUMP_IF_FALSE-এর পরে শর্ত stack-এ রাখা | ৫৮, ৫৯ |
| Leader | প্রথম, লক্ষ্য, jump-এর পরেরটি | jump-এর লক্ষ্যকে আগের block-এ রাখা | ৬২ |
| φ | সংজ্ঞার block-গুলোর iterated DF, live হলে | predecessor-এর বদলে dominator লেখা | ৬৩ |
| Liveness | IN = use ∪ (OUT − def), পেছনে | সামনে চালানো; return-এর পরে live | ৬৪ |
| Reaching | OUT = gen ∪ (IN − kill), সামনে | শূন্যবার ঘোরার পথ বাদ | ৬৪ |
| LICM | invariant এবং নিরাপদ | ভাগ বা global পড়া সরানো | ৬৬ |
| রং | degree < k হলে simplify; select উল্টো ক্রমে | লেখার পরে live নয় এমন নামে edge | ৭০ |
| Frame | ra −8, s0 −16, slot −24 থেকে; ১৬-এ গোল | ৯ম argument-এ ঋণাত্মক offset | ৭১ |
| GC | mark DFS, Cheney BFS; RC cycle ছাড়ে না | cycle মানেই garbage ভাবা | ৭৫ |
১৫ মিনিটের মিনি-সেট — ঘড়ি ধরে করুন
আটটি ছোট প্রশ্ন, প্রতিটিতে দুই মিনিটের মতো। কাগজ-কলম চলবে, চেকার নয়। ৭–৮ ঠিক হলে প্রস্তুত; ৫–৬ হলে সংশ্লিষ্ট অংশ আবার করুন।
x<=-y-এ কয়টি token?1 - 2 - 3-এর S-expression আর মান?fn ship(w: Int, far: Bool) -> Int { var fee = 40; if w > 5 || far { fee = fee + 30; } return fee; }-এর IR-এ কয়টি basic block?- একই
ship-এর SSA-তে কয়টি φ? sum_to(n)-এর bytecode-এ (৪.৩) n = 5 হলে কয়টি নির্দেশ চলে?- Haat ABI v1-এ দুই parameter আর মোট ছয়টি IR নামের, call-হীন function-এর frame কত byte?
- তিনটি node পরস্পর যুক্ত (ত্রিভুজ), আর কোনো edge নেই: কমপক্ষে কয়টি register?
- Root → A → B, আর C ↔ D (root থেকে পৌঁছানো যায় না): mark-sweep কয়টি মোছে, RC কয়টি?
উত্তরমিনি-সেটের উত্তর আর এক লাইনের কারণ (নিজে করার পরে খুলুন)
1. 4 IDENT, LT_EQ, MINUS, IDENT (reference: a<=-b একই ভাগ)
2. (- (- 1 2) 3) = -4 বাঁ-সংযোগ
3. 5 leader: প্রথম নির্দেশ আর L1–L4 (5.3)
4. 2 B2-তে t2, B4-এ fee (6.2)
5. 75 13n + 10 (4.3)
6. 64 16 + 6 · 8 = 64, আগেই 16-এর গুণিতক (fee, 9.1)
7. 3 ত্রিভুজের প্রতিটি node বাকি দুজনের শত্রু
8. 2 আর 0 C, D পৌঁছানো যায় না; RC-তে তাদের গণনা 1, 1
সবচেয়ে বেশি ভুল হয় ৫ আর ৬-এ। ৫-এ শর্ত n + ১ বার চলে, n বার নয়। ৬-এ অনেকে ra আর s0-এর ১৬ byte ভুলে যান।
আরও গভীরে: এই পাতার register allocator আর SSA-র পদ্ধতি পাঠ্যবইয়ের ক্লাসিক রূপ: φ বসানো Cytron ও সহকর্মীদের ১৯৯১ সালের প্রবন্ধের iterated dominance frontier, রং-করা Chaitin (১৯৮১–৮২) আর Briggs-এর আশাবাদী select. বাস্তব compiler-এ SSA-র ওপর সরাসরি register allocation, linear scan (Poletto–Sarkar, ১৯৯৯) বা আরও জটিল পদ্ধতিও চলে; পর্ব ৭০ আর পর্ব ৬৮ দেখুন। Dataflow analysis কেন কখনো পুরো নিখুঁত হতে পারে না, তার তত্ত্ব গণনার তত্ত্ব · পর্ব ৭৮-এ।
পরীক্ষা ও ইন্টারভিউতে: একই ধরনের প্রশ্ন প্রায়ই আসে। “এই expression-এর three-address code লিখুন” — post-order, প্রতিটি operator-এ একটি temp. “Basic block আর CFG আঁকুন” — আগে leader. “φ কোথায় বসবে” — দুবার লেখা নামের block-গুলোর DF. “Liveness-এর ছক” — শেষ block থেকে পেছনে। “k register-এ রং করুন” — simplify, তারপর উল্টো ক্রমে select. “Activation record আঁকুন” — return address, পুরোনো frame pointer, argument আর local, প্রতিটির offset.
AI-এর যুগে — AI-এর লেখা compiler-উত্তর যাচাই
AI সহকারী এই ধরনের উত্তর দ্রুত লেখে, আর প্রায়ই এই পাতার ফাঁদেই পড়ে: binding power গুলিয়ে precedence বা associativity ভুল করে, ||-কে সাধারণ operator ধরে short-circuit হারায়, φ dominator-এ বসায়, liveness সামনের দিকে চালায়, ভাগ loop-এর বাইরে সরিয়ে “optimize” করে অর্থ বদলায়, ABI-র offset বা register বানিয়ে লেখে, আর এক ভাষার নিয়ম (C-র --, C-র undefined behaviour) Haat-এ চাপায়। প্রতিকার: প্রতিটি উত্তর একটি চলমান implementation-এ মেলান (reference-এর tokens/ast/check/dis/run, পাতার Python block), রূপান্তরের আগে-পরে একই আউটপুট আসে কি না দেখুন, আর edge case (শূন্যবার ঘোরা, শূন্য ভাজক) চালিয়ে দেখুন।
নিজের উত্তর AI-কে দিয়ে পরীক্ষা করানোর একটি কাঠামো:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন। সব তথ্য প্রশ্নের ভেতরেই আছে।
ক্রমএকটি Haat function-কে source থেকে register-এ নামানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Maximal munch-এ token-এ ভাঙা
- Pratt আর recursive descent দিয়ে AST
- নাম-সমাধান আর type check
- Three-address code আর leader থেকে CFG
- Dominance frontier দেখে φ বসিয়ে SSA
- Liveness থেকে interference graph, তারপর রং
(সহজ) Haat-এ let c = a-->b; লিখলে কী হয়?
- Token: IDENT, MINUS, MINUS, GT, IDENT; program চলে
- Lexer error: unexpected character
- Token-এ ভাগ সফল (MINUS, ARROW), parser error দেয়
- a এক কমে b-এর সঙ্গে তুলনা হয়
(সহজ) Pratt parser-এ +-এর lbp ৫০. a + b + c যেন (+ (+ a b) c) হয়, তার জন্য ডান পাশ কোন min_bp দিয়ে পড়তে হয়?
- ৫০
- ৫১
- ০
- ৭০
(মাঝারি) CFG: B0 → B1, B0 → B2, B1 → B2, B2 → B3, B2 → B4, B3 → B4. নাম fee লেখা হয় B0 আর B3-এ, আর B4-এ পড়া হয়। φ কোথায়?
- B2-তে
- B3-তে
- B0-তে
- B4-এ
(মাঝারি) while i < n { let share = 100 / k; s = s + share; i = i + 1; }: share-এর নির্দেশ preheader-এ সরানো যায় না কেন?
- Loop শূন্যবার ঘুরলে নতুন runtime error আসতে পারে
- k loop-এ বদলায়
- share দুবার লেখা হয়
- ভাগ যোগের চেয়ে ধীর
(মাঝারি) IR: x = a + b; y = a * x; z = x - b; t1 = y + z; return t1 (a, b parameter). কোন জোড়া interference graph-এ যুক্ত নয়?
- b–y
- a–x
- a–y
- y–z
(কঠিন) Haat ABI v1 (RISC-V): ১০টি Int parameter-এর function-এ ১০ম parameter callee কোথায় পায়?
- a9 register-এ
- 8(s0)-এ
- −96(s0)-এ
- একটি global variable-এ
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:
মনে রাখুন
- আগে ধাপ, তারপর নিয়ম: প্রশ্নটি token, গাছ, IR, graph না frame-এর, চিনে নিয়ে সেই ধাপের খাতা লিখুন।
- Front end: সবচেয়ে লম্বা বৈধ token; lbp ≥ min_bp হলে বাঁধে, rbp = lbp + ১ মানে বাঁ-সংযোগ।
- IR আর SSA: leader-এর তিন নিয়ম; দুবার লেখা নামের φ তার সংজ্ঞার block-গুলোর DF-এ, argument predecessor-এর ক্রমে।
- Dataflow আর optimization: liveness পেছনে, reaching সামনে; রূপান্তর বৈধ শুধু যদি সব input-এ, শূন্যবার ঘোরা আর শূন্য ভাজকসহ, একই আউটপুট দেয়।
- Back end: লেখার মুহূর্তের liveness থেকে edge, simplify তারপর উল্টো select; frame-এ ra, s0, তারপর slot, ১৬-এ গোল; GC-তে mark DFS, Cheney BFS, RC-র শত্রু cycle.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৮৩ · MCQ প্রশ্নব্যাংক — প্রোগ্রামিং ভাষা ও কম্পাইলারপরবর্তী পর্বপুরো কোর্সের ব্যাখ্যাসহ বহুনির্বাচনী প্রশ্ন।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর ১৪টি মডিউল।
- পর্ব ৬২ · Intermediate representation — three-address code আর control flow graphআবার পড়ুনHaat IR, quadruple, triple আর leader.
- পর্ব ৬৩ · SSA form — phi function আর dominatorআবার পড়ুনDominator, frontier, φ বসানো আর SSA থেকে ফেরা।
- পর্ব ৭০ · Register allocation — graph coloring আর linear scanআবার পড়ুনInterference graph, spill আর coalescing.
- পর্ব ৭১ · Calling convention আর ABI — function call-এর চুক্তিআবার পড়ুনHaat ABI v1-এর frame layout আর call sequence.
- পর্ব ৮৫ · Type derivation আর semantics-এর অনুশীলন — typing rule, inference আর Hoare logicঅনুশীলনDerivation tree, unification আর Hoare logic-এর আদর্শ উত্তর।
- পর্ব ৮৪ · লিখিত ও মৌখিক (ভাইভা) প্রশ্ন — প্রোগ্রামিং ভাষা ও কম্পাইলারঅনুশীলনতুলনামূলক লিখিত প্রশ্ন আর ছোট ভাইভার আদর্শ উত্তর।
- গণনার তত্ত্ব · পর্ব ৮১ · Automaton আর grammar নকশার অনুশীলনপাশের ট্র্যাকDFA, CFG, PDA আর Turing machine নকশার আদর্শ উত্তর।