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

Dataflow analysis — liveness, reaching definition আর fixpoint

Dataflow Analysis — Liveness, Reaching Definitions and Fixpoints

Taught in Bangla, this lesson builds a general dataflow framework from a lattice, a meet operator, transfer functions and a direction, and solves it with a worklist algorithm to a fixpoint. It applies one solver to liveness, dead stores, reaching definitions with use-def chains, and the must-analyses available expressions and very busy expressions. It compares worklist with round-robin iteration, discusses precision versus soundness, checks claims against IR interpreter traces and runs Clang's static analyzer.

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

  • Dataflow analysis-এর কাঠামো: lattice, meet, transfer function, দিক, may বনাম must
  • Worklist অ্যালগরিদম, কেন এটি থামে, আর একটি সাধারণ solver যা পর্ব ৬৫, ৬৬ আর ৭০ হুবহু ব্যবহার করবে
  • Liveness, dead store, reaching definitions আর use-def chain, হাতে আর কোডে, পরীক্ষার ধাঁচে টেবিলসহ
  • Available expressions, very busy expressions আর constant-এর lattice: পরের পর্বের optimization-এর ভিত্তি
  • Precision বনাম soundness: বিশ্লেষণ কোন দিকে ভুল করতে পারে, আর চালিয়ে দেখে কীভাবে তা যাচাই করবেন

১ · একটি প্রশ্ন, সব পথে — dataflow analysis কী জানতে চায়

রান্নাঘরের তাকের কথা ভাবুন। সপ্তাহের রান্নার রেসিপিগুলো সামনে রেখে আপনি জানতে চান: কোন মসলা এখন তাকে রাখা দরকার? উত্তর সহজ নিয়মে আসে: যে মসলা সামনের কোনো রেসিপিতে লাগবে, আর তার আগে নতুন প্যাকেট কেনা হবে না, সেটি রাখতে হবে। বাকিগুলো সরানো যায়। লক্ষ করুন, প্রশ্নটি ভবিষ্যৎ নিয়ে, আর উত্তর পেতে আপনি রেসিপির তালিকা পেছন থেকে পড়েন। Compiler-এর কাছে এই প্রশ্নের নাম liveness: একটি variable এই বিন্দুতে live, যদি এখান থেকে কোনো পথে তার বর্তমান মান পড়া হয়, তার আগে নতুন করে লেখা ছাড়াই।

এমন প্রশ্ন compiler-এ অনেক। “এই x-এর মান কোন কোন assignment থেকে আসতে পারে?” “qty * unit কি এখানে আগেই হিসাব করা আছে?” “এই variable কি এখানে সবসময় 60?” প্রতিটির উত্তর program-এর একটি বিন্দু নিয়ে, আর প্রতিটির জন্য দেখতে হয় সেখানে পৌঁছানোর বা সেখান থেকে বেরোনোর সব পথ। পথগুলো আসে পর্ব ৬২-এর control flow graph থেকে, তাই এই ধরনের বিশ্লেষণের নাম dataflow analysis: তথ্য CFG-র edge ধরে “বয়ে” যায়।

প্রায় প্রতিটি optimization এখান থেকে শুরু: register allocation (পর্ব ৭০) জানতে চায় কোন দুটি মান একসঙ্গে live, dead code elimination (পর্ব ৬৫) খোঁজে এমন লেখা যার মান কেউ পড়ে না, আর “variable set but not used” ধরনের warning-ও একই হিসাব।

পর্ব ৫৪-এ এর হালকা রূপ দেখেছেন: AST-এর ওপর definite assignment, আর unused variable-এর check, যা শুধু গুনেছে একটি নাম কতবার পড়া হয়। সেখানেই ফাঁকটি ধরা পড়েছিল: tries = tries + 1;-এ tries একবার পড়া হয়, তাই গোনা চুপ, অথচ সেই মান কোনো কাজে লাগে না। এই পর্ব কাজটি সাধারণ করে: CFG-র ওপর, loop-সহ, যেকোনো প্রশ্নের জন্য একটি কাঠামো আর একটি solver. Haat IR, build_cfg আর run_ir পর্ব ৬২-এর কোড, হুবহু; নতুন কোড আলাদা ফাইল haat_dfa.py-তে, যা পর্ব ৬৫, ৬৬ আর ৭০ হুবহু ব্যবহার করবে।

আরেকটি তুলনা — পোস্ট অফিসের ঠিকানা: আপনার চাচা গত বছর দুবার বাসা বদলেছেন। কোন ঠিকানা-বদলের খবর আজ এই ডাকঘরে পৌঁছাতে পারে, তা নির্ভর করে খবরটি কোন পথে এসেছে তার ওপর। এটিই reaching definitions: একটি assignment একটি বিন্দুতে পৌঁছায়, যদি মাঝে একই নামে নতুন কিছু লেখা হয়নি এমন একটি পথ থাকে।

২ · কাঠামো — lattice, meet, transfer function আর দিক

সব dataflow প্রশ্নের একটি সাধারণ গড়ন আছে, যাকে বলে monotone framework. চারটি জিনিস ঠিক করলেই একটি বিশ্লেষণ সম্পূর্ণ:

সংজ্ঞা ৬৪.১ — একটি dataflow প্রশ্নের চার উপাদান
  1. মানের জগৎ L: প্রতিটি বিন্দুতে যে তথ্য রাখা হয়, যেমন “live নামের set”. L একটি lattice, অর্থাৎ একটি partial order ⊑ যেখানে দুটি উপাদানের meet থাকে।
  2. Meet ⊓: দুটি পথ মিললে তথ্য মেলানোর নিয়ম। “কোনো পথে সত্য হলেই চলবে” প্রশ্নে ⊓ = ∪ (may-analysis); “সব পথে সত্য হতে হবে” প্রশ্নে ⊓ = ∩ (must-analysis). ⊤ হলো শুরুর মান, “এখনো কিছু জানা নেই”, আর ⊤ ⊓ x = x.
  3. Transfer function f: প্রতিটি নির্দেশ তথ্যকে কীভাবে বদলায়। f হতে হবে monotone: x ⊑ y হলে f(x) ⊑ f(y). একটি block-এর transfer function তার নির্দেশগুলোর function-এর পরপর প্রয়োগ।
  4. দিক: forward (entry থেকে সামনে, তথ্য অতীত নিয়ে) বা backward (return থেকে পেছনে, তথ্য ভবিষ্যৎ নিয়ে)। শুরুর প্রান্তে একটি boundary মান বসে।

সমীকরণগুলো দুই দিকে প্রায় আয়নার মতো। Forward বিশ্লেষণে block B-এর শুরুর মান তার predecessor-দের শেষের মানের meet, আর শেষের মান B-এর transfer:

IN[B] = ⊓P ∈ pred(B) OUT[P]   ·   OUT[B] = fB(IN[B])   ·   IN[entry] = boundary

Backward বিশ্লেষণে ঠিক উল্টো: OUT[B] = ⊓S ∈ succ(B) IN[S], IN[B] = fB(OUT[B]), আর return-এ শেষ হওয়া block-এর OUT হলো boundary. Loop থাকলে সমীকরণগুলো চক্রাকার: B1-এর মান B2-এর ওপর নির্ভর করে, B2-এরটি আবার B1-এর ওপর। তাই একবার হিসাবে চলে না; সমাধান খুঁজতে হয় একটি fixpoint, যেখানে আর একবার হিসাব করলে কিছুই বদলায় না।

Lattice আর Hasse diagram-এর গণিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫৬-এ, আর fixpoint-এর প্রমাণ গণনার তত্ত্বের পর্ব ৭৮-এ (উপপাদ্য ২.২)। একটি রীতির পার্থক্য: পর্ব ৭৮ লিখেছে join ⊔ দিয়ে, ⊥ থেকে ওপরে উঠে; compiler-এর পাঠ্যবইয়ে (Aho–Lam–Sethi–Ullman-এর “Dragon book”) প্রচলিত meet ⊓, ⊤ থেকে নিচে নামা। Lattice উল্টে ধরলে দুটি একই জিনিস; এই পর্ব, পর্ব ৫৪-এর মতো, meet-এর রীতি নেয়।

ছবি ৬৪.১ — দুটি lattice: নামের set আর constant-এর মান

ওপরে ⊤ (শুরু), meet সবসময় নিচে নামে

Top: the powerset lattice for liveness with top = empty set and meet = union. Bottom: the constant-propagation lattice with top, all integers in one row, and bottom liveness: ⊓ = ∪ constant-এর ⊓ { } {a} {b} {a,b} ⊤ … -104060 … ⊥ {a} ⊓ {b} = {a,b} 60 ⊓ 60 = 60 · 0 ⊓ 40 = ⊥
ছবি ৬৪.১ — ওপরে liveness-এর lattice, দুটি নাম নিয়ে: শুরুর ⊤ হলো খালি set (“কিছুই live নয় বলে ধরে নিই”), আর meet ∪ মানে যেকোনো পথে live হলেই live; যত নিচে, তত বেশি register আটকে থাকে। নিচে constant propagation-এর lattice (পর্ব ৬৫): ⊤ = “এখনো কোনো মান দেখা যায়নি”, ⊥ = “ধ্রুবক নয়”; সারিটি অসীম হলেও উচ্চতা মাত্র ২।

Lattice-এর উচ্চতা মানে ⊤ থেকে নিচে কঠোরভাবে নামতে থাকা সবচেয়ে লম্বা শিকলের ধাপ-সংখ্যা। n টি নামের set-এর lattice-এর উচ্চতা n; constant-এর lattice-এর উচ্চতা ২। উচ্চতা সসীম হলে প্রতিটি বিন্দুর মান সসীমবার নামতে পারে, তাই বারবার হিসাব একসময় থামে। এই পর্বের চারটি বিশ্লেষণকে একটি টেবিলে রাখা যায়, পরীক্ষায় যা প্রায়ই চাওয়া হয়:

বিশ্লেষণদিক⊓মানব্যবহার
Livenessbackward∪ (may)নামের setregister allocation, dead store
Reaching definitionsforward∪ (may)definition-এর setuse-def chain, constant আর copy propagation
Available expressionsforward∩ (must)expression-এর setcommon subexpression elimination
Very busy expressionsbackward∩ (must)expression-এর setহিসাব আগে তুলে আনা (code hoisting)

প্রথম তিনটি আর প্রায় সব “bit-vector” বিশ্লেষণের transfer একই ছাঁচের: f(X) = gen ∪ (X − kill). Gen হলো নির্দেশটি নতুন যা যোগ করে, kill হলো যা মুছে দেয়। Liveness-এ gen = যে নাম পড়া হয় (use), kill = যে নাম লেখা হয় (def); তাই সমীকরণ IN = use ∪ (OUT − def). এমন gen/kill ছাঁচের function সবসময় monotone, আর আরও একটি গুণ আছে, যা অংশ ৯-এ কাজে লাগবে: f(X ∪ Y) = f(X) ∪ f(Y).

Meet কীভাবে কাজ করে, তা একটি বাজারঘর function-এ দেখুন, constant-এর lattice দিয়ে, যাতে ⊤ আর ⊥ দুটিরই ভূমিকা চোখে পড়ে। মানগুলো লেখকের lab-এ haat_dfa.py-র solver-এ একটি constant-এর Problem বসিয়ে প্রতিটি visit লিখে মেলানো।

1fn ship(express: Bool, n: Int) -> Int {2    var base = 60;3    var extra = 0;4    if express { extra = 40; }5    var i = 0;6    while i < n { i = i + 1; }7    return base + extra + i;8}
Block-এর শেষে মান
block
base
extra
i
  1. শুরু. প্রতিটি block-এর মান ⊤: “এখনো কিছু দেখিনি”. Entry-তে parameter দুটি ⊥, কারণ তাদের মান বাইরে থেকে আসে। Haat IR-এ ৬টি block: B0, B1 (then), B2 (i = 0), B3 (loop-এর শর্ত), B4 (দেহ), B5 (return).
  2. B0. base = const 60, extra = const 0: দুটিই ধ্রুবক। B0-এর কোনো predecessor নেই, তাই meet নেই।
  3. B1, then-শাখা. extra = const 40; base অপরিবর্তিত, 60.
  4. B2, মিলনের বিন্দু. দুটি predecessor, B0 আর B1. base: 60 ⊓ 60 = 60, দুই পথে একই ধ্রুবক। extra: 0 ⊓ 40 = ⊥, দুটি আলাদা ধ্রুবক। তারপর i = const 0.
  5. B3, প্রথমবার. Predecessor B2 আর B4 (পেছনের edge); B4-এর মান এখনো ⊤, আর ⊤ ⊓ x = x, তাই i = 0. এটি আশাবাদী অনুমান। (Visit ৫ ছিল B5, যেখানে meet নেই।)
  6. B4, loop-এর দেহ. i = 0 আর t2 = const 1, তাই i = i + t2-এর ফল 1. B4 বদলেছে, তাই B3 আবার সারিতে।
  7. B3, দ্বিতীয়বার. পেছনের edge থেকে i = 1: 0 ⊓ 1 = ⊥. আশাবাদী অনুমান শোধরানো হলো; এজন্যই একবারের হিসাব যথেষ্ট নয়।
  8. Fixpoint. Visit ৮ (B4) আর ৯ (B5)-এর পরে visit ১০-এ B3 আর বদলায় না, সারি খালি। return-এ base = 60, extra = ⊥, i = ⊥; মোট ১০টি visit. প্রতিটি মান শুধু নিচে নেমেছে, আর উচ্চতা ২ বলে কোনো নাম দুবারের বেশি নামতে পারে না।

