সরাসরি পর্বে যান
পর্ব ৮২ · ৮৬-এর মধ্যে · মডিউল ১৪

Compiler-এর সমস্যা অনুশীলন — three-address code, activation record, SSA আর register allocation

Practice: Compiler Problems — Tokens, Pratt Traces, Bytecode, Three-Address Code, CFGs, SSA, Dataflow, Optimization, Register Allocation, Stack Frames and GC

Taught in Bangla, this practice page sets exam-style compiler problems, 34 questions in nine groups: tokens and Pratt traces, symbol tables, bytecode and VM stacks, three-address code, quadruples and CFGs, dominators and SSA, liveness, reaching definitions and optimization, loops and LICM, register allocation, stack frames and GC traces. Each has marks, difficulty, a model answer and common mark losses. Eleven in-page Python (Pyodide) checkers verify answers, plus a timed mini-set.

এই পর্বে যা শিখবেন

  • 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-এর ধাপগুলো শেখানো হয়েছে পর্ব ০৫-এ; এখানে প্রতিটি ধাপের খাতা লেখার অনুশীলন।

উত্তরের পাঁচ ধাপ
ধাপ চেনা → ইনপুট নকল → নিয়ম ধরে হিসাব → ছক বা graph-এ লেখা → চালিয়ে মেলানো
  1. ধাপ চেনা: token? গাছ? IR? graph? frame? ভুল ধাপের নিয়ম খাটালে পুরো উত্তর ভুল হয়।
  2. ইনপুট নকল: program বা IR হুবহু খাতায় তুলুন, সারি বা block-এর নম্বরসহ। পরের সব উত্তর এই নম্বর ধরে লেখা হয় (B2.5 মানে block B2-এর পঞ্চম অবস্থানের নির্দেশ, গোনা শূন্য থেকে)।
  3. নিয়ম ধরে হিসাব: binding power, leader-এর তিন নিয়ম, dominance frontier, transfer function, colouring-এর simplify/select: প্রতিটি লাইনের পাশে নিয়মের নাম।
  4. ছক বা graph: liveness-এর ছক, interference graph, frame-এর offset: পরীক্ষক এগুলোতেই নম্বর দেন।
  5. মেলানো: Haat হলে reference-এর tokens, ast, check, dis, run; IR হলে পাতার Python block. আগের আর পরের program একই আউটপুট দিলে তবেই রূপান্তর গ্রহণযোগ্য।

ছবি ৮২.১ — Pipeline-এর কোন ধাপে কোন ধরনের প্রশ্ন

বাঁয়ে ধাপ, ডানে সেই ধাপের খাতা আর এই পাতার অংশ

Compiler pipeline stages and the kinds of exam problems at each stage LexerParserSemanticBytecode, VMIR আর CFGSSADataflow, optLoopBack end, GC token, maximal munchঅংশ ২ Pratt trace, S-expressionঅংশ ২ symbol table, checkঅংশ ৩ dis listing, VM stackঅংশ ৪ TAC, quadruple, CFGঅংশ ৫ dominator, DF, φঅংশ ৬ liveness, reaching, foldঅংশ ৭ natural loop, LICMঅংশ ৮ register রং, frame, GCঅংশ ৯ প্রতিটি রূপান্তরের পরে: চালিয়ে আউটপুট মেলান
অংশপ্রশ্নের ধরনমূল পর্বপ্রশ্ন
২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; — ৫ নম্বর (সহজ)
  1. (ক) Maximal munch: a, তারপর - (কারণ -- নেই), তারপর -> একটি ARROW, তারপর b. Lexer খুশি, parser নয়: --এর ডান পাশে expression চাই, এসেছে ->. সত্যিকারের run: 5:11: error: expected expression.
  2. (খ) একা & কোনো token নয় (README-এর spec decision ২): 1:11: error: unexpected character '&'.
  3. (গ) Haat-এ শুধু \" \\ \n escape: 1:12: error: unknown escape sequence '\t'.
  4. (ঘ) 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)).