৩ · Fixpoint আর worklist — একটি সাধারণ solver

সবচেয়ে সরল সমাধান round-robin: সব block ⊤ দিয়ে শুরু, তারপর রাউন্ডের পর রাউন্ড প্রতিটি block হিসাব, যতক্ষণ না কোনো রাউন্ডে কিছু বদলায়; শেষ রাউন্ডটি শুধু থামার প্রমাণ। ১৯৭৩ সালে Gary Kildall-এর প্রবন্ধে যে iterative পদ্ধতি আসে, তার প্রচলিত রূপের নাম worklist algorithm: একটি সারিতে শুধু সেই block রাখা হয়, যার ইনপুট বদলে থাকতে পারে।

অ্যালগরিদম ৬৪.২ — worklist solver
  1. প্রতিটি block-এর মান ⊤. সব block একটি সারিতে, ভালো একটি ক্রমে: forward-এর জন্য reverse postorder (B0 থেকে DFS করে postorder-এর উল্টো), backward-এর জন্য তার উল্টো।
  2. সারি থেকে একটি block B তুলুন। তার “উৎস” দিকের প্রতিবেশীদের (forward-এ predecessor, backward-এ successor) মানের meet নিন; B যদি শুরুর প্রান্ত হয় (entry বা return-এর block), boundary-ও meet-এ যোগ হয়।
  3. সেই মানে B-এর transfer চালান। ফল আগের চেয়ে আলাদা হলে, “গন্তব্য” দিকের প্রতিবেশীদের যারা সারিতে নেই, তাদের সারির শেষে যোগ করুন।
  4. সারি খালি হলে থামুন: প্রতিটি সমীকরণ এখন সত্য, এটিই fixpoint.

কেন থামে, আর কত কাজে? (প্রমাণের রূপরেখা) ধরুন N টি block, E টি edge, আর lattice-এর উচ্চতা h.

  1. প্রতিটি block-এর ফল শুধু নিচে নামে। ধাপ ১-এ সবাই ⊤; যদি প্রতিবেশীদের মান নিচে নামে, তাদের meet-ও নামে বা একই থাকে, আর f monotone বলে f-এর ফলও নামে বা একই থাকে। (Induction, visit-এর সংখ্যার ওপর।)
  2. তাই প্রতিটি block-এর ফল বড়জোর h বার বদলায়। প্রতিটি বদলে বড়জোর তার গন্তব্য-প্রতিবেশীরা সারিতে ওঠে।
  3. মোট visit ≤ N (শুরুর সারি) + h · E. সারি একসময় খালি হয়। খালি সারির মানে প্রতিটি block-এর ইনপুট শেষবার হিসাবের পরে আর বদলায়নি, তাই সব সমীকরণ সত্য। ∎

পাওয়া উত্তরটি সবচেয়ে বড় fixpoint, অর্থাৎ সবচেয়ে নিখুঁত sound সমাধান (প্রমাণ: গণনার তত্ত্বের পর্ব ৭৮-এর উপপাদ্য ২.২, join-এর রীতিতে)। লেখকের lab-এ সীমাটি পরীক্ষা করা হয়েছে: ৩,০০০টি এলোমেলো program-এর ৯,০০১টি function-এ তিনটি বিশ্লেষণের একটিতেও visit N + h · E ছাড়ায়নি; সবচেয়ে খারাপ function-এও প্রতি block-এ গড়ে প্রায় ৬টি visit.

এবার কোড। নিচে haat_dfa.py-র মূল অংশ: একটি প্রশ্নকে বর্ণনা করার Problem, আর সব প্রশ্নের জন্য একটিই solve. পুরো ফাইল (liveness, reaching definitions, available expressions, points, ud_chains, dead_stores) নিচের ভাঁজে।

@dataclass
class Problem:                    # একটি dataflow প্রশ্ন = lattice + দিক + transfer function
    name: str
    forward: bool                 # True: entry থেকে সামনে; False: return থেকে পেছনে
    meet: object                  # (x, y) -> x ⊓ y: পথ মিললে দুই মান মেলানো
    top: object                   # fn -> ⊤: প্রতিটি block-এর শুরুর মান
    boundary: object              # fn -> entry-র আগে (forward) বা return-এর পরে (backward) মান
    step: object                  # (ins, x, b, i) -> নির্দেশ পেরোনোর পরের মান, বিশ্লেষণের দিকে

# … Solution, rpo, through: পুরো ফাইলে

def solve(p, fn, strategy="worklist"):          # fixpoint: worklist বা round-robin
    P, S = preds(fn), {b: succs(fn, b) for b in fn.blocks}
    src, dst = (P, S) if p.forward else (S, P)  # src: যেখান থেকে মান আসে; dst: বদলালে যাদের জানাতে হয়
    start = (lambda b: b == "B0") if p.forward else (lambda b: not S[b])
    seq = rpo(fn) if p.forward else rpo(fn)[::-1]
    top = p.top(fn); before = {b: top for b in fn.blocks}; after = dict(before)
    visits = 0
    def visit(b):                 # meet নিয়ে transfer; ফল বদলাল কি না ফেরত দেয়
        nonlocal visits; visits += 1
        x = p.boundary(fn) if start(b) else top
        for q in src[b]: x = p.meet(x, after[q])
        before[b], y = x, through(p, fn, b, x)
        changed = y != after[b]; after[b] = y
        return changed
    if strategy == "round-robin":               # প্রতিটি রাউন্ডে সব block, কিছু না বদলানো পর্যন্ত
        while any([visit(b) for b in seq]): pass
    else:                                       # শুধু যার ইনপুট বদলেছে, সে আবার সারিতে
        work, queued = deque(seq), set(seq)
        while work:
            b = work.popleft(); queued.discard(b)
            if visit(b):
                for s in dst[b]:
                    if s not in queued: work.append(s); queued.add(s)
    return Solution(before, after, visits) if p.forward else Solution(after, before, visits)
সহায়ক module haat_dfa.py পুরোটা দেখুন (এই পর্বের সব নতুন কোড; পর্ব ৬৫, ৬৬, ৭০ এটি হুবহু নেবে)
# haat_dfa.py — পর্ব ৬৪: Haat IR-এর CFG-র ওপর সাধারণ dataflow framework, liveness আর reaching definitions.
# পর্ব ৬৫, ৬৬ আর ৭০ এই ফাইলটি হুবহু ব্যবহার করে। লাগে শুধু পর্ব ৬২-এর haat_ir.py (build_cfg-এর non-SSA CFG).
# Global (@x) memory-তে থাকে আর call তাকে বদলাতে পারে; তাই এখানকার বিশ্লেষণ শুধু local নাম (variable, temp) দেখে।
from collections import deque
from dataclasses import dataclass
from haat_ir import *

def defs(ins): return [ins.dst] if ins.dst and ins.dst[0] != "@" else []   # নির্দেশটি যে local নাম লেখে
def uses(ins): return [x for x in ins.args if x[0] != "@"]                    # যে local নাম পড়ে

@dataclass
class Problem:                    # একটি dataflow প্রশ্ন = lattice + দিক + transfer function
    name: str
    forward: bool                 # True: entry থেকে সামনে; False: return থেকে পেছনে
    meet: object                  # (x, y) -> x ⊓ y: পথ মিললে দুই মান মেলানো
    top: object                   # fn -> ⊤: প্রতিটি block-এর শুরুর মান
    boundary: object              # fn -> entry-র আগে (forward) বা return-এর পরে (backward) মান
    step: object                  # (ins, x, b, i) -> নির্দেশ পেরোনোর পরের মান, বিশ্লেষণের দিকে

@dataclass
class Solution:
    IN: dict                      # block -> block-এর শুরুতে মান (program-এর ক্রমে)
    OUT: dict                     # block -> block-এর শেষে মান
    visits: int                   # কতবার একটি block-এর transfer হিসাব হলো

def rpo(fn):                      # reverse postorder: B0 থেকে DFS; forward বিশ্লেষণের ভালো ক্রম
    seen, post, stack = {"B0"}, [], [("B0", iter(succs(fn, "B0")))]
    while stack:
        b, it = stack[-1]
        s = next((s for s in it if s not in seen), None)
        if s is None: post.append(b); stack.pop()
        else: seen.add(s); stack.append((s, iter(succs(fn, s))))
    return post[::-1] + [b for b in fn.blocks if b not in seen]

def through(p, fn, b, x):         # block-এর transfer f_B: সব নির্দেশ পরপর, বিশ্লেষণের দিকে
    body = fn.blocks[b]
    for i in (range(len(body)) if p.forward else range(len(body) - 1, -1, -1)):
        x = p.step(body[i], x, b, i)
    return x

def solve(p, fn, strategy="worklist"):          # fixpoint: worklist বা round-robin
    P, S = preds(fn), {b: succs(fn, b) for b in fn.blocks}
    src, dst = (P, S) if p.forward else (S, P)  # src: যেখান থেকে মান আসে; dst: বদলালে যাদের জানাতে হয়
    start = (lambda b: b == "B0") if p.forward else (lambda b: not S[b])
    seq = rpo(fn) if p.forward else rpo(fn)[::-1]
    top = p.top(fn); before = {b: top for b in fn.blocks}; after = dict(before)
    visits = 0
    def visit(b):                 # meet নিয়ে transfer; ফল বদলাল কি না ফেরত দেয়
        nonlocal visits; visits += 1
        x = p.boundary(fn) if start(b) else top
        for q in src[b]: x = p.meet(x, after[q])
        before[b], y = x, through(p, fn, b, x)
        changed = y != after[b]; after[b] = y
        return changed
    if strategy == "round-robin":               # প্রতিটি রাউন্ডে সব block, কিছু না বদলানো পর্যন্ত
        while any([visit(b) for b in seq]): pass
    else:                                       # শুধু যার ইনপুট বদলেছে, সে আবার সারিতে
        work, queued = deque(seq), set(seq)
        while work:
            b = work.popleft(); queued.discard(b)
            if visit(b):
                for s in dst[b]:
                    if s not in queued: work.append(s); queued.add(s)
    return Solution(before, after, visits) if p.forward else Solution(after, before, visits)

def points(p, fn, sol):           # প্রতিটি নির্দেশের আগে আর পরে মান: {(b, i): (আগে, পরে)}, program-এর ক্রমে
    res = {}
    for b, body in fn.blocks.items():
        if p.forward:
            x = sol.IN[b]
            for i, ins in enumerate(body): y = p.step(ins, x, b, i); res[b, i] = (x, y); x = y
        else:
            x = sol.OUT[b]
            for i in range(len(body) - 1, -1, -1): y = p.step(body[i], x, b, i); res[b, i] = (y, x); x = y
    return res

# ---- liveness: backward, may (∪). x live = এখান থেকে কোনো পথে x পড়া হবে, তার আগে নতুন করে লেখা ছাড়াই
LIVENESS = Problem("liveness", False, lambda x, y: x | y, lambda fn: frozenset(), lambda fn: frozenset(),
                   lambda ins, x, b, i: (x - set(defs(ins))) | set(uses(ins)))

# ---- reaching definitions: forward, may (∪). একটি definition = (নাম, "B2.1") বা parameter-এর জন্য (নাম, "in")
def kill_gen(ins, x, b, i):
    d = defs(ins)
    return frozenset(e for e in x if e[0] not in d) | {(v, f"{b}.{i}") for v in d}
REACHING = Problem("reaching definitions", True, lambda x, y: x | y, lambda fn: frozenset(),
                   lambda fn: frozenset((v, "in") for v in fn.params), kill_gen)

# ---- available expressions: forward, must (∩). একটি expression = (op, a) বা (op, a, b)
def expr_of(ins): return (ins.sym, *ins.args) if ins.kind in ("bin", "un") else None
def all_exprs(fn): return frozenset(e for body in fn.blocks.values() for ins in body if (e := expr_of(ins)))
def avail_step(ins, x, b, i):
    e, d = expr_of(ins), set(defs(ins))
    return frozenset(f for f in (x | {e} if e else x) if not d & set(f[1:]))
AVAILABLE = Problem("available expressions", True, lambda x, y: x & y, all_exprs, lambda fn: frozenset(), avail_step)

def analyze(fn, p=LIVENESS, strategy="worklist"):   # সুবিধার জন্য: solve + points একসঙ্গে
    sol = solve(p, fn, strategy)
    return sol, points(p, fn, sol)

def ud_chains(fn):                # use-def chain: {(b, i, নাম): এখানে পৌঁছানো definition-গুলো}
    _, pts = analyze(fn, REACHING)
    return {(b, i, v): frozenset(d for d in pts[b, i][0] if d[0] == v)
            for (b, i) in pts for v in uses(fn.blocks[b][i])}

def dead_stores(fn):              # লেখা হলো, কিন্তু পরের কোনো পথে পড়া হবে না: [(b, i, নাম)]
    _, pts = analyze(fn, LIVENESS)
    return [(b, i, v) for (b, i), (_, after) in sorted(pts.items(), key=lambda kv: (int(kv[0][0][1:]), kv[0][1]))
            for v in defs(fn.blocks[b][i]) if v not in after]

তিনটি নকশা-সিদ্ধান্ত। step নির্দেশ-স্তরের: block-এর transfer through নির্দেশগুলোর ওপর পরপর step চালায়, তাই points প্রতিটি নির্দেশের আগে-পরের মানও দেয়, যা register allocation-এর লাগবে। @x ধরনের global বাদ, কারণ সেগুলো memory-তে আর যেকোনো call সেগুলো বদলাতে পারে (পর্ব ৬৭-এর বিষয়)। আর মানগুলো Python-এর frozenset; বাস্তব compiler bit vector ব্যবহার করে, যেখানে ∪ একটি OR নির্দেশ, কিন্তু অ্যালগরিদম একই।

৪ · Liveness — কোন মান পরে লাগবে

প্রথম বিশ্লেষণ, liveness, এবার পুরো নিয়মে। একটি নাম x একটি বিন্দু p-তে live, যদি p থেকে CFG-তে এমন একটি পথ থাকে যেখানে x পড়া হয়, আর সেই পড়ার আগে পথে x-এ কোনো লেখা নেই। প্রশ্নটি ভবিষ্যৎ নিয়ে, তাই তথ্য বয়ে যায় পেছনের দিকে; আর “কোনো একটি পথে” পড়লেই চলে, তাই meet = ∪.

সমীকরণ ৬৪.৩ — liveness

একটি নির্দেশ s-এর জন্য: use(s) = s যে local নাম পড়ে, def(s) = s যে local নাম লেখে। Block-এর জন্য: use[B] = B-এ লেখার আগেই পড়া নাম, def[B] = B-এ লেখা নাম।

OUT[B] = ⋃S ∈ succ(B) IN[S]   ·   IN[B] = use[B] ∪ (OUT[B] − def[B])   ·   OUT[B] = ∅, যদি B return-এ শেষ হয়

নির্দেশ-স্তরে একই নিয়ম: live-আগে = use(s) ∪ (live-পরে − def(s)). t = t + 1-এর মতো নির্দেশে t একই সঙ্গে use আর def; সমীকরণে প্রথমে def বাদ, তারপর use যোগ, তাই t নির্দেশের আগে live থাকে।

উদাহরণ হিসেবে নিচ্ছি পর্ব ৫৪-এর cart.haat, হুবহু: বাজারঘরের কার্টের মোট দাম, যাতে ইচ্ছা করে কয়েকটি অপ্রয়োজনীয় লেখা রাখা। Reference এটি চালালে ছাপে 360 (সত্যিকারের run).

// বাজারঘর: কার্টের হিসাব
fn cart_total(items: Int, unit: Int, coupon: Str) -> Int {
    let vat = 15;
    var count = 0;
    var subtotal = 0;
    while count < items {
        subtotal = subtotal + unit;
        count = count + 1;
    }
    var note = "new";
    note = "checked";
    var tries = 0;
    tries = tries + 1;
    return subtotal;
}
print(cart_total(3, 120, "NONE"));

cart_total-এর Haat IR-এ চারটি block: B0 (তিনটি let/var), B1 (loop-এর শর্ত), B2 (দেহ) আর B3 (loop-এর পরের সব)। নিচের stepper worklist solver-কে ধাপে ধাপে চালায় (বাঁয়ে প্রতিটি block-এর successor, কোলনের পরে তার use); প্রতিটি মান লেখকের lab-এ solve-এর একটি logging কপি থেকে নেওয়া।

1B0→B1: —2B1→B2,B3: count items3B2→B1: count subtotal unit4B3→return: subtotal
IN[B], আর সারি
সারি
B0
B1
B2
B3
  1. শুরু. প্রতিটি IN আর OUT ⊤, অর্থাৎ খালি set. Backward, তাই সারি reverse postorder-এর উল্টো: B2, B3, B1, B0. ক্রম শুধু গতি বদলায়, উত্তর নয়।
  2. B2. OUT[B2] = IN[B1] = {} (এখনো ⊤)। IN[B2] = use[B2] = {count, subtotal, unit}. বদলেছে; predecessor B1 আগে থেকেই সারিতে।
  3. B3. return-এ শেষ, তাই OUT[B3] = ∅ (boundary), আর IN[B3] = {subtotal}. note আর tries এখানে পড়ার আগেই লেখা হয়, বা পড়াই হয় না।
  4. B1, দুই successor. OUT[B1] = IN[B2] ∪ IN[B3] = {count, subtotal, unit}; IN[B1] = {count, items} ∪ OUT. বদলেছে, তাই B2 আবার সারির শেষে।
  5. B0. B0 count আর subtotal লেখে, তাই IN[B0] = {items, unit}: শুরুতে শুধু দুটি parameter লাগে, coupon কখনো live নয়।
  6. B2 আবার. এবার OUT[B2]-এ items আছে, তাই IN[B2] = {count, items, subtotal, unit}. Loop-এর শিক্ষা: দেহে items পড়া হয় না, কিন্তু পরের রাউন্ডের শর্তে লাগবে, তাই দেহেও live. B1 আবার সারিতে।
  7. B1 আবার, fixpoint. কিছুই বদলায় না, সারি খালি; মোট ৬টি visit. Round-robin-এ লাগে ১২টি: তিন রাউন্ড × চারটি block, শেষ রাউন্ডটি শুধু “কিছু বদলায়নি” প্রমাণ।

ছবি ৬৪.২ — cart_total-এর CFG, প্রতিটি block-এর শুরুতে live নাম

লাল দাগানো নির্দেশ: dead store (অংশ ৫)

CFG of cart_total with live-in sets above each block and dead stores in red IN {items, unit} IN {count, items, subtotal, unit} IN {count, items, subtotal, unit} IN {subtotal} OUT {} B0 vat = const 15 count = const 0 subtotal = const 0 jump B1 B1 t1 = count < items branch t1 B2 B3 B2 subtotal = subtotal + unit t2 = const 1 count = count + t2 jump B1 B3 note = const "new" note = const "checked" tries = const 0 t3 = const 1 tries = tries + t3 return subtotal সত্য back edge
ছবি ৬৪.২ — সবুজ লেখা প্রতিটি block-এর IN (stepper-এর শেষ ধাপ)। একটি block-এর OUT তার successor-দের IN-এর মিলন, যেমন OUT[B1] = IN[B2] ∪ IN[B3]. coupon কোথাও নেই; লাল দাগানো চারটি লেখার মান পরের কোনো পথে পড়া হয় না।

পরীক্ষার খাতায় এই হিসাব হয় block-স্তরে, use/def (gen/kill) টেবিল দিয়ে। নিচের JavaScript ব্লক তাই করে: Haat IR-এর text থেকে use আর def, তারপর round-robin রাউন্ড। CFG বদলে নিজের উদাহরণ চালাতে পারেন; প্রতি লাইনে একটি block থাকে।

// Haat IR-এর CFG (প্রতি লাইনে একটি block) থেকে use/def (gen/kill), তারপর liveness-এর round-robin
const cfg = `B0: vat = const 15; count = const 0; subtotal = const 0; jump B1
B1: t1 = count < items; branch t1 B2 B3
B2: subtotal = subtotal + unit; t2 = const 1; count = count + t2; jump B1
B3: note = const "new"; note = const "checked"; tries = const 0; t3 = const 1; tries = tries + t3; return subtotal`;
const B = {}, order = [];                          // ওপরের CFG বদলে আবার চালান
for (const line of cfg.split("\n")) {
  const [name, body] = line.split(": ", 2); order.push(name);
  B[name] = body.split("; ").map(s => {
    const w = s.replace(/"[^"]*"/g, "S").split(/[\s(),]+/).filter(Boolean);
    const term = ["jump", "branch", "return", "print"].includes(w[0]);
    const reads = (term ? w.slice(1) : w.slice(2)).filter(x => /^[A-Za-z_][\w.]*$/.test(x)
      && !/^(const|call|true|false|S|B\d+)$/.test(x) && !(w[2] === "call" && x === w[3]));
    return { dst: term ? null : w[0], reads, succ: w[0] === "jump" ? [w[1]] : w[0] === "branch" ? w.slice(2) : [] };
  });
}
const set = a => "{" + [...a].sort().join(", ") + "}", use = {}, def = {}, IN = {}, OUT = {};
for (const b of order) {                           // use = block-এ লেখার আগে পড়া; def = block-এ লেখা
  use[b] = new Set(); def[b] = new Set(); IN[b] = new Set(); OUT[b] = new Set();
  for (const i of B[b]) { i.reads.forEach(x => def[b].has(x) || use[b].add(x)); if (i.dst) def[b].add(i.dst); }
  console.log(`${b}  use ${set(use[b])}  def ${set(def[b])}`);
}
for (let round = 1, changed = true; changed; round++) {
  changed = false; console.log(`রাউন্ড ${round}:`);
  for (const b of [...order].reverse()) {           // পেছনের বিশ্লেষণ: শেষের block আগে
    OUT[b] = new Set(B[b].at(-1).succ.flatMap(s => [...IN[s]]));
    const inn = new Set([...use[b], ...[...OUT[b]].filter(x => !def[b].has(x))]);
    const mark = set(inn) !== set(IN[b]) ? "  ← বদলেছে" : "";
    if (mark) { changed = true; IN[b] = inn; }
    console.log(`  ${b} IN ${set(IN[b])}${mark}`);
  }
}

আসল আউটপুট (ব্রাউজারের JavaScript):

B0  use {}  def {count, subtotal, vat}
B1  use {count, items}  def {t1}
B2  use {count, subtotal, unit}  def {count, subtotal, t2}
B3  use {subtotal}  def {note, t3, tries}
রাউন্ড 1:
  B3 IN {subtotal}  ← বদলেছে
  B2 IN {count, subtotal, unit}  ← বদলেছে
  B1 IN {count, items, subtotal, unit}  ← বদলেছে
  B0 IN {items, unit}  ← বদলেছে
রাউন্ড 2:
  B3 IN {subtotal}
  B2 IN {count, items, subtotal, unit}  ← বদলেছে
  B1 IN {count, items, subtotal, unit}
  B0 IN {items, unit}
রাউন্ড 3:
  B3 IN {subtotal}
  B2 IN {count, items, subtotal, unit}
  B1 IN {count, items, subtotal, unit}
  B0 IN {items, unit}

প্রথম চার লাইন use/def টেবিল। B3-এর use শুধু {subtotal}: tries পড়ার আগেই একই block-এ tries = const 0 লেখা। রাউন্ড ২-এ শুধু B2 বদলায় (items যোগ হয়), রাউন্ড ৩-এ কিছুই না। মোট ১২টি block-হিসাব, worklist-এর দ্বিগুণ; উত্তর stepper-এর সঙ্গে হুবহু এক।

এবার একই কাজ haat_dfa.py দিয়ে, নির্দেশ-স্তরে; analyze block-এর Solution আর প্রতিটি নির্দেশের আগে-পরের মান একসঙ্গে দেয়।

# ধাপ ১: cart_total-এর liveness — block-এর IN/OUT, নির্দেশে নির্দেশে, আর dead store
from haat_dfa import *                           # LIVENESS, solve, analyze, dead_stores … (+ haat_ir)
fn = compile_ir(open("cart.haat", encoding="utf-8").read()).funcs["cart_total"]
def s(x): return "{" + ", ".join(sorted(x)) + "}"
sol, pts = analyze(fn, LIVENESS)
for b in fn.blocks:
    print(f"{b}: IN {s(sol.IN[b]):30} OUT {s(sol.OUT[b])}")
print("worklist-এ block দেখা:", sol.visits, "· round-robin-এ:", solve(LIVENESS, fn, "round-robin").visits)
print("B3, নির্দেশে নির্দেশে (পরে live):")
for i, ins in enumerate(fn.blocks["B3"]):
    print(f"  {str(ins):24} {s(pts['B3', i][1])}")
for b, i, v in dead_stores(fn):
    if not is_temp(v): print(f"dead store: {b}.{i}  {fn.blocks[b][i]}")

আসল আউটপুট (ব্রাউজারের Python):