min_bp শুরুতে 0 · rbp = lbp + 1
পড়া token
সিদ্ধান্ত
এ পর্যন্ত গাছ
  1. প্রথম বিয়োগ। a prefix অবস্থানে পড়া হলো। --এর lbp ৫০ ≥ ০, তাই সে a-কে বাঁ সন্তান করে; ডান পাশ পড়া শুরু হয় min_bp ৫১ দিয়ে।
  2. বাঁ-সংযোগ আর গুণ। ডান পাশে b-এর পরে আবার -: ৫০ < ৫১, তাই থামে, গাছ (- a b). বাইরের স্তরে একই - ৫০ ≥ ০, বাঁধে। এবার ডানে c-এর পরে *: ৬০ ≥ ৫১, তাই গুণ আগে বাঁধে।
  3. তুলনা। 2-এর পরে >=: গুণের ভেতরে ৪০ < ৬১, বিয়োগের ভেতরে ৪০ < ৫১, দুই স্তরই থামে। সবচেয়ে বাইরের স্তরে ৪০ ≥ ০, বাঁধে; ডান পাশ min_bp ৪১.
  4. &&. x-এর পরে &&: ২০ < ৪১, তুলনার ডান পাশ শেষ। বাইরে ২০ ≥ ০, বাঁধে।
  5. শেষ। ok পড়া হলো, আর কোনো operator নেই। গোড়া &&: সবচেয়ে কম binding power-এর operator-ই গাছের মাথায় যায়। মোট ৯টি তুলনা।
২.৪S-expression লিখুন, বা error বলুন: (ক) -a * b + c % 3 == x || !ok (খ) a < b == c < d (গ) a < b < c (লাইন ৪, প্রথম < কলাম ১১-এ, দ্বিতীয়টি ১৩-এ)। — ৫ নম্বর (মাঝারি)
  1. (ক) Prefix --এর rbp ৭০, তাই সে শুধু a নেয়: (|| (== (+ (* (- a) b) (% c 3)) x) (! ok)).
  2. (খ) আলাদা স্তরের তুলনা মেশানো চলে (decision ১০): (== (< a b) (< c d)); a, b, c, d = 1, 2, 3, 4 হলে true.
  3. (গ) একই স্তরের তুলনা পরপর: 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.

  1. fn: function ঘোষণা fn name(…), আবার anonymous function-এর expression statement fn(…) …;. Reference parser একটি token বেশি দেখে: fn-এর পরে IDENT হলে ঘোষণা (দুই token-এর lookahead).
  2. IDENT: assignment x = e; আর expression statement x + 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'
  1. লাইন ৫: একই scope-এ আবার ঘোষণা (decision ১৫); shadowing চলে শুধু ভেতরের block-এ।
  2. লাইন ৭: block-টি নিজেই cut ঘোষণা করে, তাই ঘোষণার আগের ব্যবহার error, বাইরে কোনো cut থাকলেও (decision ১৬)।
  3. লাইন ১০: 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 করে।

শুরুতে slot = [800, false, –], stack = [ ]
নির্দেশ
stack (শেষে)
slot
চলা নির্দেশ
  1. t = 0. Constant #0 stack-এ, তারপর slot 2-এ। Stack আবার খালি।
  2. amount > 500. 800 আর 500 ঢোকে, GT দুটি তুলে true রাখে। JUMP_IF_FALSE 9 true তুলে নেয়, লাফ দেয় না।
  3. !vip. false ঢোকে, NOT তাকে true করে। এই true-ই &&-এর ফল, তাই JUMP 10 constant false-এর সারি (৯) ডিঙিয়ে যায়।
  4. if-এর শর্ত। ১০-এ JUMP_IF_FALSE 15 true তুলে নেয়; then-অংশে ঢোকা।
  5. t = amount / 20. 800 / 20 = 40, slot 2-এ রাখা।
  6. return t. 40 stack-এ, RETURN frame শেষ করে, মানটি 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 পড়ে না? — ১০ নম্বর (মাঝারি)