B0: IN {items, unit}                  OUT {count, items, subtotal, unit}
B1: IN {count, items, subtotal, unit} OUT {count, items, subtotal, unit}
B2: IN {count, items, subtotal, unit} OUT {count, items, subtotal, unit}
B3: IN {subtotal}                     OUT {}
worklist-এ block দেখা: 6 · round-robin-এ: 12
B3, নির্দেশে নির্দেশে (পরে live):
  note = const "new"       {subtotal}
  note = const "checked"   {subtotal}
  tries = const 0          {subtotal, tries}
  t3 = const 1             {subtotal, t3, tries}
  tries = tries + t3       {subtotal}
  return subtotal          {}
dead store: B0.0  vat = const 15
dead store: B3.0  note = const "new"
dead store: B3.1  note = const "checked"
dead store: B3.4  tries = tries + t3

Block-স্তরের IN/OUT আর visit-এর সংখ্যা (৬ আর ১২) JavaScript আর stepper-এর সঙ্গে হুবহু মেলে। B3-এর তালিকা শেষ থেকে পড়ুন: tries = tries + t3-এর পরে শুধু subtotal live, অর্থাৎ সদ্য লেখা tries কেউ পড়বে না; tries = const 0-এর পরে tries live, কারণ পরের নির্দেশ পড়ে। শেষ চার লাইন dead_stores-এর ফল (temp বাদ): প্রতিটি এমন লেখা, যার নামটি লেখার ঠিক পরে live নয়।

৫ · Dead store — পর্ব ৫৪-এর check-এর সাধারণ রূপ

একটি dead store হলো এমন লেখা, যার মান পরের কোনো পথে পড়া হয় না; liveness-এর ভাষায়, নির্দেশ s নাম x লেখে আর x ∉ live-পরে(s). পর্ব ৫৪-এর unused variable-এর check প্রতিটি নাম কতবার পড়া হয় গুনেছিল; liveness প্রতিটি লেখা আলাদা করে বিচার করে, পথ ধরে। নিচের stepper B3-কে পেছন থেকে হাঁটে, এক নির্দেশ করে।

1note = const "new"2note = const "checked"3tries = const 04t3 = const 15tries = tries + t36return subtotal
পেছন থেকে হিসাব
live পরে
use / def
live আগে
  1. return subtotal. OUT[B3] = ∅; নির্দেশটি subtotal পড়ে, তাই আগে live = {subtotal}.
  2. tries = tries + t3. পরে live শুধু {subtotal}; নির্দেশটি tries লেখে, কিন্তু tries সেখানে নেই: dead store. তবু এটি tries আর t3 পড়ে, তাই আগে দুটিই live; পর্ব ৫৪-এর গোনা এই পড়াটিকেই “ব্যবহার” ধরে চুপ ছিল।
  3. t3 = const 1. লেখার পরে t3 live, তাই লেখাটি দরকারি।
  4. tries = const 0. পরে tries live, তাই dead store নয়, যদিও এর মান শুধু একটি মৃত লেখায় যায়। এমন নামকে বলে “faint”; ধরতে হলে মৃত লেখা মুছে আবার বিশ্লেষণ লাগে (পর্ব ৬৫)।
  5. note = const "checked". পরে note live নয়: dead store.
  6. note = const "new". পরের নির্দেশই note আবার লেখে, তাই এটিও dead store. গোনা-ভিত্তিক check এই দুটি লেখাকে আলাদা করতে পারে না, liveness পারে। B0-এর vat = const 15 মিলিয়ে মোট চারটি।

এই ফল কি বাস্তব compiler-এর সঙ্গে মেলে? একই function-এর C রূপ (long, আর note একটি const char *) PyPI-র ziglang 0.17.1-এর ভেতরের Clang 22.1.8 দিয়ে দুভাবে দেখা হলো, লেখকের lab-এ সত্যিকারের run. প্রথমে সাধারণ warning (-Wall -Wextra; কোডের লাইন দেখানোর অংশ বাদ):

cart.c:2:10: warning: unused variable 'vat' [-Wunused-variable]
cart.c:9:17: warning: variable 'note' set but not used [-Wunused-but-set-variable]

tries = tries + 1-এ compiler চুপ: পর্ব ৫৪-এর গোনার মতোই, warning-টি নামের স্তরে দেখে। এবার Clang Static Analyzer (--analyze), যার deadcode.DeadStores checker CFG-র ওপর liveness চালায় (zig-এর driver-এর দুটি “argument unused” লাইন বাদ দেওয়া):

~/dfa $ python -m ziglang cc --analyze -S --target=x86_64-linux-gnu cart.c -o cart.out
cart.c:9:17: warning: Value stored to 'note' during its initialization is never read [deadcode.DeadStores]
    9 |     const char *note = "new";
      |                 ^~~~   ~~~~~
cart.c:10:5: warning: Value stored to 'note' is never read [deadcode.DeadStores]
   10 |     note = "checked";
      |     ^      ~~~~~~~~~
cart.c:12:5: warning: Value stored to 'tries' is never read [deadcode.DeadStores]
   12 |     tries = tries + 1;
      |     ^       ~~~~~~~~~
3 warnings generated.

তিনটিই আমাদের dead_stores-এর সঙ্গে হুবহু এক; vat analyzer আলাদা করে বলেনি, কারণ -Wunused-variable সেটি আগেই ধরে। একটি পার্থক্যও আছে: আমাদের বার্তায় line:col নেই, কারণ Haat IR pos রাখে শুধু operator, call আর global-এর নির্দেশে, যেখানে runtime error হতে পারে (পর্ব ৬২-এর নিয়ম); একটি সাধারণ assignment-এর অবস্থান IR-এ পৌঁছায় না।

Dead store মানেই মোছা যায় না। t = call f(a)-এর t মৃত হলেও call-টি থাকতে হবে, কারণ f ছাপতে পারে বা global বদলাতে পারে। t = x / y-এর t মৃত হলেও, y শূন্য হতে পারলে ভাগটি থাকতে হবে, কারণ Haat-এ শূন্য দিয়ে ভাগ একটি runtime error, যা program-এর দেখা যায় এমন আচরণ (সিদ্ধান্ত ২৬; পর্ব ৬২-এর স্থায়ী নিয়ম)। Liveness বলে “মান লাগবে না”; “নির্দেশটি মুছে ফেলা নিরাপদ” বলতে আরও একটি প্রশ্ন লাগে: নির্দেশটির কোনো side effect আছে কি না। পর্ব ৬৫ দুটি প্রশ্ন একসঙ্গে মেলাবে।

পর্ব ৫৪-এর বাকি দুটি pass-ও এই কাঠামোয় বসে। Unreachable code: forward, মান {পৌঁছানো যায়, যায় না}, meet = “বা”; Haat IR-এ উত্তর সবসময় “সব পৌঁছানো যায়”, কারণ পর্ব ৬২-এর lowering মৃত কোড লেখেই না, আর while false-এর মতো ধ্রুবক শর্তের edge বাদ দেওয়া পর্ব ৬৫-এর কাজ। Definite assignment: forward, must (∩), মান “নিশ্চিতভাবে লেখা নাম”; Haat v1-এ প্রতিটি local initializer পায়, তাই প্রশ্নটি শুধু বর্ধিত রূপে ওঠে।

৬ · Reaching definitions আর use-def chain

Haat IR-এ একটি definition মানে একটি local নাম লেখা নির্দেশ, চেনা হয় নাম আর জায়গা দিয়ে, যেমন total@B2.1 (B2-এর ১ নম্বর নির্দেশ, ০ থেকে গোনা); parameter-এর জন্য entry-র আগে একটি কল্পিত qty@in. d একটি বিন্দু p-তে পৌঁছায়, যদি d থেকে p পর্যন্ত এমন পথ থাকে যেখানে d-এর নাম আর লেখা হয়নি।

সমীকরণ ৬৪.৪ — reaching definitions

নির্দেশ s যদি x লেখে: gen(s) = {s-এর definition}, kill(s) = x-এর বাকি সব definition. Block-এর gen = block-এ প্রতিটি নামের শেষ definition; kill = block-এ লেখা নামগুলোর অন্য সব definition.

IN[B] = ⋃P ∈ pred(B) OUT[P]   ·   OUT[B] = gen[B] ∪ (IN[B] − kill[B])   ·   IN[entry] = {p@in : p parameter}

bazar.haat-এর <main> নিন (পর্ব ৬২-এর CFG: B0-এ first, total = const 0, rounds = const 0; B1 শর্ত; B2 দেহ; B3 শেষ)। Temp বাদ দিয়ে Haat-এর নাম পাঁচটি definition: d1 = first@B0.7, d2 = total@B0.9, d3 = rounds@B0.10, d4 = total@B2.1, d5 = rounds@B2.3. পরীক্ষার ধাঁচে gen/kill টেবিল আর fixpoint-এর IN/OUT (লেখকের lab-এ haat_dfa.py দিয়ে হিসাব করা):

blockgenkillINOUT
B0d1, d2, d3d4, d5—d1, d2, d3
B1——d1, d2, d3, d4, d5d1, d2, d3, d4, d5
B2d4, d5d2, d3d1, d2, d3, d4, d5d1, d4, d5
B3——d1, d2, d3, d4, d5d1, d2, d3, d4, d5
1B0: d1, d2, d32B1: t9 = total < t8 (মিলন)3B2: d4, d5 → B14B3: print total, rounds - 1
Definition-এর set
সারি
OUT[B0]
IN[B1]
OUT[B2]
  1. শুরু. সব set ⊤ = খালি; <main>-এর parameter নেই, তাই boundary-ও খালি। Forward, তাই সারি reverse postorder-এ: B0, B1, B3, B2.
  2. B0. gen = {d1, d2, d3}, তাই OUT[B0] = {d1, d2, d3}.
  3. B1, প্রথমবার. Predecessor B0 আর B2; OUT[B2] এখনো খালি, তাই IN[B1] = {d1, d2, d3}. এখন মনে হয় শর্তের total শুধু d2 থেকে, অর্থাৎ সবসময় 0: অসম্পূর্ণ উত্তর।
  4. B3. IN[B3] = {d1, d2, d3}; B3 কিছু লেখে না।
  5. B2, loop-এর দেহ. d4 total-এর পুরোনো d2-কে মুছে দেয় (kill), d5 মুছে দেয় d3. OUT[B2] = {d1, d4, d5}; বদলেছে, তাই B1 আবার সারিতে।
  6. B1, মিলন. IN[B1] = {d1, d2, d3} ∪ {d1, d4, d5}: loop-এর মাথায় total আসতে পারে loop-এর আগের d2 বা আগের রাউন্ডের d4 থেকে, তাই ধ্রুবক নয়। B2 আর B3 সারিতে।
  7. B2 আবার. OUT[B2] একই, কারণ d2 আর d3 আবার মুছে যায়।
  8. B3, fixpoint. IN[B3]-এ পাঁচটিই; মোট ৭টি visit, ওপরের টেবিলের সঙ্গে প্রতিটি set মেলে।

Reaching definitions থেকে আসে একটি ব্যবহারিক তালিকা, use-def chain: প্রতিটি পড়ার জন্য, যে definition-গুলো সেখানে পৌঁছায় আর একই নাম লেখে। haat_dfa.py-র ud_chains(fn) ঠিক এটি দেয়, {(b, i, নাম): definition-এর set} আকারে। একটি পড়ায় একটিই definition পৌঁছালে, আর সেটি x = const 5 হলে, সেখানে x = 5 (constant propagation); সেটি x = y হলে x-এর বদলে y পড়া যায়, যদি মাঝে y বদলায়নি (copy propagation). দুটিই পর্ব ৬৫-এ। পর্ব ৬৩-এর SSA form এই chain নামেই লিখে রাখে, কারণ সেখানে প্রতিটি নামের একটিই definition.

৭ · Must-analysis — available আর very busy expression

এবার must-এর প্রশ্ন। একটি expression a op b একটি বিন্দু p-তে available, যদি entry থেকে p পর্যন্ত প্রতিটি পথে a op b হিসাব হয়েছে আর তার পরে a বা b আর লেখা হয়নি। তখন p-তে আবার হিসাব না করে আগের ফল নেওয়া যায়: এটিই common subexpression elimination-এর ভিত্তি। একটি পথেও না মিললে আগের ফল নেই, তাই meet = ∩.

সমীকরণ ৬৪.৫ — available expressions

নির্দেশ s যদি t = a op b হয়: gen(s) = {a op b}, তারপর kill(s) = যে expression-এর operand t (নিজেরটিও, যেমন i = i + t2).

IN[B] = ⋂P ∈ pred(B) OUT[P]  ·  OUT[B] = gen[B] ∪ (IN[B] − kill[B])  ·  IN[entry] = ∅  ·  ⊤ = সব expression-এর set U

শুরুর মান কেন U? Back edge থেকে প্রথমবার আসা ⊤ যেন ∩-এ কিছু না মোছে, ঠিক যেমন constant-এর stepper-এ ⊤ ⊓ 0 = 0 ছিল। ∅ দিয়ে শুরু করলেও উত্তর sound, কিন্তু loop-এর মাথায় সবসময় ∅ আসে, আর loop-এর ভেতরে কিছুই available বলা যায় না। Entry-র boundary অবশ্য ∅.

Very busy এর আয়না-প্রশ্ন: p থেকে প্রতিটি পথে a op b হিসাব হবে, a বা b বদলানোর আগেই; তাহলে হিসাবটি p-তে আগেভাগে করা যায় (code hoisting). দিক backward, meet ∩. উদাহরণ, বাজারঘরের বিল: সদস্য হলে একটি unit-এর দাম ছাড়।

fn bill(qty: Int, unit: Int, member: Bool) -> Int {
    if member { return qty * unit - unit; }
    return qty * unit;
}

দুই শাখাতেই qty * unit, কিন্তু কোনোটিই অন্যটির আগে নয়: কোথাও available নয়, অথচ শাখার আগে very busy. নিচের ব্লক একই solve-এ চারটি প্রশ্ন চালায়: bazar-এ reaching definitions আর use-def chain, bill-এ available expressions আর একটি নতুন Problem, very busy, যা ছয় লাইনে লেখা। Solver-এ একটি অক্ষরও বদলায় না: এটিই কাঠামোর মূল লাভ।

# ধাপ ২: একই framework, অন্য প্রশ্ন — reaching definitions, available আর very busy expressions
from haat_dfa import *
mod = compile_ir(open("examples/bazar.haat", encoding="utf-8").read())
fn = mod.funcs["<main>"]
def var(x): return sorted(f"{v}@{site}" for v, site in x if not is_temp(v))   # শুধু Haat-এর নাম
sol = solve(REACHING, fn)
for b in fn.blocks: print(f"RD {b} IN:", ", ".join(var(sol.IN[b])) or "—")
print("visits:", sol.visits)
ud = ud_chains(fn)
print("B1.1 `t9 = total < t8`-এ total আসতে পারে:", var(ud["B1", 1, "total"]))
# নতুন প্রশ্ন = নতুন Problem; solve অপরিবর্তিত। Very busy: পেছনে, must (∩)
def vb_step(ins, x, b, i):                       # আগে kill, তারপর gen (পেছনের দিকে)
    d = set(defs(ins)); x = frozenset(f for f in x if not d & set(f[1:]))
    return x | {expr_of(ins)} if expr_of(ins) else x
VERY_BUSY = Problem("very busy expressions", False, lambda x, y: x & y, all_exprs,
                    lambda fn: frozenset(), vb_step)
bill = compile_ir("""fn bill(qty: Int, unit: Int, member: Bool) -> Int {
    if member { return qty * unit - unit; }
    return qty * unit;
}""").funcs["bill"]
print(show_ir(bill))
for p in (AVAILABLE, VERY_BUSY):
    sol = solve(p, bill)
    for b in bill.blocks:
        print(f"{p.name[:9]} {b}: IN", [" ".join(e) for e in sorted(sol.IN[b])],
              "OUT", [" ".join(e) for e in sorted(sol.OUT[b])])

আসল আউটপুট (ব্রাউজারের Python):

RD B0 IN: —
RD B1 IN: first@B0.7, rounds@B0.10, rounds@B2.3, total@B0.9, total@B2.1
RD B2 IN: first@B0.7, rounds@B0.10, rounds@B2.3, total@B0.9, total@B2.1
RD B3 IN: first@B0.7, rounds@B0.10, rounds@B2.3, total@B0.9, total@B2.1
visits: 7
B1.1 `t9 = total < t8`-এ total আসতে পারে: ['total@B0.9', 'total@B2.1']
fn bill(qty, unit, member):
B0:
  branch member B1 B2
B1:
  t1 = qty * unit
  t2 = t1 - unit
  return t2
B2:
  t3 = qty * unit
  return t3
available B0: IN [] OUT []
available B1: IN [] OUT ['* qty unit', '- t1 unit']
available B2: IN [] OUT ['* qty unit']
very busy B0: IN ['* qty unit'] OUT ['* qty unit']
very busy B1: IN ['* qty unit'] OUT []
very busy B2: IN ['* qty unit'] OUT []

প্রথম চার লাইন stepper আর টেবিলের সঙ্গে হুবহু, ৭টি visit. Use-def chain বলে শর্তের total আসতে পারে total@B0.9 (= 0) বা total@B2.1 থেকে, তাই ধ্রুবক নয়। bill-এ available expressions-এ B2-এর IN খালি, কারণ B0 থেকে আসার পথে কোনো গুণ হয়নি; very busy-তে B0-এর OUT-এ * qty unit, কারণ পরের দুই পথেই গুণটি আছে। তাই t = qty * unit শাখার আগে তোলা যায়।

একটি Haat IR-নির্দিষ্ট সীমা: expression চেনা হয় নাম দিয়ে, আর ধ্রুবক আসে নিজের temp-এ, তাই দুই জায়গার p / 10 হয়ে যায় (/, p, t3) আর (/, p, t5), দুটি “আলাদা” expression. মান দিয়ে চেনার কৌশল (value numbering) পর্ব ৬৫-এ এই ফাঁক বন্ধ করবে, সঙ্গে পূর্ণ constant propagation.

পরীক্ষা ও ইন্টারভিউতে: এই প্রশ্নগুলো ঘুরেফিরে আসে।

  • Liveness কেন backward? প্রশ্নটি ভবিষ্যৎ নিয়ে (“পরে পড়া হবে কি”), তাই তথ্য আসে successor থেকে।
  • May আর must-এ meet কী? May-তে ∪, ⊤ = ∅; must-এ ∩, ⊤ = সব উপাদানের set.
  • Reaching definitions-এর সমীকরণ? OUT = gen ∪ (IN − kill), IN = predecessor-দের OUT-এর ∪.
  • Iterative algorithm থামে কেন? Lattice-এর উচ্চতা সসীম আর transfer monotone, তাই প্রতিটি মান সসীমবার নামে।
  • Liveness কোথায় লাগে? Register allocation-এর interference graph আর dead store/dead code খোঁজায়।

৮ · Worklist বনাম round-robin, আর চালিয়ে যাচাই

দুটি প্রশ্ন বাকি: worklist কতটা কাজ বাঁচায়, আর বিশ্লেষণ যে সঠিক তার প্রমাণ কী? বিশ্লেষণ কোনো আউটপুট বদলায় না, তাই পর্ব ৬২-এর মতো আউটপুট মিলিয়ে কিছু প্রমাণ হয় না; দেখতে হবে প্রতিটি দাবি, চলার সময়ের (dynamic) প্রমাণের সঙ্গে। dfa_check.py প্রতিটি block-এর list-কে একটি “গুপ্তচর” subclass দিয়ে মুড়ে দেয়, যা run_ir-এর পড়া প্রতিটি নির্দেশ খাতায় তোলে; haat_ir.py-র এক লাইনও বদলায় না। খাতা থেকে প্রতিটি call-এর frame আলাদা করে তিনটি পরীক্ষা:

  • Liveness: frame-এর চলা নির্দেশ পেছন থেকে হেঁটে “পরে, লেখার আগে সত্যিই পড়া হয়েছে” নামের set; এটি static live-এর ভেতরে থাকতেই হবে।
  • Reaching definitions: সামনে থেকে হেঁটে প্রতিটি নামের শেষ লেখা; সেটি static set-এ থাকতে হবে।
  • Available expressions: উল্টো দিক, কারণ এটি must: static “available” বলা প্রতিটি expression এই run-এ সত্যিই হিসাব হয়ে থাকতে হবে।
সহায়ক module dfa_check.py পুরোটা দেখুন (trace আর তিনটি পরীক্ষা)
# dfa_check.py — পর্ব ৬৪: বিশ্লেষণের দাবি চালানোর সত্যিকারের trace-এর সঙ্গে মেলানো (soundness-এর পরীক্ষা).
# haat_ir.py আর haat_dfa.py অপরিবর্তিত; run_ir কোন নির্দেশ পড়ছে, তা একটি list-এর subclass চুপচাপ খাতায় লেখে।
from collections import Counter
from haat_dfa import *

class Spy(list):                  # একটি block-এর নির্দেশ; run_ir যেটি পড়ে (fn, b, i) খাতায় যায়
    def __init__(self, body, log, key): super().__init__(body); self.log, self.key = log, key
    def __getitem__(self, i):
        if isinstance(i, int): self.log.append((*self.key, i))
        return super().__getitem__(i)

def trace(mod):                   # চালিয়ে প্রতিটি frame-এর চলা নির্দেশ: [(fn-এর নাম, [(b, i), …]), …]
    log, frames, stack = [], [], []
    for f in mod.funcs.values(): f.blocks = {b: Spy(body, log, (f.name, b)) for b, body in f.blocks.items()}
    try: run_ir(mod, out=lambda s: None)
    except HaatError: pass        # runtime error: trace সেখানেই শেষ
    for f in mod.funcs.values(): f.blocks = {b: list(body) for b, body in f.blocks.items()}
    for name, b, i in log:
        if not stack: stack.append((name, [])); frames.append(stack[-1])
        stack[-1][1].append((b, i)); kind = mod.funcs[name].blocks[b][i].kind
        if kind == "call":
            stack.append((mod.funcs[name].blocks[b][i].sym, [])); frames.append(stack[-1])
        elif kind == "return": stack.pop()
    return frames

def check(mod, c=None):           # তিন বিশ্লেষণের প্রতিটি দাবি trace-এর সঙ্গে; ভুল (miss) হতে হবে ০
    c = c if c is not None else Counter()
    P = {f: {p.name: analyze(fn, p)[1] for p in (LIVENESS, REACHING, AVAILABLE)} for f, fn in mod.funcs.items()}
    seen = {}                     # (fn, b, i, বিশ্লেষণ) -> সব run মিলিয়ে দেখা মান
    for name, seq in trace(mod):
        fn, A = mod.funcs[name], P[name]
        later = set()             # liveness: পেছন থেকে, “এই frame-এ পরে, লেখার আগে পড়া হবে”
        for b, i in reversed(seq):
            ins = fn.blocks[b][i]; later = (later - set(defs(ins))) | set(uses(ins))
            c["live miss"] += len(later - A["liveness"][b, i][0])
            seen.setdefault((name, b, i, "live"), set()).update(later)
        last, have = {v: (v, "in") for v in fn.params}, frozenset()
        for b, i in seq:          # reaching: প্রতিটি নামের শেষ লেখা; available: হিসাব হয়েছে, operand বদলায়নি
            ins = fn.blocks[b][i]; c["points"] += 1
            c["rd miss"] += sum(d not in A["reaching definitions"][b, i][0] for d in last.values())
            c["av miss"] += len(A["available expressions"][b, i][0] - have)
            seen.setdefault((name, b, i, "rd"), set()).update(last.values())
            for v in defs(ins): last[v] = (v, f"{b}.{i}")
            have = avail_step(ins, have, b, i)
    for (name, b, i, k), got in seen.items():   # নির্ভুলতা: static দাবির কতটা সত্যিই দেখা গেল
        claim = P[name]["liveness" if k == "live" else "reaching definitions"][b, i][0]
        c[k + " claimed"] += len(claim); c[k + " observed"] += len(got)
    return c
# ধাপ ৩: worklist বনাম round-robin, আর প্রতিটি দাবি চালিয়ে যাচাই (soundness)
from collections import Counter
from dfa_check import *                          # trace, check (+ haat_dfa, haat_ir)
from haat_gen import gen_program                 # পর্ব ৬২-এর এলোমেলো program
names = ["bazar", "mutual", "shadowing", "shortcircuit", "strings", "loops", "err_divzero", "counter"]
srcs = [open(f"examples/{n}.haat", encoding="utf-8").read() for n in names]
srcs += [gen_program(s) for s in range(100)]     # seed 0–99
c, visits, same, skipped = Counter(), Counter(), 0, 0
for src in srcs:
    try: mod = compile_ir(src)
    except Unsupported: skipped += 1; continue   # closure: Haat IR v1-এর বাইরে
    check(mod, c)
    for fn in mod.funcs.values():
        for p in (LIVENESS, REACHING, AVAILABLE):
            w, r = solve(p, fn), solve(p, fn, "round-robin")
            same += w.IN == r.IN and w.OUT == r.OUT
            visits[p.name] += w.visits; visits[p.name, "rr"] += r.visits
print(f"program: {len(srcs) - skipped} (বাদ {skipped}), চলা নির্দেশ: {c['points']:,}")
print("দুই solver-এর উত্তর এক:", same, "বার")
for p in (LIVENESS, REACHING, AVAILABLE):
    print(f"  {p.name}: worklist {visits[p.name]:,} · round-robin {visits[p.name, 'rr']:,}")
print("ভুল দাবি — live:", c["live miss"], "· reaching:", c["rd miss"], "· available:", c["av miss"])
for k in ("live", "rd"):
    print(f"{k}: দাবি {c[k + ' claimed']:,}, চালিয়ে দেখা {c[k + ' observed']:,}",
          f"({100 * c[k + ' observed'] / c[k + ' claimed']:.1f}%)")

আসল আউটপুট (ব্রাউজারের Python):

program: 107 (বাদ 1), চলা নির্দেশ: 23,243
দুই solver-এর উত্তর এক: 963 বার
  liveness: worklist 2,730 · round-robin 5,772
  reaching definitions: worklist 4,638 · round-robin 6,721
  available expressions: worklist 2,434 · round-robin 4,397
ভুল দাবি — live: 0 · reaching: 0 · available: 0
live: দাবি 19,357, চালিয়ে দেখা 18,339 (94.7%)
rd: দাবি 241,166, চালিয়ে দেখা 176,933 (73.4%)

পর্ব ৬২-এর দশটি উদাহরণের আটটি (recursion বাদ শুধু সময় বাঁচাতে, কারণ তার এক লাখের বেশি চলা নির্দেশ; nested-এ nested function, যা Haat IR v1-এর বাইরে), আর seed 0–99-এর ১০০টি এলোমেলো program; আটটির মধ্যে counter closure-এর জন্য বাদ পড়ে। দুই solver ৯৬৩টি প্রশ্নেই একই IN আর OUT দেয়, কিন্তু liveness-এ worklist অর্ধেকের কম কাজে। ভুল দাবি তিন বিশ্লেষণেই শূন্য। শেষ দুই লাইন নির্ভুলতার মাপ: “live” বলা নামের ৯৪.৭% সত্যিই পরে পড়া হয়েছে, reaching definitions-এর ৭৩.৪% সত্যিই পৌঁছেছে। বাকিটা ভুল নয়, সাবধানতা: অন্য input-এ সেই পথ হয়তো চলত (অংশ ৯)।

লেখকের lab-এ (CPython 3.14.4) পরীক্ষাটি বড় করে: ৮টি উদাহরণ (recursion-সহ) আর ৩,০০০টি এলোমেলো program, মোট ৯,০২০টি function আর ৯,৬২,০৬১টি চলা নির্দেশ। ২৭,০৬০টি প্রশ্নেই দুই solver-এর উত্তর এক, ভুল দাবি শূন্য, আর দাবির ৯৫.২% (liveness) ও ৭৩.০% (reaching definitions) চালিয়ে দেখা গেছে। কাজের হিসাব (block-হিসাবের সংখ্যা):

বিশ্লেষণworklistround-robinঅনুপাত
Liveness৭৯,৮২৫১,৬৬,০৯৬০.৪৮
Reaching definitions১,৩০,৩৬৮১,৯৩,৮০০০.৬৭
Available expressions৭১,৩২৫১,২৮,৮০৪০.৫৫

দুটি solver-ই একই ক্রম (reverse postorder) ব্যবহার করেছে; round-robin-এর বাড়তি কাজ মূলত শেষের “কিছু বদলায়নি” রাউন্ড আর loop-এর বাইরের block বারবার দেখা। এগুলো গোনা visit, সময় নয়।

পরীক্ষাটি নিজে কাজ করে কি না, তাও দেখা দরকার: যে test কখনো ব্যর্থ হয় না, সে হয়তো কিছুই দেখে না। Lab-এ তাই solver-এ জেনেশুনে ভুল বসানো হয়েছে (mutation testing). Liveness-এর meet ∩ করলে ১,৮৫৫টি program-এ ২,৮৭,৭০৮টি ভুল দাবি ধরা পড়ে; একবারের হিসাবের ফল অনুশীলন ২-এ। Reaching definitions থেকে kill বাদ দিলে কোনো ভুল ধরা পড়ে না, শুধু দাবি ৬৮,৯৯,৫০৩ থেকে বেড়ে ৬৯,২৮,৩০৭: কম নিখুঁত কিন্তু এখনো sound. এই পরীক্ষা soundness দেখে; নির্ভুলতার মাপ শুধু “observed ÷ claimed”.

৯ · Precision বনাম soundness — বিশ্লেষণ কোন দিকে ভুল করে

“x এখানে live কি না” প্রশ্নের নিখুঁত উত্তর দেওয়া অসম্ভব। x পরে পড়া হবে কি না জানতে হলে জানতে হয় program কোন পথে চলবে, আর তার মধ্যে আছে “এই loop কখনো থামবে কি না”: halting problem. সাধারণভাবে, program-এর আচরণ নিয়ে প্রতিটি অতুচ্ছ প্রশ্ন undecidable, যা Rice-এর উপপাদ্য (গণনার তত্ত্বের পর্ব ৫৩)। তাই প্রতিটি dataflow analysis একটি আনুমানিক উত্তর দেয়, আর আসল প্রশ্ন হলো: ভুল করলে কোন দিকে?

উত্তর ঠিক করে ব্যবহার। Liveness বেশি নাম live বললে register অকারণে আটকে থাকে (ধীর, কিন্তু সঠিক); কম বললে দুটি জীবিত মান এক register পায় (ভুল ফল)। Available expressions-এ উল্টো: কম বললে হিসাব আবার হয়, বেশি বললে বাসি মান ব্যবহার হয়। এই “নিরাপদ দিকে ভুল” হলো soundness; যত কম বাড়তি, তত বেশি precision. অংশ ৮-এ miss = ০ মানে sound, আর observed ÷ claimed precision-এর একটি নিচের সীমা।

অনুমানের উৎস দুটি। প্রথমত, CFG-র প্রতিটি পথ সম্ভব বলে ধরা হয়, এমনকি যেগুলো কোনো input-এ চলে না:

if express { fee = 40; }
...                       // মাঝে express বদলায় না
if express { print(fee); }

প্রথম if মিথ্যা আর দ্বিতীয়টি সত্য, এমন পথ বাস্তবে নেই, কিন্তু CFG-তে আছে; তাই reaching definitions বলে print(fee)-এ fee-র পুরোনো মানও পৌঁছাতে পারে। শর্তের সম্পর্ক মনে রাখা বিশ্লেষণ path-sensitive, যেমন Clang Static Analyzer-এর বেশির ভাগ checker; compiler-এর সাধারণ dataflow সস্তা থাকতে ইচ্ছা করে path-insensitive.

দ্বিতীয় উৎসটি সূক্ষ্ম: meet-এর সময়। আদর্শ উত্তর হতো প্রতিটি পথ আলাদা করে হিসাব করে শেষে মেলানো, যার নাম meet over all paths (MOP). আমাদের solver প্রতিটি মিলনে সঙ্গে সঙ্গে মেলায় (maximal fixpoint, MFP). Kildall দেখান, transfer distributive হলে, অর্থাৎ f(x ⊓ y) = f(x) ⊓ f(y), MFP = MOP; gen/kill-এর সব বিশ্লেষণ এমন, constant propagation নয়:

fn mix(flag: Bool) -> Int {
    var a = 1;
    var b = 2;
    if flag { a = 2; b = 1; }
    let c = a + b;
    return c;
}

দুই পথেই c = 3 (reference ছাপে 3 আর 3), তাই MOP বলে c = 3. কিন্তু মিলনের বিন্দুতে আগে মেলালে a = 1 ⊓ 2 = ⊥ আর b = 2 ⊓ 1 = ⊥, তারপর c = ⊥: লেখকের lab-এ haat_dfa.py-র solver-এ constant-এর Problem বসিয়ে ঠিক এই উত্তর এসেছে। উত্তরটি sound, কিন্তু MOP-এর চেয়ে কম নিখুঁত। Kam আর Ullman ১৯৭৭ সালে দেখান যে সাধারণ monotone framework-এ MOP হিসাব করার কোনো সাধারণ অ্যালগরিদম নেই, তাই MFP-ই বাস্তব পছন্দ।

আরও গভীরে: বাস্তব compiler-এ dense dataflow (প্রতিটি block-এ প্রতিটি নামের set) প্রায়ই sparse বিশ্লেষণে বদলে যায়: SSA form-এ (পর্ব ৬৩) প্রতিটি নামের একটিই definition, তাই reaching definitions-এর প্রশ্ন নামেই মিটে যায়, আর constant propagation def-use edge ধরে চলে (Wegman–Zadeck-এর sparse conditional constant propagation, ১৯৯১ সালের প্রবন্ধ)। LLVM liveness-এর মতো তথ্য মূলত register allocation-এর কাছাকাছি, machine-স্তরে হিসাব করে; Java-র মতো GC-ওয়ালা runtime-এ JIT compiler প্রতিটি safepoint-এ কোন pointer live তা জানায় (stack map), যাতে garbage collector মৃত pointer-কে root না ধরে। আর interval-এর মতো অসীম উচ্চতার lattice-এ থামতে widening লাগে, যা গণনার তত্ত্বের পর্ব ৭৮-এ আছে।

১০ · AI-এর যুগে dataflow analysis

AI assistant liveness বা reaching definitions-এর কোড কয়েক সেকেন্ডে লিখে দেয়, আর ছোট উদাহরণে উত্তর প্রায়ই ঠিক আসে। কিন্তু এখানকার ভুল loop ছাড়া ধরা পড়ে না, আর ভুল বিশ্লেষণের ওপর বসানো optimization চুপচাপ অর্থ বদলায়।

AI-এর ভুলকীভাবে ধরবেন
Fixpoint ছাড়া একবারের হিসাব; loop-এর back edge বাদLoop-ওয়ালা উদাহরণ (cart.haat); দুই solver-এর উত্তর তুলনা; চালিয়ে দাবি যাচাই
দিক বা meet ভুল: liveness forward, বা may-তে ∩সংজ্ঞা থেকে প্রশ্নটি নিজে বলুন (“কোনো পথে” না “সব পথে”, অতীত না ভবিষ্যৎ)
Must-analysis ∅ দিয়ে শুরু, বা may-analysis সব-set দিয়েLoop-এর ভেতরের একটি নিশ্চিত available expression দিয়ে test
Global, call আর side effect-কে local নামের মতো ধরাFunction-এর ভেতরে global লেখা আর call-এর পরে পড়া, এমন উদাহরণ
Dead store পেলেই নির্দেশ মুছে ফেলা, call বা ভাগসহশূন্য দিয়ে ভাগ আর ছাপা call-সহ program আগে-পরে চালানো
বানানো compiler flag বা LLVM pass-এর নামনিজের compiler-এর version-এ --help-এর তালিকা বা documentation পড়া; চালিয়ে দেখা

AI-কে কাজে লাগাতে প্রশ্নের চারটি উপাদান আর যাচাইয়ের উপায় নিজেই বলে দিন:

আমি Python 3.14-এ একটি ছোট IR-এর (Haat IR) জন্য dataflow analysis লিখছি। CFG-র প্রতিটি block একটি নির্দেশের list; প্রতিটি নির্দেশের dst (যে নাম লেখে) আর args (যে নাম পড়ে) আছে; @ দিয়ে শুরু নাম global, সেগুলো বাদ দাও। ১. একটি সাধারণ worklist solver লেখো: Problem-এ থাকবে দিক, meet, ⊤, boundary আর নির্দেশ-স্তরের transfer. Loop-ওয়ালা CFG-তে fixpoint পর্যন্ত চলবে। ২. এর ওপর liveness (backward, ∪) আর reaching definitions (forward, ∪) দাও; প্রতিটির ⊤ আর boundary কেন এমন, এক লাইনে বলো। ৩. একটি loop-ওয়ালা উদাহরণে প্রতিটি block-এর IN আর OUT হাতে হিসাব করে দেখাও, যাতে আমি কোডের ফলের সঙ্গে মেলাতে পারি। ৪. Dead store খুঁজে পেলে মুছবে না; শুধু তালিকা দেবে, কারণ call আর শূন্য দিয়ে ভাগের side effect আছে। ৫. কোনো বাস্তব compiler-এর pass বা flag-এর নাম বললে version বলো; নিশ্চিত না হলে অনুমান করবে না।

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

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Gary Kildall-এর ১৯৭৩ সালের “unified approach”: আলাদা আলাদা কৌশল থেকে একটি কাঠামোয় আসা কেন এত বড় পদক্ষেপ ছিল?

১৯৬০-এর দশকে optimizing compiler-গুলো প্রতিটি optimization-এর জন্য আলাদা, হাতে বানানো বিশ্লেষণ লিখত। IBM-এ Frances Allen আর John Cocke control flow আর loop-এর তত্ত্ব দাঁড় করান (পর্ব ৬২-এর ভাবনার প্রশ্ন ৩), আর ১৯৭০-এর দশকের শুরুতে liveness, available expressions বা constant propagation-এর জন্য আলাদা আলাদা অ্যালগরিদম প্রকাশিত হচ্ছিল। প্রতিটির নিজের প্রমাণ, নিজের কোড, নিজের ভুল।

Gary Kildall-এর ১৯৭৩ সালের POPL সম্মেলনের প্রবন্ধ “A Unified Approach to Global Program Optimization” দেখায় যে এরা আসলে একটিই অ্যালগরিদম, শুধু তথ্যের ধরন আর মেলানোর নিয়ম আলাদা: একটি meet-semilattice, প্রতিটি node-এর একটি function, আর একটি সাধারণ iterative পদ্ধতি, যা distributive হলে সব পথের meet-এর সমান উত্তর দেয়। Kildall পরে CP/M operating system-এর নির্মাতা হিসেবে বেশি পরিচিত হন, কিন্তু compiler-এর জগতে এই প্রবন্ধই তাঁর স্থায়ী অবদান বলে ধরা হয়। এরপর Kam আর Ullman (১৯৭৬–৭৭) কাঠামোটিকে monotone function পর্যন্ত বাড়ান আর দেখান কোথায় MOP আর পাওয়া যায় না।

লাভটি প্রকৌশলের। একটি সঠিক, ভালোভাবে পরীক্ষিত solver থাকলে নতুন বিশ্লেষণ মানে শুধু একটি lattice আর কয়েকটি transfer লেখা, যেমন এই পর্বে very busy expressions এসেছে ছয় লাইনে। ভুলের জায়গাও কমে: থামার প্রমাণ একবার, সঠিকতার পরীক্ষা একবার। আজকের static analyzer আর abstract interpretation-এর কাঠামোও (Cousot ১৯৭৭) একই চিন্তার বড় রূপ।

মূল উপলব্ধি: অনেকগুলো আলাদা কৌশলের পেছনে একটি গাণিতিক গড়ন খুঁজে পাওয়া মানে একবার প্রমাণ, একবার কোড, আর নতুন বিশ্লেষণ প্রায় বিনামূল্যে।

প্র ০২Liveness ছাড়া register allocation অসম্ভব কেন, আর garbage collector-ও liveness-এর ওপর কেন নির্ভর করে?

একটি CPU-তে register হাতে গোনা, RISC-V-তে ৩২টি, যার কয়েকটি বিশেষ কাজে বাঁধা। অথচ একটি function-এ শত শত temp থাকতে পারে। দুটি মান একই register ভাগ করতে পারে ঠিক তখন, যখন তারা কখনো একসঙ্গে live নয়। তাই register allocation-এর প্রথম কাজ liveness: প্রতিটি নির্দেশের পরে কোন মানগুলো live, আর সেখান থেকে একটি interference graph, যেখানে একসঙ্গে live দুটি মানের মাঝে একটি edge. Gregory Chaitin আর সহকর্মীরা ১৯৮১–৮২ সালে IBM-এ এই graph রং করে register বাছার পদ্ধতি দেন; রঙের সংখ্যা মানে register-এর সংখ্যা (পর্ব ৭০)। এখানে soundness-এর দিকটি স্পষ্ট: liveness কম বললে দুটি জীবিত মান একই register পাবে, আর একটি অন্যটিকে মুছে দেবে।

Call-এর চারপাশেও একই প্রশ্ন। Calling convention (পর্ব ৩০-এ activation record, আর পর্ব ৭১-এ ABI) কিছু register-কে “caller-saved” বলে: call-এর পরে সেগুলোর মান নিশ্চিত নয়। তাই compiler জানতে চায় কোন মান call পেরিয়েও live, আর শুধু সেগুলো সংরক্ষণ করে (অনুশীলন ১)।

Garbage collector-এর প্রশ্নও liveness-এর আত্মীয়। GC জানতে চায় কোন object এখনো লাগতে পারে; শুরু হয় “root” থেকে: stack আর register-এ থাকা pointer. JIT compiler প্রতিটি নিরাপদ থামার বিন্দুতে (safepoint) একটি তালিকা রাখে, কোন stack slot-এ এখন live pointer আছে। Liveness না জানলে GC মৃত pointer-কেও root ধরবে, আর অনেক object অকারণে বেঁচে থাকবে (পর্ব ৭৫-এর বিষয়)। এক্ষেত্রে বেশি বলা নিরাপদ কিন্তু memory নষ্ট; কম বলা মারাত্মক।

মূল উপলব্ধি: “কোন মান এখনো লাগবে” প্রশ্নটি compiler-এর নিচের স্তরে সবখানে: register, call-এর চারপাশ, GC-র root; আর সবখানেই ভুলের নিরাপদ দিক হলো বেশি live বলা।

প্র ০৩Bit vector-এর dense বিশ্লেষণ থেকে SSA-র sparse বিশ্লেষণে: আধুনিক compiler reaching definitions প্রায় হিসাবই করে না কেন?

এই পর্বের বিশ্লেষণ “dense”: প্রতিটি block-এ, অনেক সময় প্রতিটি নির্দেশে, সব নামের একটি set. Reaching definitions-এ set-এর আকার সব definition-এর সংখ্যা, তাই memory আর সময় দুটিই program-এর আকারের প্রায় বর্গে বাড়তে পারে। ১৯৭০-৮০-র দশকের compiler bit vector দিয়ে একে সস্তা করত: একটি definition মানে একটি bit, ∪ মানে কয়েকটি OR নির্দেশ। ছোট function-এ এটি চমৎকার, কিন্তু বড় function-এ, যেখানে হাজার হাজার temp, set-গুলো বিশাল আর বেশির ভাগ bit শূন্য।

Cytron ও সহকর্মীদের SSA form (১৯৯১ সালের প্রবন্ধ, পর্ব ৬৩) প্রশ্নটিকেই বদলে দেয়। প্রতিটি নামে একবারই মান বসে, আর মিলনে φ; তাই “এই পড়ায় কোন definition পৌঁছায়” প্রশ্নের উত্তর নামটিই: total.2-এর definition একটি। Use-def chain হলো সরাসরি একটি pointer. Constant propagation তখন শুধু def-use edge ধরে চলে (sparse), প্রতিটি block-এ প্রতিটি নামের মান বয়ে নেওয়ার দরকার পড়ে না। LLVM IR জন্ম থেকেই SSA, আর তার optimization-গুলো এভাবেই লেখা।

তবে dense বিশ্লেষণ উধাও হয়নি। Liveness SSA-তেও লাগে, বিশেষ করে register allocation-এর সময়, যখন SSA ভেঙে আবার সাধারণ কোডে ফেরা হয়। Memory-র মধ্য দিয়ে প্রবাহিত মান (pointer, array) SSA-র নামে ধরা পড়ে না, তাই সেখানে আলাদা dataflow বা alias analysis লাগে। আর debugger বা static analyzer অনেক সময় source-এর কাছাকাছি CFG-তেই কাজ করে, যেমন Clang-এর DeadStores checker.

মূল উপলব্ধি: SSA একবার dataflow-এর কাজ করে নামের মধ্যে উত্তর লিখে রাখে; তারপর অনেক প্রশ্নের জন্য পুরো set বয়ে নিতে হয় না, শুধু def-use edge ধরে হাঁটলেই চলে।

প্র ০৪Compiler-এর warning কখনো অকারণে চেঁচায়, কখনো আসল ভুলে চুপ থাকে। এটি কি compiler-লেখকদের অবহেলা, না এর পেছনে গভীর কারণ আছে?

কারণটি গভীর, আর এর নাম Rice-এর উপপাদ্য। “এই variable পড়ার আগে কি সবসময় মান পায়” বা “এই লেখার মান কি কখনো পড়া হয়”, এগুলো program-এর আচরণ নিয়ে প্রশ্ন, আর সাধারণভাবে undecidable. তাই প্রতিটি warning একটি আনুমানিক বিশ্লেষণের ফল, যা দুই দিকের একটিতে ঝোঁকে। Sound দিকে ঝুঁকলে কোনো আসল সমস্যা বাদ পড়ে না, কিন্তু কিছু মিথ্যা সতর্কতা আসে (false positive); উল্টো দিকে ঝুঁকলে প্রতিটি সতর্কতা সত্যি, কিন্তু কিছু আসল সমস্যা চুপচাপ পেরিয়ে যায়।

বাস্তব tool-গুলো ইচ্ছা করে মাঝামাঝি থাকে। Programmer মিথ্যা warning সহ্য করেন না: কয়েকবার ভুল সতর্কতা দেখলে warning-ই বন্ধ করে দেন। তাই -Wunused-but-set-variable-এর মতো warning নামের স্তরে সরল নিয়ম মানে আর tries = tries + 1-এ চুপ থাকে (অংশ ৫-এর সত্যিকারের run). আরও গভীর প্রশ্নের জন্য আলাদা tool, যেমন Clang Static Analyzer, যার বেশির ভাগ checker path-sensitive: শর্তগুলো মনে রেখে পথ ধরে চলে, তাই অংশ ৯-এর if express দুবারের মতো উদাহরণে ভুল সতর্কতা কম দেয়, কিন্তু চলতে অনেক বেশি সময় নেয় আর সব পথ দেখতে পারে না। GCC-র কিছু uninitialized warning optimization-এর স্তরের ওপর নির্ভর করে বলে GCC-র documentation নিজেই সতর্ক করে, কারণ সেই বিশ্লেষণ optimizer-এর তথ্য ব্যবহার করে।

Optimization-এর জন্য নিয়ম কড়া: সেখানে soundness ছাড়া চলে না, কারণ ভুল বিশ্লেষণে বসানো optimization program-এর অর্থ বদলায়। Warning-এর জন্য নিয়ম নরম: সেখানে ব্যবহারযোগ্যতাই প্রধান। একই compiler দুই নীতিতে চলে।

মূল উপলব্ধি: নিখুঁত warning অসম্ভব; প্রশ্ন শুধু কোন দিকে ভুল করা হবে, আর optimization ও warning-এর উত্তর আলাদা।

প্র ০৫Block কোন ক্রমে দেখা হয়, তা উত্তর বদলায় না, তবু compiler-লেখকেরা ক্রম নিয়ে এত মাথা ঘামান কেন?

উত্তর বদলায় না, কারণ worklist বা round-robin যেকোনো ক্রমে একই সবচেয়ে বড় fixpoint-এ পৌঁছায়; অংশ ৮-এ ২৭,০৬০টি প্রশ্নে তা মেপে দেখা হয়েছে। কিন্তু কাজের পরিমাণ বদলায়। Forward বিশ্লেষণে একটি block-এর মান তার predecessor থেকে আসে; reverse postorder-এ প্রতিটি block তার সব predecessor-এর পরে আসে, শুধু back edge ছাড়া। ফলে loop ছাড়া কোডে এক রাউন্ডেই সব মান চূড়ান্ত। উল্টো ক্রমে প্রতিটি তথ্য এক রাউন্ডে মাত্র এক ধাপ এগোয়, আর রাউন্ড লাগে block-এর সংখ্যার কাছাকাছি।

Kam আর Ullman ১৯৭৬ সালের দিকে দেখান, একটি বিশেষ শ্রেণির (“rapid”) বিশ্লেষণে, যেখানে liveness, reaching definitions আর available expressions পড়ে, reverse postorder-এ round-robin মোটামুটি d + 2 রাউন্ডে থামে (রাউন্ড গোনার রীতিভেদে উৎসে সংখ্যাটি একটু আলাদা লেখা দেখা যায়), যেখানে d মোটামুটি loop-এর ঘনত্ব: কোনো চক্রহীন পথে সর্বোচ্চ কয়টি back edge. সাধারণ program-এ d ছোট, এক বা দুই, তাই বাস্তবে কয়েক রাউন্ডই যথেষ্ট। অংশ ৪-এর cart_total-এ একটি loop, আর ঠিক ৩ রাউন্ড লেগেছে, যার শেষটি শুধু “কিছু বদলায়নি” প্রমাণ।

Worklist আরও এক ধাপ এগোয়: যে block-এর ইনপুট বদলায়নি, তাকে আবার দেখে না। এই পর্বের মাপে liveness-এ round-robin-এর অর্ধেকের কম visit. বড় compiler-এ, যেখানে একটি function-এ হাজার block আর set-গুলো বড়, এই পার্থক্য compile-এর সময়ে চোখে পড়ে। Cooper, Harvey আর Kennedy-র মতো লেখকেরা যুক্তি দিয়েছেন, ভালো ক্রমের সরল iterative অ্যালগরিদম অনেক সময় জটিল তাত্ত্বিক অ্যালগরিদমের চেয়েও বাস্তবে দ্রুত।

মূল উপলব্ধি: সঠিকতা আসে lattice আর monotone-তা থেকে, গতি আসে ক্রম থেকে; reverse postorder আর worklist একসঙ্গে একটি সরল অ্যালগরিদমকে বাস্তবে যথেষ্ট দ্রুত বানায়।

অনুশীলন

প্রথমে নিজে হিসাব করুন বা লিখুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর সত্যিকারের run দিয়ে যাচাই করা।

  1. নকশা ও বাস্তবায়ন — call পেরোনো মান: পর্ব ৭০-এর register allocator আর পর্ব ৭১-এর calling convention-এর জন্য দরকার, প্রতিটি call-এর পরে কোন মান তখনো লাগবে (এগুলো caller-saved register-এ রাখা যাবে না, বা সংরক্ষণ করতে হবে)। haat_dfa.py-র ওপর একটি live_across_calls(fn) লিখুন, যা প্রতিটি call-এর (b, i) থেকে সেই নামগুলোর set দেয়। call-এর নিজের ফল (dst) কি তালিকায় থাকবে? bazar.haat-এর <main>-এ উত্তর কী?
    def live_across_calls(fn):                       # call-এর পরে live, কিন্তু call নিজে যা লেখে তা বাদ
        _, pts = analyze(fn, LIVENESS)
        return {(b, i): pts[b, i][1] - set(defs(ins)) for b, body in fn.blocks.items()
                for i, ins in enumerate(body) if ins.kind == "call"}

    dst বাদ যায়, কারণ তার মান আসে call শেষ হওয়ার পরে; রক্ষা করার কিছু নেই। লেখকের lab-এ সত্যিকারের run, bazar <main>: t3 = call price(t1, t2)-এ খালি set; t6 = call price(t4, t5)-এ {t3}; t7 = call delivery(t6)-এ {t3}. অর্থাৎ প্রথম price(2, 520)-এর ফল t3 পরের দুটি call পেরিয়ে বাঁচতে হয়, কারণ first = t3 + t7 তাকে শেষে পড়ে। একটি register allocator তাই t3-কে callee-saved register-এ রাখবে, বা দুটি call-এর আগে stack-এ সংরক্ষণ করবে। t6 তালিকায় নেই: delivery-র argument হিসেবে সে call-এর ভেতরে যায়, পরে আর লাগে না। price আর delivery-তে কোনো call নেই, তাই খালি।

  2. ভুল খুঁজুন — একবারের হিসাব: একজন সহকর্মী solve-কে “দ্রুত” করতে চাইলেন: প্রতিটি block ঠিক একবার, reverse postorder-এ (backward-এ উল্টো), কোনো সারি বা রাউন্ড ছাড়া। Loop ছাড়া কোডে উত্তর ঠিক থাকে কেন? Loop থাকলে কোন বিশ্লেষণ কোন দিকে ভুল করে, আর অংশ ৮-এর trace-ভিত্তিক পরীক্ষা কী বলবে?

    Loop ছাড়া CFG একটি DAG, আর reverse postorder-এ প্রতিটি block তার সব উৎস-প্রতিবেশীর পরে আসে, তাই প্রথম হিসাবেই প্রতিটি মান চূড়ান্ত। Loop থাকলে loop-এর মাথা প্রথমবার হিসাব হয় back edge-এর মান ⊤ ধরে। May-analysis-এ ⊤ = ∅, তাই back edge দিয়ে আসা তথ্য বাদ পড়ে: cart_total-এ B2-এর IN-এ items থাকত না, অর্থাৎ liveness একটি দরকারি নামকে মৃত বলত, আর register allocator সেই register-এ অন্য মান বসাত। Must-analysis-এ ⊤ = U, তাই উল্টো: back edge-এর পথে মুছে যাওয়া expression-ও “available” থেকে যায়, আর CSE একটি বাসি মান ব্যবহার করত। দুটিই unsound.

    লেখকের lab-এ ভুল solver-টি বসিয়ে ৩,০০৮টি program-এ (যার ২,২৯৭টিতে অন্তত একটি loop) পরীক্ষা চালানো হয়েছে, সত্যিকারের run: liveness-এ ২,০৮,৭১৯টি ভুল দাবি ১,৫২৮টি program-এ, reaching definitions-এ ৩৬,৬৮,৭১৭টি ভুল দাবি একই ১,৫২৮টিতে, available expressions-এ ১,৪৯৩টি ভুল দাবি মাত্র ২৭টি program-এ। Loop-ওয়ালা প্রায় ৭৭০টি program-এ ভুলটি ধরাই পড়েনি: হয়তো loop একবারও ঘোরেনি, বা ভুল নামটি পরে পড়া হয়নি। শিক্ষা: চালিয়ে যাচাই শুধু চলা পথের ভুল ধরে; loop-ওয়ালা বাছাই করা উদাহরণ আর দুই solver-এর উত্তরের তুলনাও রাখুন।

  3. হিসাব — পরীক্ষার ধাঁচে liveness আর reaching definitions: পর্ব ৬২-এর অনুশীলনের bags function-এর CFG নিচে। (ক) প্রতিটি block-এর use আর def; (খ) liveness-এর IN আর OUT; (গ) B1 আর B5-এ Haat-এর নামগুলোর reaching definitions; (ঘ) কোনো dead store আছে কি?
    fn bags(items):
    B0:  n = const 0;  left = items;  jump B1
    B1:  t1 = const 0;  t2 = left > t1;  branch t2 B2 B3
    B2:  t3 = const 6;  left = left - t3;  t4 = const 1;  n = n + t4;  jump B1
    B3:  t5 = const 3;  t6 = n > t5;  branch t6 B4 B5
    B4:  t7 = const 1;  n = n - t7;  jump B5
    B5:  return n
    blockusedefINOUT
    B0itemsleft, nitemsleft, n
    B1leftt1, t2left, nleft, n
    B2left, nleft, n, t3, t4left, nleft, n
    B3nt5, t6nn
    B4nn, t7nn
    B5n—n—

    সব মান haat_dfa.py-র সত্যিকারের আউটপুট (worklist ৭টি visit, round-robin ১২টি)। লক্ষ করুন B1-এর use শুধু left, কিন্তু IN-এ n-ও আছে: শর্তে n লাগে না, তবু loop-এর পরে B3 n পড়ে, তাই n পুরো loop জুড়ে live. (গ) B1-এ: items@in, n@B0.0, left@B0.1, left@B2.1, n@B2.3, অর্থাৎ n আর left দুটিই loop-এর আগের বা আগের রাউন্ডের লেখা থেকে আসতে পারে। B5-এ এর সঙ্গে আরও একটি, n@B4.1, কারণ B5-এ দুটি পথ মেলে: B3 থেকে সরাসরি আর B4 হয়ে। (ঘ) dead_stores খালি তালিকা দেয়: প্রতিটি লেখা কোনো পথে পড়া হয়। Reference-এ bags(20) আর bags(6) ছাপে 3 আর 1 (পর্ব ৬২)।

  4. প্রমাণ — gen/kill-এর transfer distributive: দেখান যে f(X) = gen ∪ (X − kill) সব set X, Y-এর জন্য f(X ∪ Y) = f(X) ∪ f(Y) মানে, আর তাই monotone. তারপর constant-এর lattice-এ c = a + b-এর transfer-এর জন্য একটি উদাহরণ দিন যেখানে f(x ⊓ y) ≠ f(x) ⊓ f(y). এই পার্থক্য worklist-এর উত্তরে কী প্রভাব ফেলে?

    প্রমাণ, সরাসরি set-এর নিয়মে:

    1. f(X ∪ Y) = gen ∪ ((X ∪ Y) − kill), সংজ্ঞা থেকে।
    2. (X ∪ Y) − kill = (X − kill) ∪ (Y − kill), কারণ বিয়োগ ∪-এর ওপর ছড়ায়।
    3. তাই f(X ∪ Y) = gen ∪ (X − kill) ∪ (Y − kill) = (gen ∪ (X − kill)) ∪ (gen ∪ (Y − kill)) = f(X) ∪ f(Y), কারণ gen ∪ gen = gen. ∎
    4. Monotone: X ⊆ Y হলে Y = X ∪ Y, তাই f(Y) = f(X) ∪ f(Y) ⊇ f(X). একই যুক্তি ∩-এর জন্যও চলে, তাই available expressions-ও distributive.

    Constant-এর উদাহরণ: x = {a = 1, b = 2}, y = {a = 2, b = 1}. f(x) আর f(y) দুটিতেই c = 3, তাই f(x) ⊓ f(y)-এ c = 3. কিন্তু x ⊓ y = {a = ⊥, b = ⊥}, আর f(x ⊓ y)-এ c = ⊥. অর্থাৎ f(x ⊓ y) ⊏ f(x) ⊓ f(y): monotone (ফল নিচে, সাবধানী দিকে), কিন্তু distributive নয়। প্রভাব: worklist মিলনে আগে meet নেয়, তারপর transfer, তাই তার উত্তর (MFP) এখানে MOP-এর চেয়ে কম নিখুঁত, যদিও sound. অংশ ৯-এর mix function-এ লেখকের lab-এ ঠিক এটি এসেছে: solver বলে c = ⊥, অথচ দুই পথেই c = 3, আর reference ছাপে 3, 3. Gen/kill বিশ্লেষণে এমন ক্ষতি হয় না, কারণ সেখানে MFP = MOP (Kildall ১৯৭৩)।

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

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

ক্রমএকটি worklist dataflow solver-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. প্রতিটি block-এর মান ⊤ ধরে নেওয়া
  2. সব block reverse postorder-এ সারিতে রাখা
  3. সারি থেকে একটি block তুলে উৎস-প্রতিবেশীদের মানের meet নেওয়া
  4. সেই মানে block-এর transfer function চালানো
  5. ফল বদলালে গন্তব্য-প্রতিবেশীদের সারিতে তোলা
  6. সারি খালি হলে থামা: প্রতিটি সমীকরণ এখন সত্য

Liveness analysis কোন দিকে চলে, আর দুটি পথ মিললে তথ্য কীভাবে মেলানো হয়?

  • Forward, ∪ দিয়ে
  • Backward, ∪ দিয়ে
  • Backward, ∩ দিয়ে
  • Forward, ∩ দিয়ে

একটি block-এ নির্দেশ তিনটি: a = b + c, d = a + e, return d. Block-এর শুরুতে কোন নামগুলো live?

  • {a, b, c, d, e}
  • {b, c}
  • {b, c, e}
  • {a, e}

একটি CFG: B0-এ x = const 0 (d1), তারপর loop-এর মাথা B1, আর loop-এর দেহ B2-এ x = x + t (d2), যা আবার B1-এ ফেরে। B1-এর শুরুতে x-এর কোন definition পৌঁছায়?

  • d1 আর d2 দুটিই
  • শুধু d1
  • শুধু d2
  • কোনোটিই নয়, কারণ দুটি পরস্পরকে মুছে দেয়

Available expressions (forward, must, ∩) বিশ্লেষণে loop-এর ভেতরের block-গুলোর শুরুর মান ⊤ হিসেবে কেন সব expression-এর set U নেওয়া হয়, খালি set নয়?

  • খালি set দিলে solver কখনো থামে না
  • U দিলে উত্তর unsound হয়, কিন্তু দ্রুত
  • Entry-তে সব expression available থাকে
  • ∩-এ ⊤ যেন কিছু না মোছে; খালি set দিলে loop-এর ভেতরে কিছুই available বলা যেত না

একটি iterative dataflow solver যে একসময় থামবেই, তার জন্য কোন দুটি শর্ত যথেষ্ট?

  • CFG-তে কোনো loop না থাকা আর meet = ∪
  • Lattice-এর উচ্চতা সসীম আর transfer function monotone
  • Transfer function distributive আর SSA form
  • Block-গুলো reverse postorder-এ দেখা আর worklist ব্যবহার

একটি constant-propagation বিশ্লেষণে মিলনের বিন্দুতে এক পথ থেকে a = 1, b = 2 আর অন্য পথ থেকে a = 2, b = 1 আসে; তারপর c = a + b. Iterative solver (MFP) আর সব পথ আলাদা করে হিসাব (MOP) c সম্পর্কে কী বলে?

  • MFP: c ধ্রুবক নয় (⊥); MOP: c = 3
  • দুটিই বলে c = 3
  • দুটিই বলে c ধ্রুবক নয় (⊥)
  • MFP: c = 3; MOP: c ধ্রুবক নয় (⊥)

শব্দকোষ

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

মনে রাখুন

  1. চার উপাদান: lattice, meet (may-তে ∪, must-এ ∩), monotone transfer আর দিক; এই চারটি বদলালেই নতুন বিশ্লেষণ, solver একই।
  2. Fixpoint: সব ⊤ থেকে শুরু, worklist-এ শুধু যার ইনপুট বদলেছে; সসীম উচ্চতা আর monotone-তায় থামে, visit ≤ N + h · E.
  3. Liveness: backward, ∪, IN = use ∪ (OUT − def); dead store = লেখার পরে নামটি live নয়, কিন্তু call আর ভাগ মোছা যায় না।
  4. Reaching definitions: forward, ∪, OUT = gen ∪ (IN − kill); এখান থেকে use-def chain, পরে constant আর copy propagation.
  5. Sound, কিন্তু আনুমানিক: নিখুঁত উত্তর undecidable; ভুল হবে নিরাপদ দিকে, আর প্রতিটি দাবি চালিয়ে trace-এর সঙ্গে মিলিয়ে দেখা যায়।

পরের পর্বে: পর্ব ৬৫ (Optimization — constant folding, CSE আর dead code elimination). এই পর্বের haat_dfa.py-র liveness আর available expressions দিয়ে IR সত্যিই বদলানো, আর প্রতিটি বদলের পরে run_ir দিয়ে আউটপুট মেলানো।

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

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