blocklive-inlive-out
B0n ratei n p rate
B1i n p ratei n p rate
B2i n p ratei n p rate
B3i n p ratei n p rate
B4i n p ratei n p rate
B5p—

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 কী? — ১০ নম্বর (মাঝারি)
blockreaching-in (i, p)
B0—
B1, B2, B5i@B0.0 i@B4.1 p@B0.1 p@B2.5 p@B3.1
B3i@B0.0 i@B4.1 p@B2.5
B4i@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 থেকে উল্টো ক্রমে নিতে হয়।

Edge: a–b, a–x, b–x, b–y, x–y, y–z · register r0, r1, r2
কাজ
degree বা stack
রং
  1. শুরু। ছয়টি node. b, x, y-এর degree ৩, k-এর সমান, তাই এরা এখনই সরতে পারে না।
  2. simplify a. a-এর degree ২ < ৩: সরিয়ে stack-এ। তার প্রতিবেশী b আর x-এর degree এক করে কমে ২।
  3. বাকিরা। এখন সবাই < ৩: b, x, y, z, t1 পরপর stack-এ। কোনো spill-প্রার্থী লাগেনি।
  4. select শুরু। শেষে ঢোকা আগে বেরোয়: t1 r0 (প্রতিবেশী নেই), z r0 (y এখনো রঙহীন), y r1 (প্রতিবেশী z r0).
  5. select শেষ। x: প্রতিবেশী y r1 ⇒ r0. b: x r0, y r1 ⇒ r2. a: b r2, x r0 ⇒ r1. তিন রঙে সম্পূর্ণ।
  6. 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-এর আকার কত? — ১০ নম্বর (কঠিন)
  1. 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 = ১২০ → ১২৮.
  2. Callee-র দিক: sum10-এর s0 = caller-এর sp, তাই i 0(s0)-এ, j 8(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 কী মুক্ত করে, কী পারে না? — ১০ নম্বর (মাঝারি–কঠিন)
  1. (ক) A 2 (cart, C), B 2 (A, H), C 1, D 1, E 2, F 1, G 1, H 0.
  2. (খ) 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.
  3. (গ) 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 ছোঁয়াই হয়নি।
  4. (ঘ) 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-- বা ->-এর ভাগ ভুল৪৬
Prattlbp ≥ min_bp হলে বাঁধে; rbp = lbp + ১rbp = lbp, ফলে ডান-সংযোগ৪৮
নাম-সমাধানভেতরের block আগে; slot ঘোষণার ক্রমেscope শেষের পরেও ভেতরের নাম ধরা৫১
Bytecodejump-এর লক্ষ্য নির্দেশের নম্বরJUMP_IF_FALSE-এর পরে শর্ত stack-এ রাখা৫৮, ৫৯
Leaderপ্রথম, লক্ষ্য, jump-এর পরেরটিjump-এর লক্ষ্যকে আগের block-এ রাখা৬২
φসংজ্ঞার block-গুলোর iterated DF, live হলেpredecessor-এর বদলে dominator লেখা৬৩
LivenessIN = use ∪ (OUT − def), পেছনেসামনে চালানো; return-এর পরে live৬৪
ReachingOUT = gen ∪ (IN − kill), সামনেশূন্যবার ঘোরার পথ বাদ৬৪
LICMinvariant এবং নিরাপদভাগ বা global পড়া সরানো৬৬
রংdegree < k হলে simplify; select উল্টো ক্রমেলেখার পরে live নয় এমন নামে edge৭০
Framera −8, s0 −16, slot −24 থেকে; ১৬-এ গোল৯ম argument-এ ঋণাত্মক offset৭১
GCmark DFS, Cheney BFS; RC cycle ছাড়ে নাcycle মানেই garbage ভাবা৭৫

১৫ মিনিটের মিনি-সেট — ঘড়ি ধরে করুন

আটটি ছোট প্রশ্ন, প্রতিটিতে দুই মিনিটের মতো। কাগজ-কলম চলবে, চেকার নয়। ৭–৮ ঠিক হলে প্রস্তুত; ৫–৬ হলে সংশ্লিষ্ট অংশ আবার করুন।

  1. x<=-y-এ কয়টি token?
  2. 1 - 2 - 3-এর S-expression আর মান?
  3. fn ship(w: Int, far: Bool) -> Int { var fee = 40; if w > 5 || far { fee = fee + 30; } return fee; }-এর IR-এ কয়টি basic block?
  4. একই ship-এর SSA-তে কয়টি φ?
  5. sum_to(n)-এর bytecode-এ (৪.৩) n = 5 হলে কয়টি নির্দেশ চলে?
  6. Haat ABI v1-এ দুই parameter আর মোট ছয়টি IR নামের, call-হীন function-এর frame কত byte?
  7. তিনটি node পরস্পর যুক্ত (ত্রিভুজ), আর কোনো edge নেই: কমপক্ষে কয়টি register?
  8. 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-কে দিয়ে পরীক্ষা করানোর একটি কাঠামো:

তুমি compiler design-এর একজন কড়া পরীক্ষক। নিচে একটি প্রশ্ন, প্রশ্নে দেওয়া রীতি (IR-এর format, binding power-এর ছক, ABI-র নিয়ম) আর আমার উত্তর দিলাম। [প্রশ্ন] [রীতি] [আমার উত্তর — প্রতিটি লাইন নম্বর দিয়ে] ১. শুধু প্রশ্নে দেওয়া রীতি ব্যবহার করো; অন্য compiler বা ভাষার নিয়ম চাপিয়ো না। ২. প্রতিটি লাইন কোন নিয়মে এসেছে বলো (leader-এর কোন নিয়ম, কোন DF, কোন transfer function), আর কোন লাইন ভুল, নম্বর ধরে দেখাও। ৩. কোনো রূপান্তর (optimization, SSA থেকে ফেরা, register বসানো) অর্থ বদলায় কি না, একটি ছোট input দিয়ে হাতে চালিয়ে দেখাও। ৪. শূন্যবার ঘোরা loop আর শূন্য ভাজকের case আলাদা করে ভাবো। ৫. নম্বর-ভাগ বানিয়ে নম্বর দাও, পুরো উত্তর নিজে লিখে দিও না। নিশ্চিত না হলে "নিশ্চিত নই" লেখো।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন। সব তথ্য প্রশ্নের ভেতরেই আছে।

ক্রমএকটি Haat function-কে source থেকে register-এ নামানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Maximal munch-এ token-এ ভাঙা
  2. Pratt আর recursive descent দিয়ে AST
  3. নাম-সমাধান আর type check
  4. Three-address code আর leader থেকে CFG
  5. Dominance frontier দেখে φ বসিয়ে SSA
  6. 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-এ

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:

মনে রাখুন

  1. আগে ধাপ, তারপর নিয়ম: প্রশ্নটি token, গাছ, IR, graph না frame-এর, চিনে নিয়ে সেই ধাপের খাতা লিখুন।
  2. Front end: সবচেয়ে লম্বা বৈধ token; lbp ≥ min_bp হলে বাঁধে, rbp = lbp + ১ মানে বাঁ-সংযোগ।
  3. IR আর SSA: leader-এর তিন নিয়ম; দুবার লেখা নামের φ তার সংজ্ঞার block-গুলোর DF-এ, argument predecessor-এর ক্রমে।
  4. Dataflow আর optimization: liveness পেছনে, reaching সামনে; রূপান্তর বৈধ শুধু যদি সব input-এ, শূন্যবার ঘোরা আর শূন্য ভাজকসহ, একই আউটপুট দেয়।
  5. Back end: লেখার মুহূর্তের liveness থেকে edge, simplify তারপর উল্টো select; frame-এ ra, s0, তারপর slot, ১৬-এ গোল; GC-তে mark DFS, Cheney BFS, RC-র শত্রু cycle.

পরের পর্বে: পর্ব ৮৩ “MCQ প্রশ্নব্যাংক — প্রোগ্রামিং ভাষা ও কম্পাইলার”: পুরো কোর্সের তেরোটি মডিউল থেকে ব্যাখ্যাসহ বহুনির্বাচনী প্রশ্ন, আর ঘড়ি ধরে নিজেকে যাচাইয়ের সুযোগ।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান