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

Optimization — constant folding, CSE আর dead code elimination

Local and Global Optimization — Constant Folding, CSE and Dead Code Elimination

Taught in Bangla, this lesson implements classic optimizations on Haat IR: constant folding and propagation across branches, algebraic simplification, copy propagation, common subexpression elimination with local value numbering and available expressions, dead code elimination with liveness and mark-sweep, and a peephole pass. It shows traps from 64-bit wrap and division by zero, compares pass orderings, and catches a deliberately planted x / x to 1 rule with differential testing, alongside real Clang output.

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

  • Optimization-এর সঠিকতার চুক্তি, আর local, global ও interprocedural optimization-এর পার্থক্য
  • Constant folding ও propagation, ধ্রুবক শর্তের branch আর অগম্য block; কেন শূন্য দিয়ে ভাগ কখনো fold হয় না
  • Copy propagation, local value numbering আর available expressions দিয়ে global CSE, হাতে আর কোডে
  • Dead code elimination: liveness দিয়ে, আর mark–sweep দিয়ে এক ধাপে; কোন নির্দেশ মৃত হলেও মোছা যায় না
  • Algebraic simplification, peephole (Haat-এর stack bytecode-এ), pass-এর ক্রম, আর CPython ও Clang-এর সত্যিকারের optimization

১ · অর্থ না বদলে কম কাজ — optimization কী

সকালে বাজারে যাওয়ার আগে মা ফর্দটি একবার দেখে নেন। “আলু ১ কেজি” দুবার লেখা থাকলে একটি কেটে দেন; “৫০ + ১০ টাকার পান” লেখা থাকলে আগেই যোগ করে লেখেন “৬০ টাকার পান”; আর অতিথি না আসায় যে মিষ্টি আর লাগবে না, সেটি বাদ দেন। ফর্দ ছোট হলো, অথচ বাজার থেকে ঠিক যা দরকার তাই আসবে। Compiler-এর optimization হুবহু এই কাজ: program-এর অর্থ না বদলে তাকে কম কাজের রূপে লেখা।

“Optimization” নামটি অবশ্য একটু বাড়িয়ে বলা। সবচেয়ে ছোট বা সবচেয়ে দ্রুত সমতুল্য program খুঁজে পাওয়া সাধারণভাবে অসম্ভব: দুটি program সব input-এ একই আচরণ করে কি না, এই প্রশ্ন undecidable (Rice-এর উপপাদ্য, গণনার তত্ত্বের পর্ব ৫৩)। তাই optimizer শুধু কিছু নিরাপদ, পরিচিত রূপান্তর জানে, আর যেখানে নিশ্চিত নয় সেখানে কিছুই করে না।

সংজ্ঞা ৬৫.১ — একটি রূপান্তর সঠিক, যদি

প্রতিটি input-এ রূপান্তরের আগের আর পরের program-এর দেখা যায় এমন আচরণ একই হয়। Haat-এ দেখা যায় এমন আচরণ তিনটি: ছাপা লাইনগুলো ক্রমসহ; runtime error হলে তার বার্তা আর line:col (সিদ্ধান্ত ২৪ আর ২৬); আর program থামে কি না। কত নির্দেশ চলল, কোন temp-এ কী থাকল, তা আচরণ নয়, তাই সেগুলো বদলানো যায়।

এই সংজ্ঞা থেকেই তিনটি স্থায়ী নিয়ম আসে, যা এই পর্বের প্রতিটি pass মানে। (১) print আর call-এর ক্রম অটুট, কারণ call ছাপতে বা global বদলাতে পারে। (২) যে / বা %-এর ভাজক শূন্য হতে পারে, তা কখনো fold, মোছা বা সরানো হয় না, কারণ শূন্য দিয়ে ভাগ একটি runtime error, যা আচরণের অংশ। (৩) Int-এর হিসাব ৬৪-bit-এ wrap করে (সিদ্ধান্ত ১৩), তাই compile-এর সময়ের হিসাবও ঠিক সেভাবে করতে হবে।

কাজের পরিধি দিয়ে optimization তিন রকম। Local: একটি basic block-এর ভেতরে, যেখানে কোড সোজা চলে, কোনো শাখা নেই। Global: একটি function-এর পুরো CFG জুড়ে, যেখানে শাখা আর loop-এর জন্য পর্ব ৬৪-এর dataflow analysis লাগে। Interprocedural: function-এর সীমা পেরিয়ে, যেমন inlining, যা পর্ব ৬৭-এর বিষয়। Loop-এর বিশেষ optimization (invariant সরানো, strength reduction) পর্ব ৬৬-এর।

এই পর্ব পর্ব ৬২-এর Haat IR-এর ওপর কাজ করে। haat_front.py, haat_ir.py (lowering, build_cfg, IR interpreter run_ir) আর haat_gen.py পর্ব ৬২-এর কোড, আর haat_dfa.py (Problem, solve, points, liveness, available expressions, ud_chains) পর্ব ৬৪-এর কোড, সব হুবহু, এক অক্ষরও না বদলে। নতুন সব কোড একটি নতুন ফাইল haat_opt.py-তে, যা পর্ব ৬৬ আর ৬৭ হুবহু নেবে। Haat IR-এ operand শুধু নাম, ধ্রুবক আসে শুধু t = const k দিয়ে; SSA (পর্ব ৬৩) এখানে লাগে না, সব pass সাধারণ CFG-র ওপর।

সারা পর্বের উদাহরণ বাজারঘরের বিলের একটি function, যাতে ইচ্ছা করেই কয়েকটি অদক্ষতা রাখা:

// বাজারঘর: ডেলিভারিসহ বিল
fn bill(qty: Int, unit: Int) -> Int {
    let express = false;
    let base = 50 + 10;
    var fee = base;
    if express { fee = base * 2; }
    let p = qty * unit;
    let vat = qty * unit * 5 / 100;
    let lucky = p % 7;
    let avg = p / qty;
    return p + vat + fee;
}
print(bill(2, 520));
print(bill(0, 99));

Reference implementation (python -B haat.py run bill.haat) ছাপে 1152, তারপর 10:17: runtime error: division by zero: দ্বিতীয় call-এ qty = 0, আর ১০ নম্বর লাইনের p / qty শূন্য দিয়ে ভাগ করে। avg-এর মান কেউ পড়ে না, তবু এই error-টিই program-এর শেষ আচরণ। কোনো optimizer যদি “অব্যবহৃত” বলে লাইনটি মুছে দেয়, program তখন 60 ছাপবে, যা ভুল।

২ · Constant folding আর constant propagation

Constant folding সবচেয়ে পুরোনো আর সহজ optimization: যে হিসাবের সব operand compile-এর সময়েই জানা, তা তখনই করে ফল বসানো। let base = 50 + 10;-এর IR t1 = const 50; t2 = const 10; base = t1 + t2; fold করলে base = const 60. তবে Haat IR-এ operand নাম, তাই t1 যে 50, তা জানতে হয় নামটির মান খুঁজে। এটিই constant propagation: কোন বিন্দুতে কোন নামের মান নিশ্চিতভাবে একটি ধ্রুবক।

প্রশ্নটি forward আর must: সব পথে একই ধ্রুবক এলে তবেই ধ্রুবক। পর্ব ৬৪-এর ছবি ৬৪.১-এর constant lattice এখানে কাজে লাগে: প্রতিটি নামের মান ⊤ (“এখনো দেখা যায়নি”), একটি ধ্রুবক, বা ⊥ (“ধ্রুবক নয়”); দুই পথের meet: একই ধ্রুবক হলে সেটি, আলাদা হলে ⊥. haat_opt.py এটিকে পর্ব ৬৪-এর Problem হিসেবে লেখে, আর solve হুবহু সেই worklist solver:

def value(ins, env):                             # env-এ নির্দেশটির ফল: ধ্রুবক, বা BOT
    a = [env.get(x, BOT) if local(x) else BOT for x in ins.args]
    if ins.kind == "const": return ins.sym
    if ins.kind not in ("copy", "bin", "un") or any(v is BOT for v in a): return BOT
    if ins.kind == "copy": return a[0]
    if ins.kind == "un": return wrap(-a[0]) if ins.sym == "-" else not a[0]
    if ins.sym in ("/", "%") and a[1] == 0: return BOT     # runtime error-টি চলার সময়ই হতে হবে: fold নয়
    return arith(ins.sym, a[0], a[1], 0, 0)               # ৬৪-bit wrap, C-ধাঁচের / আর % (সিদ্ধান্ত ১৩)

def cmeet(x, y):                                 # None = ⊤ (এখনো পৌঁছায়নি); নাম না থাকলে ⊥ ধরা হয়
    if x is None or y is None: return y if x is None else x
    return {k: x[k] if k in x and k in y and same(x[k], y[k]) else BOT for k in x.keys() | y.keys()}
def cstep(ins, x, b, i):
    if x is None or not local(ins.dst): return x
    return {**x, ins.dst: value(ins, x)}
CONSTANTS = Problem("constants", True, cmeet, lambda fn: None, lambda fn: {p: BOT for p in fn.params}, cstep)

def fold(fn):                                    # constant propagation + folding; ধ্রুবক শর্তের branch -> jump
    pts, n = points(CONSTANTS, fn, solve(CONSTANTS, fn)), 0
    for b, body in fn.blocks.items():
        for i, ins in enumerate(body):
            env = pts[b, i][0]
            if env is None: continue             # পৌঁছানো যায় না: cleanup মুছবে
            if ins.kind == "branch" and (v := env.get(ins.args[0], BOT)) is not BOT:     # শর্ত ধ্রুবক
                body[i] = Ins("jump", targets=[ins.targets[0] if v else ins.targets[1]]); n += 1
            elif ins.kind in ("bin", "un") and local(ins.dst) and (v := value(ins, env)) is not BOT:
                body[i] = Ins("const", ins.dst, sym=v); n += 1
    return n + cleanup(fn)

দুটি খুঁটিনাটি লক্ষ করুন। value ভাগের ভাজক 0 দেখলে BOT দেয়: হিসাবটি এখন না করে চলার সময়ের জন্য রেখে দেয়, যাতে error ঠিক সেই line:col-এ হয়। আর হিসাব হয় haat_front.py-র arith দিয়ে, যেটি run_ir-ও ব্যবহার করে, তাই compile-এর সময়ের ফল চলার সময়ের ফলের সঙ্গে wrap আর C-ধাঁচের / %-সহ মিলবেই।

ধ্রুবক জানা থাকলে শর্তও জানা যায়: branch c B1 B2-এ c ধ্রুবক হলে নির্দেশটি jump হয়ে যায়, আর অন্য শাখার block-এ আর কোনো পথে পৌঁছানো যায় না (unreachable). cleanup সেই block মোছে, শুধু-jump-ওয়ালা block এড়িয়ে লক্ষ্য সরাসরি বসায় (jump threading), আর একমাত্র-পথের দুটি block জোড়া দেয়। bill-এ পুরো ফল আসে দুইবার solve করার পরে; কেন, তা stepper-এ দেখুন।

1B0: express = const false2    t1 = const 503    t2 = const 104    base = t1 + t25    fee = base6    branch express B1 B27B1: t3 = const 28    fee = base * t39B2: p = qty * unit10    …11    t10 = t9 + fee
ধ্রুবকের মান
কোথায়
express
base
fee
  1. শুরু. solve(CONSTANTS, fn) B0 থেকে শুরু করে; parameter qty আর unit ⊥, কারণ তাদের মান বাইরে থেকে আসে।
  2. B0-এর শেষ. express = false; base = t1 + t2-এর মান 50 + 10 = 60; fee = base একটি copy, তাই fee-ও 60.
  3. B1. express সবসময় false, তবু solver B1-কে হিসাব করে, কারণ পর্ব ৬৪-এর framework CFG-র প্রতিটি edge সম্ভব বলে ধরে। B1-এর শেষে fee = 60 × 2 = 120.
  4. B2-তে মিলন. দুটি predecessor: base দুই পথেই 60, তাই 60; fee একটিতে 60, অন্যটিতে 120, তাই ⊥. এই রাউন্ডে মোট ৩টি block-visit.
  5. Fold. base = t1 + t2 হয় base = const 60; branch-এর শর্ত express ধ্রুবক false, তাই branch express B1 B2 হয় jump B2.
  6. Cleanup. B1-এ আর কোনো পথ নেই, তাই মোছা হয়; B2-তে আসার একমাত্র পথ B0, তাই দুটি জোড়া লেগে একটি block. Fold-এর হিসাবে মোট ৫টি বদল।
  7. আবার solve. এখন একটিই block (১টি visit), আর fee = 60 নিশ্চিত। পরের copy propagation t10 = t9 + fee-কে t10 = t9 + base বানায়। প্রথম রাউন্ডে fee ⊥ ছিল শুধু একটি অগম্য পথের জন্য।

শেষ ধাপটিই আরও চতুর একটি অ্যালগরিদমের প্রেরণা। Mark Wegman আর Kenneth Zadeck-এর sparse conditional constant propagation (SCCP; ১৯৯১ সালের প্রবন্ধে প্রকাশিত) edge-গুলোকেও আশাবাদীভাবে “চলে না” ধরে শুরু করে, আর একটি edge চালু করে শুধু তখন, যখন তার branch-এর শর্ত সেদিকে যেতে পারে। তাই অগম্য B1-এর 120 কখনো meet-এ ঢোকে না, আর fee = 60 এক রাউন্ডেই আসে। “Sparse” কারণ এটি SSA-র def-use edge ধরে চলে (পর্ব ৬৩)।

৩ · Algebraic simplification আর তার ফাঁদ

সব operand না জানলেও কিছু হিসাব সহজ হয়: x + 0 আসলে x, x * 0 আসলে 0. এর নাম algebraic simplification. স্কুলের বীজগণিতে যা সত্য, যন্ত্রের সংখ্যায় তা সবসময় সত্য নয়, তাই প্রতিটি নিয়ম Haat-এর আসল semantics দিয়ে যাচাই করতে হয়। নিচের টেবিলের প্রতিটি সারি এমন যাচাইয়ের ফল:

নিয়মHaat Int-একারণ
x + 0 → x, x * 1 → x, x / 1 → xসঠিকwrap-এও একই ফল; ভাজক 1 কখনো শূন্য নয়
x * 0 → 0, x - x → 0, x % 1 → 0সঠিকx একটি নাম, তার হিসাব আগেই হয়ে গেছে; কোনো side effect নেই
x == x → trueসঠিকHaat-এ NaN নেই; IEEE 754 float-এ NaN == NaN মিথ্যা (পর্ব ২০)
(x + 1) - 1 → xসঠিক৬৪-bit wrap মানে 264-এর ভাগশেষের হিসাব, যেখানে যোগ-বিয়োগ সাধারণ নিয়ম মানে
x / x → 1ভুলx = 0 হলে runtime error হওয়ার কথা
x + 1 > x → trueভুলx = 9223372036854775807 হলে x + 1 wrap করে সবচেয়ে ছোট Int
(x * 5) / 100 → x / 20ভুলx * 5 wrap করলে দুটি আলাদা (অনুশীলন ২)
x + y → y + xসব type-এ নয়Str-এ + জোড়া দেয়; IR-এ type নেই, তাই LVN +-কে বিনিময়যোগ্য ধরে না

C-তে এই হিসাব আলাদা, আর পার্থক্যটি শিক্ষণীয়। C-তে signed overflow আর শূন্য দিয়ে ভাগ undefined behavior, অর্থাৎ standard বলে “এমন হয় না”; তাই compiler ধরে নিতে পারে x কখনো শূন্য নয়, আর x + 1 কখনো overflow করে না। নিচে bill-এর C রূপ আর দুটি এক-লাইনের function, PyPI-র ziglang 0.17.1-এর ভেতরের Clang 22.1.8 দিয়ে -O2 -S -emit-llvm (x86-64 Linux target, -fno-sanitize=undefined), লেখকের lab-এ সত্যিকারের run; LLVM IR থেকে শুধু function-এর দেহ রাখা:

long ratio(long x) { return x / x; }
int grows(long x) { return x + 1 > x; }

define noundef i64 @ratio(i64 noundef %x) {
entry:
  ret i64 1
}
define noundef i32 @grows(i64 noundef %x) {
entry:
  ret i32 1
}

Clang-এর কাছে দুটিই বৈধ: C-র নিয়মে x = 0 বা x = LONG_MAX-এর ক্ষেত্রটি UB, তাই “যা খুশি” করা যায়, আর 1 ফেরত দেওয়াও তার একটি। Haat UB রাখেনি, প্রতিটি হিসাবের ফল নির্ধারিত (সিদ্ধান্ত ১৩ আর ২৬), তাই Haat-এর optimizer-এর হাত বাঁধা। বিনিময়ে Haat programmer কখনো অবাক হন না; পর্ব ০৬-এর নিরাপত্তা বনাম গতির আপস এখানে নির্দেশ-স্তরে দেখা যায়। অংশ ৮-এ দেখবেন, ঠিক এই x / x → 1 নিয়ম জেনেশুনে বসালে আমাদের পরীক্ষা কী বলে।

৪ · Copy propagation আর common subexpression elimination

Fold-এর পরে bill-এ পড়ে থাকে fee = base, একটি copy. Copy propagation বলে: x = y-এর পরে যেখানে x পড়া হয়, সেখানে y পড়ুন, যদি সেই বিন্দুতে পৌঁছানোর প্রতিটি পথে copy-টি হয়েছে আর তার পরে x বা y কোনোটি আর লেখা হয়নি। এটিও পর্ব ৬৪-এর ছাঁচের একটি forward, must প্রশ্ন (“available copies”): মান হলো (x, y) জোড়ার set, meet ∩, ⊤ = function-এর সব copy. copy_prop উত্তর থেকে প্রতিটি নির্দেশের operand বদলায়; copy-টি নিজে থাকে, কিন্তু x আর কেউ না পড়লে পরে DCE সেটি মোছে।

এবার bill-এর let vat = qty * unit * 5 / 100;. Lowering দুবার qty * unit হিসাব করে: একবার p-এর জন্য, একবার vat-এর ভেতরে। একই হিসাব দ্বিতীয়বার না করে আগের ফল নেওয়ার নাম common subexpression elimination (CSE). Block-এর ভেতরে এর ধ্রুপদী অ্যালগরিদম local value numbering (LVN):

অ্যালগরিদম ৬৫.২ — local value numbering, একটি block-এ
  1. প্রতিটি নামের একটি value number (VN): একই VN মানে চলার সময় একই মান। block-এর বাইরে থেকে আসা নাম প্রথমবার দেখা হলে নতুন VN পায়।
  2. প্রতিটি d = a op b-এর জন্য একটি key: (op, VN(a), VN(b)); *, ==, !=-এ দুই VN সাজিয়ে, যাতে y * x আর x * y একই key পায়। const k-এর key (const, k-এর type, k).
  3. key আগে দেখা হলে, আর সেই VN এখনো কোনো নামে আছে (নামটি পরে নতুন করে লেখা হয়নি), তাহলে নির্দেশটিকে d = সেই নাম copy বানান, আর d পায় সেই VN.
  4. নইলে d পায় নতুন VN, আর key-টি টেবিলে ওঠে। d = a copy হলে d পায় a-এর VN.
1p = qty * unit2t4 = qty * unit3t5 = const 54t6 = t4 * t55t7 = const 1006vat = t6 / t77t8 = const 78lucky = p % t89avg = p / qty10t9 = p + vat11t10 = t9 + fee
Value number
key
নতুন VN
  1. p = qty * unit. qty আর unit block-এর বাইরে থেকে আসে, তাই VN 1 আর 2. key (*, 1, 2) নতুন, p পায় VN 3.
  2. t4 = qty * unit. একই key (*, 1, 2), আর VN 3 এখনো p-তে আছে। নির্দেশটি হয় t4 = p, t4-এর VN 3. পরে copy propagation t6 = t4 * t5-কে t6 = p * t5 বানাবে, আর t4 মৃত হবে।
  3. t5 = const 5. key (const, 5) নতুন, VN 4.
  4. t6 = t4 * t5. t4-এর VN 3, তাই key (*, 3, 4): LVN নাম নয়, মান দেখে। নতুন, VN 5.
  5. t7 আর vat = t6 / t7. VN 6 আর 7. ভাগও CSE হতে পারে: একই block-এ আগের ভাগটি চলেছে আর error হয়নি, তাই একই মানের দ্বিতীয় ভাগও error দেবে না।
  6. t8 আর lucky = p % t8. VN 8 আর 9; key (%, 3, 8).
  7. avg = p / qty আর t9 = p + vat. key (/, 3, 1) আর (+, 3, 7), দুটিই নতুন: VN 10 আর 11.
  8. t10 = t9 + fee. fee এই block-এ প্রথম দেখা, VN 12; t10 পায় 13. lvn-এর ফল: এই block-এ ১টি বদল। এখানে + সাজানো হয় না, কারণ IR জানে না operand-দুটি Int না Str.

LVN-এর সীমা block-এর দেয়াল। দুটি block-এ একই হিসাব থাকলে লাগে global CSE, আর তার প্রশ্নটি পর্ব ৬৪-এর available expressions: বিন্দু p-তে a op b available হলে পৌঁছানোর প্রতিটি পথে এটি হিসাব হয়েছে, আর তার পরে a বা b বদলায়নি। তবে ফলটি কোন নামে আছে? পথভেদে আলাদা নামে থাকতে পারে। gcse তাই প্রতিটি এমন expression-এর জন্য একটি নতুন temp u নেয়: যেখানে expression হিসাব হয়, d = a op b হয় u = a op b; d = u; আর যেখানে এটি available, সেখানে d = u. Must (∩) কেন? একটি পথেও হিসাব না হলে সেই পথে u-তে বাসি মান থাকবে।

একটি জিনিস CSE কখনো মেলায় না: call. bazar.haat-এর <main>-এ price(2, 520) দুবার ডাকা হয়; LVN দুই call-এর argument মেলায় (t4 = const 2 আর t1 = const 2 একই VN), কিন্তু call দুটি থাকে, কারণ IR জানে না price ছাপে কি না বা global বদলায় কি না। সেটি জানতে function-এর ভেতরে তাকাতে হয়, যা interprocedural (পর্ব ৬৭)।

৫ · Dead code elimination — liveness দিয়ে, আর এক ধাপে mark–sweep দিয়ে

পর্ব ৬৪ dead store খুঁজেছিল: লেখা মান, যা পরে কোনো পথে পড়া হয় না। সেখানে শুধু তালিকা দেওয়া হয়েছিল, কারণ “মান লাগবে না” আর “নির্দেশটি মোছা নিরাপদ” এক কথা নয়। Dead code elimination (DCE) দুটি প্রশ্ন একসঙ্গে মেলায়। একটি নির্দেশ জরুরি (মোছা যায় না), যদি সে:

  • print, call, return, jump বা branch হয় (দেখা যায় এমন আচরণ বা control flow);
  • একটি global @x-এ লেখে, বা @x পড়ে (পড়াতেও 'x' is not initialized yet error হতে পারে, সিদ্ধান্ত ১৮);
  • / বা %, যার ভাজক নিশ্চিত অশূন্য ধ্রুবক নয়।

Liveness দিয়ে DCE চালালে একটি সমস্যা: পর্ব ৬৪-এর cart_total-এ tries = const 0; t3 = const 1; tries = tries + t3. প্রথম রাউন্ডে শুধু শেষ লেখাটি মৃত; সেটি মোছার পরে আবার liveness চালালে বাকি দুটি মৃত হয়। এমন নাম, যার মান শুধু মৃত হিসাবে যায়, তাকে বলে faint. লেখকের lab-এ সত্যিকারের run: liveness-ভিত্তিক DCE প্রথম রাউন্ডে ৪টি, দ্বিতীয়তে ২টি নির্দেশ মোছে। ভালো উপায় উল্টো দিক থেকে ভাবা, garbage collector-এর মতো (পর্ব ৭৫): জীবিত কী, তা প্রমাণ করুন; বাকি সব মৃত।

অ্যালগরিদম ৬৫.৩ — mark–sweep DCE
  1. Mark-এর শুরু: প্রতিটি জরুরি নির্দেশ চিহ্নিত, আর একটি কাজের তালিকায়।
  2. তালিকা থেকে একটি নির্দেশ তুলুন; সে যে নাম পড়ে, তার প্রতিটির জন্য পর্ব ৬৪-এর use-def chain (ud_chains) থেকে যে definition-গুলো সেখানে পৌঁছায়, সেগুলো চিহ্ন দিয়ে তালিকায় তুলুন।
  3. তালিকা খালি হলে sweep: চিহ্নহীন প্রতিটি নির্দেশ মুছুন। একবারেই faint শিকলসহ সব মৃত কোড যায়।
1B0: vat = const 152    count = const 03    subtotal = const 04    jump B15B1: t1 = count < items6    branch t1 B2 B37B2: subtotal = subtotal + unit8    t2 = const 19    count = count + t210    jump B111B3: note = const "new"12    note = const "checked"13    tries = const 014    t3 = const 115    tries = tries + t316    return subtotal
Mark–sweep
ধাপ
চিহ্নিত
  1. জরুরি নির্দেশ. তিনটি block-এর শেষের jump/branch আর return subtotal: মোট ৪টি চিহ্নিত।
  2. return subtotal-এর use. subtotal-এর যে দুটি definition B3-এ পৌঁছায়: B0-এর subtotal = const 0 আর loop-এর subtotal = subtotal + unit. দ্বিতীয়টি নিজে subtotal আর unit পড়ে, কিন্তু subtotal-এর উৎস আগেই চিহ্নিত, unit একটি parameter.
  3. branch t1-এর use. t1-এর definition t1 = count < items; সেটি count পড়ে, যার দুটি definition (B0-এর const 0 আর B2-এর যোগ) চিহ্ন পায়; যোগটি t2 পড়ে, তাই t2 = const 1-ও। এখন ১০টি চিহ্নিত।
  4. তালিকা খালি. কোনো চিহ্নিত নির্দেশ vat, note, tries বা t3 পড়ে না, তাই সেগুলোর কাছে কেউ পৌঁছায়নি।
  5. Sweep. ১৬টির মধ্যে চিহ্নহীন ৬টি এক ধাপে মোছা: vat, দুটি note, দুটি tries আর t3. Liveness-এর দুই রাউন্ডের ৪ + ২-এর সঙ্গে হুবহু মেলে, কিন্তু একবারে। B3-এ থাকে শুধু return subtotal.

bill-এ DCE ৭টি নির্দেশ মোছে, আর একটি রাখে। lucky = p % t8 মোছা যায়, কারণ constant propagation জানে t8 = 7, অশূন্য; avg = p / qty থাকে, কারণ qty-র মান অজানা। এই একটি বাছাই-ই অংশ ১-এর 10:17: runtime error-কে বাঁচিয়ে রাখে।

Error-এর অবস্থান কি বদলাতে পারে? এই পর্বের কোনো pass একটি ভাগকে সরায় না, নতুন জায়গায় বসায় না, বা আগে-পরে করে না; ভাগের নির্দেশ তার pos (line, col) নিয়ে যেখানে ছিল সেখানেই চলে, শুধু তার আশপাশের নিরীহ নির্দেশ কমে। তাই বার্তা আর line:col হুবহু থাকে, যা অংশ ৮-এর পরীক্ষায় ৩২৬টি error-এ থামা program-এ মিলেছে। পর্ব ৬৬-এর loop-invariant code motion একটি ভাগকে loop-এর বাইরে আনতে চাইলে এই প্রশ্ন সত্যিই ওঠে; সেখানে নিয়মটি আরও কড়া।

৬ · Pass pipeline আর pass-এর ক্রম

প্রতিটি pass একা সামান্য করে; শক্তি আসে একসঙ্গে। Fold একটি copy তৈরি করে, copy propagation সেটিকে অপ্রয়োজনীয় করে, DCE মোছে, আর মোছার পরে নতুন ধ্রুবক শর্ত দেখা দিতে পারে। haat_opt.py-র প্রতিটি pass একটি function, যা fn-কে জায়গায় বদলায় আর কয়টি বদল হলো ফেরত দেয়; optimize পুরো তালিকা ঘোরায়, যতক্ষণ না একটি পুরো রাউন্ডে কিছুই বদলায় (বড়জোর ১০ রাউন্ড):

PIPELINE = [fold, simplify, copy_prop, lvn, gcse, copy_prop, dce, cleanup]
def optimize(fn, passes=PIPELINE, log=None, rounds=10):      # কোনো pass কিছু না বদলানো পর্যন্ত, বড়জোর rounds বার
    for r in range(rounds):
        total = 0
        for p in passes:
            k = p(fn); total += k
            if log is not None and k: log.append((r + 1, p.__name__, k, size(fn)))
        if not total: break
    return fn
def size(fn): return sum(len(body) for body in fn.blocks.values())
def optimize_module(mod, passes=PIPELINE):
    for fn in mod.funcs.values(): optimize(fn, passes)
    return mod
সহায়ক module haat_opt.py পুরোটা দেখুন (এই পর্বের সব নতুন কোড; পর্ব ৬৬ আর ৬৭ এটি হুবহু নেবে)
# haat_opt.py — পর্ব ৬৫: Haat IR-এর CFG-র ওপর optimization pass: constant folding/propagation, algebraic
# simplification, copy propagation, CSE (local value numbering আর available expressions দিয়ে global), DCE, CFG cleanup.
# লাগে পর্ব ৬২-এর haat_ir.py আর পর্ব ৬৪-এর haat_dfa.py, দুটিই হুবহু। প্রতিটি pass fn বদলায়, ফেরত দেয় কয়টি বদল।
# স্থায়ী নিয়ম: যে / বা % শূন্য দিয়ে ভাগ করতে পারে, তা কখনো fold, মোছা বা সরানো হয় না; call আর print-এর ক্রম অটুট।
from haat_dfa import *

class Bot:                                       # constant-এর lattice-এর ⊥: “ধ্রুবক নয়”
    def __repr__(self): return "⊥"
BOT = Bot()
def same(a, b): return type(a) is type(b) and a == b      # True আর 1 আলাদা (Python-এ True == 1)
def local(x): return x is not None and x[0] != "@"

def value(ins, env):                             # env-এ নির্দেশটির ফল: ধ্রুবক, বা BOT
    a = [env.get(x, BOT) if local(x) else BOT for x in ins.args]
    if ins.kind == "const": return ins.sym
    if ins.kind not in ("copy", "bin", "un") or any(v is BOT for v in a): return BOT
    if ins.kind == "copy": return a[0]
    if ins.kind == "un": return wrap(-a[0]) if ins.sym == "-" else not a[0]
    if ins.sym in ("/", "%") and a[1] == 0: return BOT     # runtime error-টি চলার সময়ই হতে হবে: fold নয়
    return arith(ins.sym, a[0], a[1], 0, 0)               # ৬৪-bit wrap, C-ধাঁচের / আর % (সিদ্ধান্ত ১৩)

def cmeet(x, y):                                 # None = ⊤ (এখনো পৌঁছায়নি); নাম না থাকলে ⊥ ধরা হয়
    if x is None or y is None: return y if x is None else x
    return {k: x[k] if k in x and k in y and same(x[k], y[k]) else BOT for k in x.keys() | y.keys()}
def cstep(ins, x, b, i):
    if x is None or not local(ins.dst): return x
    return {**x, ins.dst: value(ins, x)}
CONSTANTS = Problem("constants", True, cmeet, lambda fn: None, lambda fn: {p: BOT for p in fn.params}, cstep)

def fold(fn):                                    # constant propagation + folding; ধ্রুবক শর্তের branch -> jump
    pts, n = points(CONSTANTS, fn, solve(CONSTANTS, fn)), 0
    for b, body in fn.blocks.items():
        for i, ins in enumerate(body):
            env = pts[b, i][0]
            if env is None: continue             # পৌঁছানো যায় না: cleanup মুছবে
            if ins.kind == "branch" and (v := env.get(ins.args[0], BOT)) is not BOT:     # শর্ত ধ্রুবক
                body[i] = Ins("jump", targets=[ins.targets[0] if v else ins.targets[1]]); n += 1
            elif ins.kind in ("bin", "un") and local(ins.dst) and (v := value(ins, env)) is not BOT:
                body[i] = Ins("const", ins.dst, sym=v); n += 1
    return n + cleanup(fn)

def simplify(fn, wrong=False):                   # algebraic simplification (wrong=True: ভুল নিয়ম x / x -> 1-ও)
    pts, n = points(CONSTANTS, fn, solve(CONSTANTS, fn)), 0
    for b, body in fn.blocks.items():
        for i, ins in enumerate(body):
            env = pts[b, i][0]
            if ins.kind != "bin" or env is None: continue
            op, (x, y), d = ins.sym, ins.args, ins.dst
            k = lambda z: env[z] if local(z) and type(env.get(z)) is int else None   # Int ধ্রুবক, নইলে None
            new = None
            if op in ("+", "-") and k(y) == 0 or op in ("*", "/") and k(y) == 1:
                new = Ins("copy", d, [x])                                  # x + 0, x - 0, x * 1, x / 1
            elif op == "+" and k(x) == 0 or op == "*" and k(x) == 1:
                new = Ins("copy", d, [y])                                  # 0 + y, 1 * y
            elif op == "*" and 0 in (k(x), k(y)) or op == "%" and k(y) in (1, -1) or op == "-" and x == y:
                new = Ins("const", d, sym=0)                               # x * 0, x % 1, x - x (wrap-এও সত্য)
            elif op in ("==", "<=", ">=") and x == y:
                new = Ins("const", d, sym=True)                            # x == x: Haat-এ NaN নেই
            elif wrong and op == "/" and x == y:
                new = Ins("const", d, sym=1)                               # ভুল! x = 0 হলে error হারিয়ে যায়
            if new: body[i] = new; n += 1
    return n

def copy_step(ins, x, b, i):                     # available copies: (d, s) মানে এখানে d-তে s-এর মানই আছে
    d = set(defs(ins)); x = frozenset(c for c in x if not d & set(c))
    return x | {(ins.dst, ins.args[0])} if ins.kind == "copy" and local(ins.dst) and local(ins.args[0]) else x
COPIES = Problem("available copies", True, lambda x, y: x & y,
                 lambda fn: frozenset((i.dst, i.args[0]) for body in fn.blocks.values() for i in body
                                      if i.kind == "copy" and local(i.dst) and local(i.args[0])),
                 lambda fn: frozenset(), copy_step)

def copy_prop(fn):                               # x = y-এর পরে x-এর ব্যবহার -> y, যদি সব পথে x আর y অপরিবর্তিত
    pts, n = points(COPIES, fn, solve(COPIES, fn)), 0
    for b, body in fn.blocks.items():
        for i, ins in enumerate(body):
            m = dict(pts[b, i][0])
            new = [m.get(a, a) if local(a) else a for a in ins.args]
            if new != ins.args: ins.args = new; n += 1
    return n

COMMUTATIVE = {"*", "==", "!="}                 # + নয়: Str-এ "a" + "b" আর "b" + "a" আলাদা
def lvn(fn, trace=None):                         # local value numbering: প্রতিটি block আলাদা
    n = 0
    for b, body in fn.blocks.items():
        vn, table, fresh = {}, {}, iter(range(1, 10**9))
        def num(x):                              # নামের value number; block-এর বাইরে থেকে আসা নাম নতুন নম্বর পায়
            if local(x) and x not in vn: vn[x] = next(fresh)
            return vn[x] if local(x) else ("@", x)
        for i, ins in enumerate(body):
            key = None
            if local(ins.dst) and ins.kind == "const": key = ("const", type(ins.sym), ins.sym)
            elif local(ins.dst) and ins.kind in ("bin", "un"):
                ops = [num(a) for a in ins.args]
                key = (ins.sym, *(sorted(ops) if ins.sym in COMMUTATIVE else ops))
            if ins.kind == "copy" and local(ins.dst) and local(ins.args[0]): v = num(ins.args[0])
            elif key in table and (h := next((x for x in vn if vn[x] == table[key] and x != ins.dst), None)):
                v = table[key]                   # একই মান আগেই আছে; const শুধু temp-এ temp হলে copy হয়
                if ins.kind != "const" or is_temp(ins.dst) and is_temp(h): body[i] = Ins("copy", ins.dst, [h]); n += 1
            else:
                v = next(fresh)
                if key: table[key] = v
            if local(ins.dst): vn[ins.dst] = v
            if trace is not None: trace.append((b, str(ins), str(body[i]), dict(vn)))
    return n

def gcse(fn):                                    # global CSE: পৌঁছানোর সব পথে আগেই হিসাব করা expression
    _, pts = analyze(fn, AVAILABLE)
    red = {(b, i) for (b, i), (inn, _) in pts.items() if (e := expr_of(fn.blocks[b][i])) and e in inn}
    if not red: return 0
    exprs = {expr_of(fn.blocks[b][i]) for b, i in red}
    top = max([int(x[1:]) for body in fn.blocks.values() for ins in body for x in [ins.dst, *ins.args] if x and is_temp(x)], default=0)
    u = {e: f"t{top + k + 1}" for k, e in enumerate(sorted(exprs, key=str))}   # প্রতিটি expression-এর নতুন temp
    for b, body in fn.blocks.items():
        out = []
        for i, ins in enumerate(body):
            e = expr_of(ins)
            if (b, i) in red: out.append(Ins("copy", ins.dst, [u[e]]))
            elif e in u: out += [replace(ins, dst=u[e], args=list(ins.args)), Ins("copy", ins.dst, [u[e]])]
            else: out.append(ins)
        fn.blocks[b] = out
    return len(red)

def nonzero(env, x): return local(x) and type(env.get(x, BOT)) is int and env[x] != 0   # নিশ্চিত অশূন্য Int
def dce(fn):                                     # mark–sweep: জরুরি নির্দেশ থেকে use-def chain ধরে পেছনে চিহ্ন
    env = points(CONSTANTS, fn, solve(CONSTANTS, fn))
    def vital(b, i, ins):                        # side effect আছে, বা runtime error হতে পারে
        return (ins.kind in ("print", "call", "return", "jump", "branch") or not local(ins.dst)
                or any(not local(a) for a in ins.args)                       # @x পড়া: “not initialized yet”
                or ins.kind == "bin" and ins.sym in "/%" and not nonzero(env[b, i][0] or {}, ins.args[1]))
    ud, work = ud_chains(fn), [(b, i) for b, body in fn.blocks.items() for i, ins in enumerate(body) if vital(b, i, ins)]
    live = set(work)
    while work:
        b, i = work.pop()
        for x in uses(fn.blocks[b][i]):
            for _, at in ud[b, i, x]:
                if at != "in" and (d := (at.split(".")[0], int(at.split(".")[1]))) not in live:
                    live.add(d); work.append(d)
    n = sum(len(body) for body in fn.blocks.values()) - len(live)
    fn.blocks = {b: [ins for i, ins in enumerate(body) if (b, i) in live] for b, body in fn.blocks.items()}
    return n

def cleanup(fn):                                 # পৌঁছানো যায় না এমন block মোছা, jump-এর শিকল ছোট, block জোড়া, নতুন নাম
    n, reach, stack = 0, {"B0"}, ["B0"]
    while stack:
        for s in succs(fn, stack.pop()):
            if s not in reach: reach.add(s); stack.append(s)
    n += len(fn.blocks) - len(reach); fn.blocks = {b: v for b, v in fn.blocks.items() if b in reach}
    for b, body in fn.blocks.items():            # শুধু `jump C`-ওয়ালা block-এ যাওয়া মানে সরাসরি C-তে যাওয়া
        last = body[-1]
        for k, t in enumerate(last.targets):
            seen, c = {t}, t
            while c != "B0" and len(fn.blocks[c]) == 1 and fn.blocks[c][0].kind == "jump" and fn.blocks[c][0].targets[0] not in seen:
                c = fn.blocks[c][0].targets[0]; seen.add(c)
            if c != t: last.targets[k] = c; n += 1
        if last.kind == "branch" and last.targets[0] == last.targets[1]: body[-1] = Ins("jump", targets=[last.targets[0]]); n += 1
    changed = True
    while changed:                               # A-র শেষে jump B, আর B-তে আসার একমাত্র পথ A: B-কে A-তে জোড়া
        changed, P = False, preds(fn)
        for a, body in fn.blocks.items():
            t = body[-1].targets[0] if body[-1].kind == "jump" else None
            if t and t != "B0" and t != a and P[t] == [a]:
                fn.blocks[a] = body[:-1] + fn.blocks.pop(t); n += 1; changed = True; break
    names = {b: f"B{k}" for k, b in enumerate(fn.blocks)}    # বাকি block-গুলোর নতুন নাম B0, B1 …, আগের ক্রমে
    fn.blocks = {names[b]: [replace(ins, args=list(ins.args), targets=[names[t] for t in ins.targets])
                            for ins in body] for b, body in fn.blocks.items()}
    return n

PIPELINE = [fold, simplify, copy_prop, lvn, gcse, copy_prop, dce, cleanup]
def optimize(fn, passes=PIPELINE, log=None, rounds=10):      # কোনো pass কিছু না বদলানো পর্যন্ত, বড়জোর rounds বার
    for r in range(rounds):
        total = 0
        for p in passes:
            k = p(fn); total += k
            if log is not None and k: log.append((r + 1, p.__name__, k, size(fn)))
        if not total: break
    return fn
def size(fn): return sum(len(body) for body in fn.blocks.values())
def optimize_module(mod, passes=PIPELINE):
    for fn in mod.funcs.values(): optimize(fn, passes)
    return mod

এবার পুরো pipeline bill-এ। ব্লকটি আগে-পরে নির্দেশ গোনে, প্রতিটি pass-এর বদল দেখায়, আর ফলের আউটপুট reference-এর আসল আউটপুটের (bill.out) সঙ্গে মেলায়, error-এর লাইনসহ। run_ir error-এ থেমে যায় বলে চলা নির্দেশ গোনা হয় শুধু প্রথম call-ওয়ালা একটি কপিতে।

# ধাপ ১: bill-এর ওপর পুরো pipeline — কোন pass কী বদলাল, পরে IR কেমন, আর আউটপুট কি একই
from haat_opt import *                    # fold, simplify, copy_prop, lvn, gcse, dce, cleanup, optimize (+ ৬২, ৬৪)
src = open("bill.haat", encoding="utf-8").read()
want = open("bill.out", encoding="utf-8").read().split("\n")[:-1]   # reference `run`-এর আসল আউটপুট
mod = compile_ir(src)
fn = mod.funcs["bill"]
before = run_lines(mod)
print("আগে:", size(fn), "টি নির্দেশ,", len(fn.blocks), "টি block")
log = []
optimize(fn, log=log)
for rnd, name, changes, now in log:
    print(f"  রাউন্ড {rnd}: {name:9} {changes} বদল → {now} টি নির্দেশ")
print(show_ir(fn))
after = run_lines(mod)
print("reference:", want)
print("আগে == reference:", before == want, "· পরে == reference:", after == want)
one = compile_ir(src.replace("print(bill(0, 99));", ""))      # error-এ run_ir থামে, তাই গোনা শুধু bill(2, 520)
n0 = run_ir(one, out=lambda s: None)
optimize_module(one)
print("চলা নির্দেশ, শুধু bill(2, 520)-এর program:", n0, "→", run_ir(one, out=lambda s: None))

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

আগে: 21 টি নির্দেশ, 3 টি block
  রাউন্ড 1: fold      5 বদল → 17 টি নির্দেশ
  রাউন্ড 1: copy_prop 1 বদল → 17 টি নির্দেশ
  রাউন্ড 1: lvn       1 বদল → 17 টি নির্দেশ
  রাউন্ড 1: copy_prop 1 বদল → 17 টি নির্দেশ
  রাউন্ড 1: dce       7 বদল → 10 টি নির্দেশ
fn bill(qty, unit):
B0:
  base = const 60
  p = qty * unit
  t5 = const 5
  t6 = p * t5
  t7 = const 100
  vat = t6 / t7
  avg = p / qty
  t9 = p + vat
  t10 = t9 + base
  return t10
reference: ['1152', '10:17: runtime error: division by zero']
আগে == reference: True · পরে == reference: True
চলা নির্দেশ, শুধু bill(2, 520)-এর program: 24 → 16

প্রথম রাউন্ডেই সব কাজ, দ্বিতীয় রাউন্ডে কিছু বদলায় না, তাই থামা। fold-এর ৫টি বদল stepper-এর মতোই; copy propagation দুবার চলে (pipeline-এ এটি দুই জায়গায় আছে): প্রথমবার fee → base, দ্বিতীয়বার LVN-এর t4 = p-এর পরে t4 → p. DCE মোছে ৭টি: express, t1, t2, fee-র copy, t4, t8 আর lucky. থাকে ১০টি নির্দেশ, একটি block; avg = p / qty জায়গামতো। চলা নির্দেশ ২৪ থেকে ১৬. লক্ষ করুন, t6 = p * t5; vat = t6 / t7 অক্ষত: wrap-এর জন্য এটিকে p / 20 বানানো যায় না।

ছবি ৬৫.১ — bill-এর Haat IR, optimize-এর আগে আর পরে

২১টি নির্দেশ, ৩টি block → ১০টি নির্দেশ, ১টি block

bill in Haat IR before and after the optimization pipeline: 21 instructions in 3 blocks become 10 instructions in 1 block আগে: ৩টি block, ২১টি নির্দেশ B0: express = const false মুছল t1 = const 50 মুছল t2 = const 10 মুছল base = t1 + t2 fold fee = base মুছল branch express B1 B2 fold B1: t3 = const 2 অগম্য fee = base * t3 অগম্য jump B2 অগম্য B2: p = qty * unit t4 = qty * unit CSE t5 = const 5 t6 = t4 * t5 t7 = const 100 vat = t6 / t7 t8 = const 7 মুছল lucky = p % t8 মুছল avg = p / qty রাখা: ভাগ t9 = p + vat t10 = t9 + fee return t10 পরে: ১টি block, ১০টি নির্দেশ B0: base = const 60 fold p = qty * unit t5 = const 5 t6 = p * t5 t7 = const 100 vat = t6 / t7 avg = p / qty রাখা: ভাগ t9 = p + vat t10 = t9 + base return t10
ছবি ৬৫.১ — রঙে প্রতিটি নির্দেশের পরিণতি। সবুজ: fold হয়ে ধ্রুবক বা jump; ধূসর: অগম্য block B1; নীল: LVN-এ copy, পরে মৃত; লাল: DCE-তে মোছা; কমলা: avg = p / qty, মৃত হলেও ভাগের জন্য জরুরি। নিচে ফল, ব্লক ১-এর আউটপুটের সঙ্গে হুবহু।

ক্রম কেন গুরুত্বপূর্ণ, তা মাপা যায়। লেখকের lab-এ haat_gen.py-র ৩,০০০টি এলোমেলো program (seed 0–2999) দিয়ে, প্রতিটি সংস্করণের ফল আগের IR-এর আউটপুটের সঙ্গে মিলিয়ে (সব ক্ষেত্রে অমিল ০); “চলা নির্দেশ” গোনা হয়েছে error ছাড়া শেষ হওয়া program-এ (এখানে আটটি উদাহরণ নেই; অংশ ৮-এর মাপে সেগুলোও আছে, আর তাদের মধ্যে recursion.haat একাই প্রায় ১,৬৬,০০০ চলা নির্দেশ যোগ করে, যা optimizer প্রায় কমায়ই না, তাই সেখানে হার ১৬.৩%), সত্যিকারের run:

pipelineস্থির নির্দেশ কমচলা নির্দেশ কম
পুরো PIPELINE, fixpoint পর্যন্ত২২.৪%১৯.৯%
dce বাদ দিয়ে৬.০%১.১%
fold বাদ দিয়ে১০.৮%১২.৪%
gcse বাদ দিয়ে২২.৪%১৯.৯%
fold → copy → dce, একবার১৮.০%১৬.৬%
dce → copy → fold, একবার৮.৬%৬.৭%
দুটি ক্রমই, fixpoint পর্যন্ত১৯.৭%১৭.১%

তিনটি শিক্ষা। প্রথমত, DCE ছাড়া বাকি pass প্রায় কিছুই কমায় না: তারা নির্দেশকে সস্তা বা অপ্রয়োজনীয় করে, মোছে DCE. দ্বিতীয়ত, global CSE এই program-গুলোতে প্রায় কিছুই যোগ করে না (৩,০০০টিতে মোট ৪০টি বদল, LVN-এর ২২,৫৯৭টির পাশে): এলোমেলো program-এ block পেরোনো একই হিসাব কম, আর এটি একটি মাপা তথ্য, সাধারণ সত্য নয়। তৃতীয়ত, একবার চালালে ক্রম বিশাল পার্থক্য করে (১৮.০% বনাম ৮.৬%), কারণ DCE আগে চললে fold-এর তৈরি মৃত কোড মোছার কেউ থাকে না; fixpoint পর্যন্ত চালালে দুই ক্রম এখানে একই ফলে পৌঁছায়। একে বলে phase ordering problem: কোন pass কখন, কতবার, তা নিয়ে সাধারণ কোনো সেরা উত্তর নেই, আর বাস্তব compiler তাই একই pass অনেকবার রাখে।

বাস্তব compiler-এ এটি কেমন দেখায়? একই bill-এর C রূপ (long, express একটি int) Clang 22.1.8-এ -O2 -S -emit-llvm -mllvm -print-changed=quiet দিয়ে চালানো হলো, যা শুধু সেই pass-গুলোর পরের IR দেখায়, যারা কিছু বদলেছে; লেখকের lab-এ সত্যিকারের run, প্রতিটি ধাপের সারাংশ:

LLVM passbill-এ যা বদলাল
SROAPasslocal variable-এর memory সরিয়ে SSA মান, fee-র জন্য একটি phi (পর্ব ৬৩-এর mem2reg-এর আত্মীয়)
EarlyCSEPassদ্বিতীয় qty * unit মোছা (CSE); 60 * 2 fold করে 120; অব্যবহৃত srem আর p / qty-এর sdiv মোছা
IPSCCPPassbranch-এর শর্ত false, তাই phi = 60; অগম্য শাখা বাদ (SCCP)
InstCombinePassmul nsw ... 5 আর sdiv ... 100 মিলে sdiv %mul1, 20
SimplifyCFGPass, ReassociatePassদুটি block জোড়া; যোগের ক্রম বদলে 60 আগে

-O2-এর শেষ ফল (একই run):

define range(i64 -9223372036854775748, -9223372036854775808) i64 @bill(i64 noundef %qty, i64 noundef %unit) {
entry:
  %mul1 = mul nsw i64 %unit, %qty
  %div = sdiv i64 %mul1, 20
  %add = add i64 %mul1, 60
  %add5 = add i64 %add, %div
  ret i64 %add5
}

আমাদের pipeline-এর মতো একই কাজ, শুধু দুটি জায়গায় C-র UB-র সুবিধা নিয়ে: p / qty মোছা (C-তে qty = 0 হলে UB, তাই error রাখার দায় নেই) আর / 20 (nsw মানে “signed overflow হবে না”, তাই wrap-এর হিসাব লাগে না)। Haat-এর জন্য দুটিই ভুল হতো: bill(0, 99) error-এর বদলে 60 ছাপত। x86-64 assembly-তে (-S, একই run) ২০ দিয়ে ভাগটিও আর ভাগ নয়: movabsq $7378697629483820647 দিয়ে গুণ আর shift, একটি strength reduction. আর -Rpass=.* এই ফাইলে একটি remark-ও দেয়নি, কারণ CSE বা InstCombine-এর মতো pass remark লেখে না; -Rpass-missed=.* দিয়েছে মাত্র দুটি (SLP vectorizer আর register allocator). Remark সব কাজের হিসাব নয়।

৭ · Peephole optimization — ছোট জানালা, চেনা নকশা

এ পর্যন্ত প্রতিটি pass আগে একটি বিশ্লেষণ চালিয়েছে। Peephole optimization উল্টো পথে হাঁটে: কোনো বিশ্লেষণ নয়, শুধু পরপর দুই-তিনটি নির্দেশের একটি ছোট জানালা, আর চেনা নকশার একটি তালিকা। দোকানের হিসাবের খাতায় পরপর “+৫০” আর “−৫০” দেখলে দুটিই কেটে দেওয়ার মতো, পুরো খাতা না পড়েই। William McKeeman-এর ১৯৬৫ সালের একটি ছোট প্রবন্ধে নামটি আসে বলে প্রচলিত ধারণা। কৌশলটি সস্তা, তাই প্রায় সব compiler-এর শেষ ধাপে, এমনকি assembly-স্তরেও, এর কোনো রূপ থাকে।

পর্ব ৫৮-এর stack bytecode-এ এটি সবচেয়ে সহজে দেখা যায়, কারণ সেখানে নির্দেশ ছোট আর নকশা স্পষ্ট। নিচের Haat function-টি reference-এর compiler (haat.py dis) দিয়ে ২৩টি নির্দেশ হয় (সত্যিকারের run; ব্লকে CONST-এর পাশে constant pool-এর ঘরের বদলে মানটিই লেখা):

// বাজারঘর: ডেলিভারির সময়, মিনিটে
fn minutes(days: Int) -> Int {
    var m = days * (24 * 60);
    if true { m = m + 30; }
    while false { m = m - 1; }
    days;
    return m;
}
print(minutes(2));

নিয়ম পাঁচটি: দুটি CONST-এর পরে ADD/SUB/MUL হলে একটি CONST (wrap-সহ); CONST true; JUMP_IF_FALSE মুছে ফেলা; CONST false; JUMP_IF_FALSE t হয় JUMP t; JUMP-এর ঠিক পরের নির্দেশ, যদি কোনো jump সেখানে না আসে, অগম্য; আর LOAD_LOCAL; POP কিছুই করে না। একটি শর্ত সব নিয়মে: জানালার মাঝে কোনো jump-এর লক্ষ্য থাকা চলবে না, কারণ অন্য পথে এসে কেউ জানালার মাঝখানে নামলে জোড়া দেওয়া নির্দেশ তার কাছে ভুল। আর যেহেতু Haat-এর jump-এর লক্ষ্য একটি নির্দেশের ক্রমিক নম্বর (সিদ্ধান্ত ২৮), কিছু মুছলে পরের সব লক্ষ্য নতুন করে গুনতে হয়।

// Haat VM-এর stack bytecode-এ peephole: ছোট জানালা, চেনা নকশা, তারপর jump-এর লক্ষ্য নতুন করে গোনা
const src = `LOAD_LOCAL 0|CONST 24|CONST 60|MUL|MUL|STORE_LOCAL 1|CONST true|JUMP_IF_FALSE 12|LOAD_LOCAL 1
|CONST 30|ADD|STORE_LOCAL 1|CONST false|JUMP_IF_FALSE 19|LOAD_LOCAL 1|CONST 1|SUB|STORE_LOCAL 1
|JUMP 12|LOAD_LOCAL 0|POP|LOAD_LOCAL 1|RETURN`;        // CONST-এর পাশে pool-এর ঘর নয়, মানটিই লেখা
let code = src.replace(/\n/g, "").split("|").map(s => s.split(" "));
const wrap = x => BigInt.asIntN(64, x);                 // Haat-এর ৬৪-bit wrap (সিদ্ধান্ত ১৩)
const fold = { ADD: (a, b) => wrap(a + b), SUB: (a, b) => wrap(a - b), MUL: (a, b) => wrap(a * b) };
const isInt = s => /^-?\d+$/.test(s ?? "");
function rule(code, i, targets) {                       // i থেকে শুরু জানালায় নকশা: [কয়টি নির্দেশ, বদলে কী, নাম]
  const [a, b = [], c = []] = code.slice(i, i + 3);
  const free = k => ![...Array(k).keys()].some(j => targets.has(i + 1 + j));   // জানালার মাঝে কোনো লক্ষ্য নয়
  if (a[0] === "CONST" && b[0] === "CONST" && fold[c[0]] && isInt(a[1]) && isInt(b[1]) && free(2))
    return [3, [["CONST", String(fold[c[0]](BigInt(a[1]), BigInt(b[1])))]], "CONST CONST op → CONST"];
  if (a[0] === "CONST" && b[0] === "JUMP_IF_FALSE" && /^(true|false)$/.test(a[1]) && free(1))
    return [2, a[1] === "true" ? [] : [["JUMP", b[1]]], `CONST ${a[1]}; JUMP_IF_FALSE`];
  if (a[0] === "JUMP" && +a[1] === i + 1) return [1, [], "ঠিক পরের নির্দেশে JUMP"];
  if (a[0] === "JUMP" && b[0] && free(1)) return [2, [a], "JUMP-এর পরের অগম্য নির্দেশ"];
  if (a[0] === "LOAD_LOCAL" && b[0] === "POP" && free(1)) return [2, [], "LOAD_LOCAL; POP"];
  return null;
}
function step(code) {                                   // প্রথম মেলা নিয়মটি একবার খাটায়
  const targets = new Set(code.filter(([op]) => op.startsWith("JUMP")).map(([, t]) => +t));
  for (let i = 0; i < code.length; i++) {
    const r = rule(code, i, targets);
    if (!r) continue;
    const [len, rep, name] = r, gone = len - rep.length;  // i-এর পরের লক্ষ্যগুলো gone ঘর আগে সরে
    const out = [...code.slice(0, i), ...rep, ...code.slice(i + len)];
    return [out.map(([op, t]) => op.startsWith("JUMP") && +t > i ? [op, String(+t - gone)] : [op, t]), name];
  }
  return null;
}
console.log("আগে:", code.length, "টি নির্দেশ");
for (let r; (r = step(code)); ) { code = r[0]; console.log(`  ${r[1].padEnd(27)}→ ${code.length}`); }
code.forEach(([op, t], i) => console.log(String(i).padStart(3), op, t ?? ""));

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

আগে: 23 টি নির্দেশ
  CONST CONST op → CONST     → 21
  CONST true; JUMP_IF_FALSE  → 19
  CONST false; JUMP_IF_FALSE → 18
  JUMP-এর পরের অগম্য নির্দেশ → 17
  JUMP-এর পরের অগম্য নির্দেশ → 16
  JUMP-এর পরের অগম্য নির্দেশ → 15
  JUMP-এর পরের অগম্য নির্দেশ → 14
  JUMP-এর পরের অগম্য নির্দেশ → 13
  ঠিক পরের নির্দেশে JUMP     → 12
  LOAD_LOCAL; POP            → 10
  0 LOAD_LOCAL 0
  1 CONST 1440
  2 MUL 
  3 STORE_LOCAL 1
  4 LOAD_LOCAL 1
  5 CONST 30
  6 ADD 
  7 STORE_LOCAL 1
  8 LOAD_LOCAL 1
  9 RETURN 

২৩টি থেকে ১০টি নির্দেশ। 24 * 60 হলো CONST 1440; if true-এর পরীক্ষা উধাও; while false হলো একটি JUMP, তার পরের পাঁচটি দেহের নির্দেশ (loop-এর ফেরার JUMP-সহ) অগম্য, তারপর নিজের ঠিক পরের নির্দেশে যাওয়া JUMP-টিও যায়। লেখকের lab-এ এই ১০টি নির্দেশ reference-এর VM-এ চালিয়ে দেখা হয়েছে: minutes(2) ছাপে 2910, মূল bytecode আর haat.py run-এর মতোই। বাকি STORE_LOCAL 1; LOAD_LOCAL 1 জোড়া মেলাতে একটি DUP opcode লাগত, যা Haat-এর ৩১টি opcode-এ নেই।

লক্ষ করুন, peephole if true ধরল, কিন্তু অংশ ২-এর bill-এর let express = false; … if express ধরতে পারত না: সেখানে শর্তটি একটি local variable থেকে আসে, আর variable-এ কী আছে তা জানতে dataflow লাগে। জানালা যত ছোট, দৃষ্টি তত সীমিত।

CPython-এর নিজের compiler-ও bytecode বানানোর পথে fold আর peephole করে (পর্ব ৬০)। লেখকের যন্ত্রে CPython 3.14.4-এর dis, সত্যিকারের run (৫টি ছোট function, আউটপুট সংক্ষেপে):

# week():       return 60 * 24 * 7
    LOAD_CONST               1 (10080)
# boom():       return 1 / 0
    LOAD_SMALL_INT           1
    LOAD_SMALL_INT           0
    BINARY_OP               11 (/)
# times_zero(x): return x * 0
    LOAD_FAST_BORROW         0 (x)
    LOAD_SMALL_INT           0
    BINARY_OP                5 (*)
# twice(a, b):  return a * b + a * b
    LOAD_FAST_BORROW_LOAD_FAST_BORROW 1 (a, b)
    BINARY_OP                5 (*)
    LOAD_FAST_BORROW_LOAD_FAST_BORROW 1 (a, b)
    BINARY_OP                5 (*)
    BINARY_OP                0 (+)
# debug_only(x): if False: print(…)  তারপর  return x
    NOP
    LOAD_FAST                0 (x)

প্রতিটি লাইন আমাদের নিয়মের সঙ্গে মেলে। 60 * 24 * 7 compile-এর সময়েই 10080. 1 / 0 fold হয় না: চলার সময়ের ZeroDivisionError রাখতে হবে, ঠিক Haat-এর নিয়ম। x * 0 সরল হয় না, কারণ Python-এ x যেকোনো object, যার __mul__ যা খুশি করতে পারে, এমনকি ছাপতে; একই কারণে twice-এ a * b দুবার হিসাব হয়, CSE নেই। if False:-এর দেহ উধাও, শুধু লাইন নম্বরের জন্য একটি NOP. আর LOAD_FAST_BORROW_LOAD_FAST_BORROW নিজেই একটি peephole-এর ফল: দুটি পরপর load জোড়া দেওয়া একটি superinstruction. অর্থাৎ dynamic ভাষায় type জানা না থাকায় optimizer অনেক কম পারে; সেই কাজ পরে করে চলার সময়ের specialization আর JIT (পর্ব ৬১)।

৮ · ভুল optimization ধরা — differential test আর জেনেশুনে বসানো ভুল

একটি optimizer-কে কীভাবে বিশ্বাস করবেন? পূর্ণ প্রমাণ সম্ভব, যেমন CompCert-এর মতো verified compiler (পর্ব ৪৪), কিন্তু ব্যয়বহুল। সস্তা আর শক্তিশালী উপায় differential testing: একই program আগের আর পরের রূপে চালিয়ে আউটপুট মেলানো, আর তুলনার জন্য একটি স্বাধীন মাপকাঠি, এখানে reference-এর haat.py run. নিচের ব্লক পর্ব ৬২-এর দশটি উদাহরণ আর প্রথম ১০০টি এলোমেলো program-এ পুরো pipeline চালিয়ে reference-এর আউটপুটের digest (random_ref.txt) মেলায়, error-এর বার্তা আর অবস্থানসহ।

# ধাপ ২: differential test — optimize-এর পরেও আউটপুট কি reference-এর `run`-এর সঙ্গে হুবহু, error-সহ?
import hashlib
from haat_opt import *
from haat_gen import gen_program
def digest(lines): return hashlib.sha256("\n".join(lines).encode()).hexdigest()[:10]
def count(mod):                                   # চলা নির্দেশ; runtime error হলে None
    try: return run_ir(mod, out=lambda s: None)
    except HaatError: return None
tot = {"স্থির নির্দেশ": [0, 0], "চলা নির্দেশ": [0, 0], "error-এ থামা": [0]}
def check(src, ok):                               # optimize-এর আগে-পরে গুনে, পরের আউটপুট ok কি না
    mod = compile_ir(src)
    s0, n0 = sum(map(size, mod.funcs.values())), count(mod)
    optimize_module(mod)
    got = run_lines(mod)
    tot["স্থির নির্দেশ"][0] += s0; tot["স্থির নির্দেশ"][1] += sum(map(size, mod.funcs.values()))
    if n0 is None: tot["error-এ থামা"][0] += 1
    else: tot["চলা নির্দেশ"][0] += n0; tot["চলা নির্দেশ"][1] += count(mod)
    return ok(got)
same = skip = 0
for name in ("bazar", "recursion", "mutual", "shadowing", "shortcircuit", "strings",
             "loops", "err_divzero", "counter", "nested"):
    want = open(f"examples/{name}.out", encoding="utf-8").read().split("\n")[:-1]
    try: same += check(open(f"examples/{name}.haat", encoding="utf-8").read(), lambda got: got == want)
    except Unsupported: skip += 1
print(f"উদাহরণ: {same}টি হুবহু, {skip}টি বাদ (closure, Haat IR v1-এর বাইরে)")
ref = open("random_ref.txt", encoding="utf-8").read().split()
ok = sum(check(gen_program(s), lambda got: digest(got) == ref[s]) for s in range(100))   # seed 0–99
print(f"এলোমেলো program: {ok}/100 হুবহু")
for k, v in tot.items():
    print(f"{k}: " + (f"{v[0]} → {v[1]} ({100 * (v[0] - v[1]) / v[0]:.1f}% কম)" if len(v) == 2 else f"{v[0]}টি program"))

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

উদাহরণ: 8টি হুবহু, 2টি বাদ (closure, Haat IR v1-এর বাইরে)
এলোমেলো program: 100/100 হুবহু
স্থির নির্দেশ: 14561 → 11548 (20.7% কম)
চলা নির্দেশ: 186297 → 182518 (2.0% কম)
error-এ থামা: 16টি program

দুটি উদাহরণ (counter, nested) closure আর nested function-এর জন্য Haat IR v1-এর বাইরে, তাই বাদ। বাকি আটটি আর ১০০টি এলোমেলো program-এর প্রতিটি হুবহু মেলে, যার মধ্যে error-এ থামা program-ও আছে। চলা নির্দেশ এখানে মাত্র ২.০% কমে, কারণ মোটের বড় অংশ recursion উদাহরণের call আর return, যা এই পর্বের কোনো pass ছোঁয় না। লেখকের lab-এ (CPython 3.14.4) পরীক্ষাটি বড় করে: আটটি উদাহরণ আর seed 0–2999-এর ৩,০০০টি program, মোট ৩,০০৮টি; reference-এর run সরাসরি চালিয়ে তুলনা, সত্যিকারের run. অমিল ০; ৩২৬টি program runtime error-এ থামে, বার্তা আর line:col হুবহু; প্রতিটি function-এ optimize-এর পরে আরেকটি রাউন্ড কিছুই বদলায়নি। স্থির নির্দেশ ৪,১৯,৩৩৩ থেকে ৩,২৫,৪১৯ (২২.৪% কম), আর error ছাড়া শেষ হওয়া ২,৬৮২টি program-এ চলা নির্দেশ ৯,১৮,৩০৮ থেকে ৭,৬৮,৯০৪ (১৬.৩% কম)। bazar.haat-এ চলা নির্দেশ ৭৪ থেকে ৭২: বাকি সম্ভাবনা loop-এর ভেতরের ধ্রুবকে, যা পর্ব ৬৬-এর কাজ।

কিন্তু যে পরীক্ষা কখনো ব্যর্থ হয় না, সে আসলে কিছু দেখে কি? যাচাই করতে simplify-এ জেনেশুনে অংশ ৩-এর ভুল নিয়ম x / x → 1 চালু করা যায় (wrong=True); একে বলে mutation testing. এর জন্য একটি ছোট program, যেখানে x / x আসে শুধু copy propagation-এর পরে:

// বাজারঘর: মাথাপিছু ভাগ
fn share(total: Int, people: Int) -> Int {
    let each = people;
    let ratio = people / each;
    return total * ratio;
}
print(share(500, 4));
print(share(300, 0));
# ধাপ ৩: জেনেশুনে একটি ভুল নিয়ম (x / x -> 1) বসিয়ে দেখা, differential test সেটি ধরে কি না
import hashlib
from haat_opt import *
from haat_gen import gen_program
def digest(lines): return hashlib.sha256("\n".join(lines).encode()).hexdigest()[:10]
fired = 0
def bad_simplify(fn):                             # ভুল নিয়মসহ simplify; কয়টি x / x বদলাল, তাও গোনে
    global fired
    fired += sum(i.kind == "bin" and i.sym == "/" and i.args[0] == i.args[1] for b in fn.blocks.values() for i in b)
    return simplify(fn, wrong=True)
WRONG = [fold, bad_simplify, copy_prop, lvn, gcse, copy_prop, dce, cleanup]
src = open("share.haat", encoding="utf-8").read()
want = open("share.out", encoding="utf-8").read().split("\n")[:-1]
for name, passes in (("সঠিক pipeline", PIPELINE), ("ভুল নিয়মসহ", WRONG)):
    mod = compile_ir(src)
    for fn in mod.funcs.values(): optimize(fn, passes)
    got = run_lines(mod)
    print(f"{name}: {got}", "মিলেছে" if got == want else "← reference থেকে আলাদা!")
print(show_ir(mod.funcs["share"]))
ref = open("random_ref.txt", encoding="utf-8").read().split()
caught = hit = 0
for s in range(100):
    mod, fired = compile_ir(gen_program(s)), 0
    for fn in mod.funcs.values(): optimize(fn, WRONG)
    hit += fired > 0
    caught += digest(run_lines(mod)) != ref[s]
print(f"এলোমেলো ১০০টি program: ভুল নিয়ম খাটল {hit}টিতে, অমিল ধরা পড়ল {caught}টিতে")

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

সঠিক pipeline: ['500', '4:24: runtime error: division by zero'] মিলেছে
ভুল নিয়মসহ: ['500', '300'] ← reference থেকে আলাদা!
fn share(total, people):
B0:
  return total
এলোমেলো ১০০টি program: ভুল নিয়ম খাটল 3টিতে, অমিল ধরা পড়ল 0টিতে

share.haat-এ ভুলটি সঙ্গে সঙ্গে ধরা পড়ে: each = people-এর copy propagation people / each-কে people / people বানায়, ভুল নিয়ম তাকে 1 করে, total * 1 হয় total, আর পুরো function একটি নির্দেশে নামে: return total. দ্বিতীয় call-এ error-এর বদলে 300. অথচ ১০০টি এলোমেলো program-এ নিয়মটি তিনটিতে খাটে, কিন্তু একটিতেও অমিল নেই: সেখানে x কখনো শূন্য হয়নি, তাই 1-ই ঠিক উত্তর ছিল। লেখকের lab-এ ৩,০০০টি program-এ: ভুল নিয়ম খাটে ৪৫টিতে, অমিল ধরা পড়ে মাত্র ১০টিতে (seed 726, 799 … 2935). শিক্ষা: এলোমেলো test ভুল নিয়মকে “চালায়”, কিন্তু ভুলটি দেখা দেয় শুধু বিশেষ মানে (x = 0); তাই সীমার মান নিয়ে হাতে বাছা উদাহরণ সবসময় রাখুন।

বাস্তব compiler-এর জগতে এই চিন্তা বড় ফল দিয়েছে। Utah বিশ্ববিদ্যালয়ের Xuejun Yang, Yang Chen, Eric Eide আর John Regehr-এর Csmith এলোমেলো, কিন্তু UB-মুক্ত C program বানিয়ে কয়েকটি compiler-এ চালিয়ে আউটপুট মেলায়; PLDI ২০১১-এর প্রবন্ধে তাঁরা লেখেন, তিন বছরে GCC আর LLVM-সহ compiler-গুলোতে ৩২৫-এর বেশি অজানা bug জানানো হয়েছে, যার অনেকগুলো চুপচাপ ভুল কোড বানানোর bug. আরেক ধারা প্রমাণের: translation validation প্রতিটি নির্দিষ্ট রূপান্তরের পরে সমতুল্যতা যাচাই করে, আর Alive (PLDI ২০১৫) LLVM-এর InstCombine-এর peephole নিয়মগুলো SMT solver দিয়ে প্রমাণ করতে গিয়ে ৩০০-এর বেশি নিয়মের মধ্যে ৮টি ভুল খুঁজে পায়।

আরও গভীরে: বাস্তব compiler-এ LVN-এর বড় রূপ global value numbering (GVN): SSA-র ওপর পুরো function জুড়ে “একই মান” খোঁজা, যার শিকড় ১৯৮৮ সালের Alpern–Wegman–Zadeck আর Rosen–Wegman–Zadeck-এর প্রবন্ধে; LLVM-এ GVN আর EarlyCSE দুটি আলাদা pass. LLVM-এর InstCombine আসলে হাজারো peephole নিয়মের একটি বড় সংগ্রহ, আর Alive2-এর মতো tool এখন নতুন নিয়ম যোগের সময় সেগুলো যাচাই করে। আরেকটি নতুন ধারা e-graph আর equality saturation (যেমন ২০২১ সালের egg library): নিয়মগুলো একটির পর একটি না খাটিয়ে সব সমতুল্য রূপ একসঙ্গে একটি graph-এ রাখা, তারপর সবচেয়ে সস্তাটি বাছা; এতে phase ordering-এর সমস্যা অনেকটা এড়ানো যায়, বিনিময়ে memory আর সময় লাগে।

পরীক্ষা ও ইন্টারভিউতে:

  • Local আর global optimization-এর পার্থক্য? Local একটি basic block-এর ভেতরে, কোনো শাখা ছাড়া; global পুরো CFG জুড়ে, dataflow analysis দিয়ে।
  • Constant folding আর constant propagation-এর পার্থক্য? Folding জানা operand-এর হিসাব আগেই করে; propagation খুঁজে বের করে কোন নামে কোন ধ্রুবক আছে, যাতে folding চলতে পারে।
  • Common subexpression কখন বাদ দেওয়া যায়? যখন expression-টি সব পথে আগে হিসাব হয়েছে আর তার operand পরে বদলায়নি (available expressions, must); call কখনো নয়, যদি না জানা থাকে সেটি pure.
  • DCE কোন নির্দেশ মুছতে পারে না? যার side effect আছে বা যা error দিতে পারে: print, call, global-এ লেখা, অজানা ভাজকের ভাগ।
  • Peephole optimization কী? পরপর কয়েকটি নির্দেশের ছোট জানালায় চেনা নকশা বদলানো, যেমন CONST 2; CONST 3; ADD → CONST 5; জানালার মাঝে jump-এর লক্ষ্য থাকা চলবে না।

৯ · AI-এর যুগে optimization

AI assistant-কে “এই কোডটি optimize করো” বললে উত্তর প্রায়ই দ্রুত, পরিচ্ছন্ন আর আত্মবিশ্বাসী আসে, এবং অনেক সময় অর্থ বদলে দেয়। Optimization-এর ভুল সবচেয়ে বিপজ্জনক ধরনের, কারণ সাধারণ input-এ ফল একই থাকে; পার্থক্য দেখা দেয় শুধু সীমার মানে, শূন্যে, overflow-এ বা side effect-এ।

AI-এর ভুলকীভাবে ধরবেন
বীজগণিতের নিয়ম সরাসরি যন্ত্রের সংখ্যায়: x / x → 1, x + 1 > x, float-এ x * 0 → 0০, সবচেয়ে বড়-ছোট মান, NaN আর −0.0 দিয়ে আগে-পরে চালানো
এক ভাষার UB-র যুক্তি অন্য ভাষায়: “compiler তো C-তে এটা করে”নিজের ভাষার specification পড়া (Haat-এ wrap আর error নির্ধারিত)
অব্যবহৃত ফলের call বা ভাগ মুছে ফেলা, call-এর ক্রম বদলানোছাপা call আর শূন্য দিয়ে ভাগসহ program-এ আউটপুট আর error মেলানো
Str-এর +-কে বিনিময়যোগ্য ধরে CSEtype-মিশ্র উদাহরণে LVN-এর ফল দেখা
বানানো LLVM pass, GCC flag বা “-O2 সবসময় X করে” ধরনের দাবিনিজের compiler-এর version-এ চালিয়ে IR বা -print-changed দেখা
Optimization-এর গতি নিয়ে বানানো সংখ্যানিজের যন্ত্রে মাপা, চলা নির্দেশ গোনা, এক যন্ত্রের ফল বলে লেখা

AI-কে কাজে লাগাতে semantics আর যাচাইয়ের নিয়ম আগেই বলে দিন:

আমি Python 3.14-এ একটি ছোট three-address IR-এর (Haat IR) জন্য optimization pass লিখছি। Int ৬৪-bit two's complement-এ wrap করে; / শূন্যের দিকে কাটে, % ভাজ্যের চিহ্ন নেয় (C-র মতো); শূন্য দিয়ে ভাগ একটি runtime error, যার বার্তা আর line:col program-এর আচরণের অংশ। কোনো undefined behavior নেই। ১. একটি algebraic simplification pass দাও; প্রতিটি নিয়মের পাশে এক লাইনে বলো কেন এটি wrap আর শূন্য দিয়ে ভাগের পরেও সঠিক। যে নিয়ম শুধু C-র UB-র জন্য বৈধ, তা দেবে না। ২. যে নির্দেশ ভাগ করে আর ভাজক শূন্য হতে পারে, তা কখনো মুছবে, fold করবে বা সরাবে না; call আর print-এর ক্রম বদলাবে না। ৩. প্রতিটি নিয়মের জন্য একটি counterexample-খোঁজা test লেখো: 0, 1, -1, সবচেয়ে বড় আর সবচেয়ে ছোট Int দিয়ে আগে-পরে চালিয়ে মেলাবে। ৪. কোনো বাস্তব compiler (LLVM, GCC) কী করে বললে version বলো; নিশ্চিত না হলে বলো “যাচাই করা হয়নি”।

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

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

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

প্র ০১প্রথম FORTRAN compiler থেকে Frances Allen-এর “catalogue” পর্যন্ত: optimization কেন শুরু থেকেই compiler-এর কেন্দ্রে ছিল?

১৯৫০-এর দশকে programmer-রা assembly-তে লিখতেন, আর “উচ্চ-স্তরের ভাষা” নিয়ে প্রধান সন্দেহ ছিল গতি: যন্ত্র নিজে লিখলে কোড ধীর হবে। John Backus-এর দল IBM-এ ১৯৫৭ সালে প্রথম FORTRAN compiler দেয়, আর তাদের বড় লক্ষ্য ছিল হাতে লেখা assembly-র কাছাকাছি কোড বানানো; সেই compiler-এর বড় অংশই ছিল loop আর array-র হিসাব সাজানো, register-এর ভালো ব্যবহার। Backus পরে লিখেছেন, দক্ষ কোড না দিলে FORTRAN গ্রহণযোগ্য হতো না। অর্থাৎ optimization ছিল উচ্চ-স্তরের ভাষার টিকে থাকার শর্ত।

১৯৬০-এর দশকে IBM-এ Frances Allen আর John Cocke বিচ্ছিন্ন কৌশলগুলোকে একটি তত্ত্বে আনেন: control flow graph, basic block, interval, আর কোন রূপান্তর কোন বিশ্লেষণের ওপর দাঁড়ায়। ১৯৭০-এর দশকের শুরুতে তাঁদের “A Catalogue of Optimizing Transformations” constant folding, CSE, dead code elimination, code motion, strength reduction-এর মতো রূপান্তরগুলোর নাম আর শর্ত গুছিয়ে দেয়, যা আজও পাঠ্যবইয়ের অধ্যায়ের তালিকার মতো শোনায় (প্রকাশের সাল সূত্রভেদে ১৯৭১ বা ১৯৭২)। Allen ২০০৬ সালে Turing Award পান, এই পুরস্কার পাওয়া প্রথম নারী হিসেবে।

লক্ষ করুন, এই পর্বের প্রায় প্রতিটি pass সেই তালিকায় আছে; নতুন যা যোগ হয়েছে তা মূলত গাণিতিক ভিত্তি (Kildall-এর dataflow কাঠামো, পর্ব ৬৪), SSA (পর্ব ৬৩), আর সঠিকতা যাচাইয়ের tool. রূপান্তরগুলো পুরোনো; প্রতিটি নতুন ভাষার semantics-এ সেগুলো কখন বৈধ, সেই প্রশ্নটি প্রতিবার নতুন। Haat-এর wrap আর শূন্য দিয়ে ভাগের error একই পুরোনো রূপান্তরের শর্ত বদলে দেয়, যেমন অংশ ৩-এর টেবিলে দেখেছেন।

মূল উপলব্ধি: optimization উচ্চ-স্তরের ভাষাকে ব্যবহারযোগ্য করেছিল; রূপান্তরের তালিকা ষাট বছর ধরে প্রায় একই, কিন্তু প্রতিটি ভাষার semantics ঠিক করে কোনটি কোথায় বৈধ।

প্র ০২Clang C-তে x / x-কে 1 আর x + 1 > x-কে সত্য বানায়। Undefined behavior কি optimizer-এর বন্ধু, না programmer-এর শত্রু?

অংশ ৩-এ Clang 22.1.8 সত্যিই দুটি function-কে এক নির্দেশে নামিয়েছে, আর bill-এর C রূপে অব্যবহৃত p / qty মুছে p * 5 / 100-কে p / 20 বানিয়েছে। C standard-এর চোখে সবই বৈধ: signed overflow আর শূন্য দিয়ে ভাগ undefined, অর্থাৎ program এমন কিছু করলে standard কোনো আচরণ দাবি করে না, তাই compiler ধরে নেয় সেগুলো ঘটে না।

ক্ষতিও বাস্তব। নিরাপত্তা-সংক্রান্ত check যেমন “যোগের পরে ফল কি আগের চেয়ে ছোট?”, যা overflow ধরতে লেখা, ঠিক এই যুক্তিতে মুছে যেতে পারে, কারণ compiler-এর চোখে overflow হয়ই না। তাই বড় প্রকল্প প্রায়ই flag দিয়ে নিয়ম বদলায়: GCC আর Clang-এর -fwrapv signed overflow-কে wrap বলে নির্ধারিত করে, ঠিক Haat-এর মতো; Linux kernel-এর মতো প্রকল্প এমন কিছু flag ব্যবহার করে বলে জানা যায় (নির্দিষ্ট তালিকা version-ভেদে বদলায়)। Rust release build-এ overflow-কে wrap করে আর debug build-এ panic করে; Java সবসময় wrap করে; Python-এর int বড় হতেই থাকে (পর্ব ০৬)।

Haat-এর পছন্দ স্পষ্ট: কোনো UB নেই। দাম আমরা মেপেছি: p * 5 / 100 থেকে যায়, p / qty মোছা যায় না, আর অনুশীলন ২-এ দেখবেন C-র রূপান্তরটি Haat-এ সত্যিই ভুল ফল দেয়। বিনিময়ে একই program সব optimization-স্তরে একই আচরণ করে, যা debugging আর নিরাপত্তায় বড় লাভ। পর্ব ৬৮-এ LLVM IR-এ নামানোর সময় এর ফল আবার আসবে: Haat-কে add nsw নয়, সাধারণ add লিখতে হবে, আর প্রতিটি sdiv-এর আগে শূন্যের check বসাতে হবে।

মূল উপলব্ধি: UB optimizer-কে স্বাধীনতা দেয়, programmer-এর কাছ থেকে নিশ্চয়তা কেড়ে নিয়ে; ভাষা-নকশাকার ঠিক করেন সেই দাম কে দেবে।

প্র ০৩Value numbering-এর ধারণা কোথা থেকে এল, আর block-এর দেয়াল পেরোতে গিয়ে কেন SSA লাগল?

Value numbering-এর মূল চিন্তা পুরোনো: প্রতিটি হিসাবকে তার operand-এর “মান-পরিচয়” দিয়ে চেনা, নাম দিয়ে নয়। সাধারণত এর কৃতিত্ব দেওয়া হয় John Cocke আর Jacob Schwartz-এর ১৯৭০ সালের compiler-কৌশলের নোটকে। এই পর্বের stepper-এ দেখেছেন, t4 = qty * unit আর p = qty * unit একই key পায়, আর t6 = t4 * t5-এর key-তে t4 নয়, তার VN 3 বসে: অর্থাৎ নাম বদলালেও মান চেনা যায়।

সমস্যা শুরু হয় block-এর বাইরে। একটি নাম দুই শাখায় আলাদা মান পেলে মিলনের বিন্দুতে তার “একটি” VN থাকে না। এখানেই SSA (পর্ব ৬৩) কাজে লাগে: প্রতিটি নামের একটিই definition, আর মিলনে একটি phi, যা নিজেই একটি নতুন মান। ১৯৮৮ সালে দুটি প্রবন্ধ (Alpern, Wegman আর Zadeck; Rosen, Wegman আর Zadeck) SSA-র ওপর global value numbering আর redundancy দূর করার কৌশল দেয়, আর ১৯৯১ সালে Wegman আর Zadeck-এর SCCP একই SSA-তে ধ্রুবক আর অগম্য শাখা একসঙ্গে খোঁজে।

আমাদের pipeline SSA ছাড়াই global CSE করেছে available expressions আর নতুন temp u দিয়ে। এটি সঠিক, কিন্তু u-এর জন্য বাড়তি copy বসে, আর একই মান আলাদা নামে থাকলে (a = x * y এক শাখায়, b = x * y অন্যটিতে, তারপর দুটিই মিলনে) চিনতে পারে না। ৩,০০০টি program-এ global CSE মাত্র ৪০টি বদল এনেছে; বাস্তব কোডে, বিশেষ করে inlining-এর পরে (পর্ব ৬৭), এমন সুযোগ অনেক বেশি থাকে, তাই বাস্তব compiler GVN-এ বেশি খরচ করে।

মূল উপলব্ধি: নামের বদলে মান দেখা CSE-এর মূল চাবি; block-এর ভেতরে hash table যথেষ্ট, block পেরোতে SSA সেই চিন্তাকে সহজ করে।

প্র ০৪Phase ordering problem: একই pass বারবার চালানো কি অপচয়, না প্রয়োজন? LLVM-এর -O2 কী বলে?

অংশ ৬-এর মাপা ফল সমস্যাটি সংখ্যায় দেখায়: fold, copy propagation আর DCE একবার চালালে ক্রমভেদে ১৮.০% বনাম ৮.৬% নির্দেশ কমে, আর fixpoint পর্যন্ত চালালে দুটিই ১৯.৭%. কারণ প্রতিটি pass অন্যের জন্য সুযোগ তৈরি করে: fold একটি নামকে অপ্রয়োজনীয় করে, DCE তা মোছে, আর মোছার পরে নতুন ধ্রুবক শর্ত বা জোড়া দেওয়ার মতো block দেখা দিতে পারে। আবার কিছু pass একে অপরের কাজ নষ্টও করে; যেমন inlining কোড বড় করে, আর register allocation-এর আগে বেশি CSE করলে একসঙ্গে live মান বেড়ে register-এর চাপ বাড়ে।

বাস্তব compiler সাধারণত একটি নির্দিষ্ট, অভিজ্ঞতা থেকে সাজানো তালিকা চালায়, যেখানে একই pass কয়েকবার থাকে। অংশ ৬-এর Clang run-এ bill-এর জন্য যে কয়টি pass কিছু বদলেছে, সেগুলোই দেখা গেছে: SROA, EarlyCSE, IPSCCP, InstCombine, SimplifyCFG, Reassociate; LLVM-এর -O2 তালিকায় InstCombine আর SimplifyCFG একাধিকবার আছে (সঠিক সংখ্যা version-ভেদে বদলায়, তাই নিজের version-এ দেখে নেওয়াই ভালো)। আমাদের ছোট pipeline-এর “কিছু না বদলানো পর্যন্ত ঘোরাও” কৌশল ছোট IR-এ চলে, কিন্তু বড় program-এ সময়ের সীমা আর নিশ্চয়তা দুটিই লাগে; তাই আমাদের optimize-এও ১০ রাউন্ডের সীমা।

সেরা ক্রম খোঁজা নিজেই একটি গবেষণার বিষয়: কিছু কাজ নির্দিষ্ট program-এর জন্য স্বয়ংক্রিয়ভাবে pass-এর ক্রম খোঁজে (autotuning, machine learning-ভিত্তিক পদ্ধতি; ফল প্রকল্পভেদে আলাদা), আর equality saturation চেষ্টা করে ক্রমের প্রশ্নটিই তুলে দিতে (আরও গভীরে বাক্স দেখুন)।

মূল উপলব্ধি: pass-গুলো একে অপরের জন্য সুযোগ তৈরি করে, তাই ক্রম আর পুনরাবৃত্তি ফল বদলায়; বাস্তব compiler-এর pipeline সেই আপসের অভিজ্ঞতার ফল, কোনো গাণিতিক সেরা উত্তর নয়।

প্র ০৫Compiler-এর optimizer-এ bug কীভাবে ধরা পড়ে? Csmith আর Alive থেকে কী শেখার আছে?

Optimizer-এর bug-এর সবচেয়ে খারাপ রূপ crash নয়, চুপচাপ ভুল কোড (“miscompilation”): program চলে, কিন্তু ভুল উত্তর দেয়, আর programmer নিজের কোডে দোষ খোঁজেন। Utah বিশ্ববিদ্যালয়ের দলের Csmith (PLDI ২০১১) এই সমস্যাকে differential testing দিয়ে আক্রমণ করে: এলোমেলো C program, যেগুলো সাবধানে UB এড়ায়, কয়েকটি compiler আর optimization-স্তরে চালিয়ে আউটপুট মেলানো; অমিল মানে কোথাও ভুল। প্রবন্ধে তাঁরা লেখেন, তিন বছরে ৩২৫-এর বেশি অজানা bug জানানো হয়েছে, আর পরীক্ষিত প্রতিটি compiler-এ ভুল কোড বানানোর bug পাওয়া গেছে। UB এড়ানোটাই মূল কৌশল: UB থাকলে দুটি আলাদা আউটপুটও “সঠিক”, তুলনার অর্থ থাকে না। Haat-এ UB নেই বলে আমাদের haat_gen.py-কে এই কষ্ট কম করতে হয়।

অন্য পথ প্রমাণের। Alive (PLDI ২০১৫) LLVM-এর InstCombine-এর peephole নিয়মগুলোকে একটি ছোট ভাষায় লিখে SMT solver দিয়ে যাচাই করে, প্রতিটি bit-width আর UB-র নিয়মসহ; প্রবন্ধ অনুযায়ী ৩০০-এর বেশি নিয়ম অনুবাদ করে ৮টি ভুল পাওয়া যায়। অংশ ৮-এর পরীক্ষা দেখায় কেন প্রমাণ দরকার: ভুল নিয়ম x / x → 1 ৪৫টি program-এ খেটেছে, কিন্তু ভুল ফল দিয়েছে মাত্র ১০টিতে, কারণ ভুলটি দেখা দেয় শুধু x = 0-তে। একটি solver ঠিক সেই counterexample সঙ্গে সঙ্গে খুঁজে দিত।

তৃতীয় পথ verified compiler (CompCert; পর্ব ৪৪), যেখানে প্রতিটি pass-এর সঠিকতা প্রমাণ-সহায়কে প্রমাণিত। বাস্তবে তিনটি পথ একে অপরের পরিপূরক: test দ্রুত আর সস্তা, প্রমাণ পূর্ণ কিন্তু ব্যয়বহুল; সফটওয়্যার টেস্টিং কোর্সের fuzz testing আর mutation testing পর্ব এই চিন্তার সাধারণ রূপ দেখায়।

মূল উপলব্ধি: optimizer-এর ভুল সাধারণ input-এ লুকিয়ে থাকে; এলোমেলো differential test অনেক ধরে, সীমার উদাহরণ আর প্রমাণ বাকিটা।

অনুশীলন

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

  1. নকশা ও বাস্তবায়ন — একটি strength reduction pass: haat_opt.py-র ওপর একটি pass strength(fn) লিখুন, যা x * 2 বা 2 * x (2 একটি Int ধ্রুবক) -কে x + x বানায়, আর PIPELINE-এ DCE-র আগে বসান। তারপর বলুন: x / 2-কে ডানে এক bit shift বানানো কেন Haat-এ ভুল হতো?
    def strength(fn):                          # x * 2 -> x + x, ধ্রুবক জানতে CONSTANTS
        pts, n = points(CONSTANTS, fn, solve(CONSTANTS, fn)), 0
        for b, body in fn.blocks.items():
            for i, ins in enumerate(body):
                env = pts[b, i][0]
                if ins.kind != "bin" or ins.sym != "*" or env is None: continue
                x, y = ins.args
                k = lambda z: env[z] if local(z) and type(env.get(z)) is int else None
                if k(y) == 2: body[i] = Ins("bin", ins.dst, [x, x], "+", pos=ins.pos); n += 1
                elif k(x) == 2: body[i] = Ins("bin", ins.dst, [y, y], "+", pos=ins.pos); n += 1
        return n
    P = PIPELINE[:-2] + [strength, dce, cleanup]

    Wrap-এ x * 2 আর x + x সবসময় একই (দুটিই 2x-এর 264 ভাগশেষ), আর কোনোটিতে error নেই, তাই নিয়মটি সঠিক। লেখকের lab-এ সত্যিকারের run: ৩,০০০টি এলোমেলো program-এর ৩১৯টিতে মোট ৩৩২টি বদল, reference-এর সঙ্গে অমিল ০. গুণের ধ্রুবক শুধু propagation-এর পরে দেখা যায় (t5 = const 2 আলাদা নির্দেশ), তাই CONSTANTS লাগে। ভাগের ক্ষেত্রে: Haat-এর / শূন্যের দিকে কাটে, তাই reference-এ -7 / 2 ছাপে -3; কিন্তু two's complement-এ −7-কে ডানে এক bit arithmetic shift করলে −4 (নিচের দিকে গোল করা)। ধনাত্মক x-এ দুটি এক, ঋণাত্মক বিজোড়ে আলাদা। Clang তাই ২-এর ঘাত দিয়ে signed ভাগে shift-এর আগে একটি সংশোধন যোগ করে, যেমন অংশ ৬-এর assembly-তে shrq $63 দিয়ে চিহ্নের bit যোগ।

  2. ভুল খুঁজুন আর প্রমাণ — p * 5 / 100 → p / 20: Clang C-র bill-এ এই রূপান্তর করেছে। (ক) একটি p দিন, যেখানে Haat-এ দুটির ফল আলাদা। (খ) প্রমাণ করুন, p * 5 overflow না করলে দুটি সমান। (গ) Clang-এর কাছে কোন তথ্য রূপান্তরটিকে বৈধ করেছে?

    (ক) p = 2305843009213693952 (261). Reference-এ সত্যিকারের run: print(p * 5 / 100); ছাপে -69175290276410818, আর print(p / 20); ছাপে 115292150460684697. 5 · 261 > 263 − 1, তাই গুণফল wrap করে ঋণাত্মক হয়। সাধারণ মান p = 1040-এ দুটিই 52.

    (খ) প্রমাণ, যখন 5p ৬৪-bit-এর সীমায় থাকে (তখন গুণে wrap নেই):

    1. trunc(x) মানে শূন্যের দিকে কাটা পূর্ণসংখ্যা অংশ। Haat-এর a / b = trunc(a ÷ b), সাধারণ মূলদ সংখ্যার ভাগে।
    2. 5p ÷ 100 = p ÷ 20, মূলদ সংখ্যা হিসেবে হুবহু সমান (লব-হরকে ৫ দিয়ে কাটা)।
    3. তাই trunc(5p ÷ 100) = trunc(p ÷ 20). আর trunc(p ÷ 20)-এর মান |p|-এর চেয়ে ছোট, তাই এখানেও wrap নেই। ∎

    (গ) LLVM IR-এ গুণটি mul nsw: “no signed wrap”, অর্থাৎ overflow হলে ফল poison, যা C-র UB থেকে আসে। ফলে Clang ধরে নেয় ধাপ ১-এর শর্ত সবসময় সত্য। Haat-এ overflow নির্ধারিত (wrap), তাই এই শর্ত নেই, আর রূপান্তরটি ভুল।

  3. হিসাব — পরীক্ষার ধাঁচে LVN আর তারপর pipeline: নিচের function-এর Haat IR একটি block. (ক) LVN চালিয়ে প্রতিটি নামের value number আর কোন নির্দেশ copy হয়, লিখুন। (খ) পুরো pipeline-এর পরে কী থাকে? (গ) f(3, 4) কী ছাপে?
    fn f(x: Int, y: Int) -> Int {
        var a = x * y;
        let b = y * x;
        a = a + 1;
        let c = x * y;
        let d = c - b;
        return d + a;
    }
    print(f(3, 4));
    
    B0: a = x * y;  b = y * x;  t1 = const 1;  a = a + t1
        c = x * y;  d = c - b;  t2 = d + a;  return t2
    নির্দেশkeyVNফল
    a = x * y(*, 1, 2)x 1, y 2, a 3নতুন
    b = y * x(*, 1, 2), সাজানোb 3b = a
    t1 = const 1(const, 1)t1 4নতুন
    a = a + t1(+, 3, 4)a 5a আর VN 3 রাখে না
    c = x * y(*, 1, 2)c 3c = b (a নয়!)
    d = c - b(-, 3, 3)d 6নতুন
    t2 = d + a(+, 6, 5)t2 7নতুন

    ফাঁদটি চতুর্থ সারিতে: a নতুন করে লেখা হলে VN 3 আর a-তে নেই, তাই c = x * y-এর জন্য LVN খোঁজে VN 3 এখন কোন নামে আছে, আর পায় b. সব মান lvn(fn, trace)-এর সত্যিকারের আউটপুট, ২টি বদল। (খ) লেখকের lab-এ pipeline তিন রাউন্ডে থামে: copy propagation d = c - b-কে d = b - b বানায়, simplify (x - x → 0) তাকে d = const 0, তারপর t2 = d + a-এ 0 + y নিয়ম দিয়ে t2 = a, আর DCE বাকিটা মোছে। থাকে চারটি নির্দেশ: a = x * y; t1 = const 1; a = a + t1; return a. (গ) reference আর optimize-এর পরের IR দুটিই ছাপে 13.

  4. আউটপুট অনুমান — wrap-এ কোন fold বৈধ: নিচের program কী ছাপে? একটি optimizer যদি big + 1 - 1-কে big, আর big + 1 > big-কে true বানায়, কোনটি ঠিক?
    let big = 9223372036854775807;
    print(big + 1 - 1);
    print(big + 1 > big);
    print(-(big + 1) == big + 1);

    Reference-এ সত্যিকারের run: 9223372036854775807, false, true. big + 1 wrap করে সবচেয়ে ছোট Int −9223372036854775808; তার থেকে 1 বিয়োগ আবার wrap করে big-এ ফেরে, তাই প্রথম রূপান্তরটি সঠিক: ২64-এর ভাগশেষের হিসাবে যোগ-বিয়োগ সাধারণ বীজগণিতের নিয়ম মানে। দ্বিতীয়টি ভুল: সবচেয়ে ছোট Int big-এর চেয়ে বড় নয়, তাই false; C-তে signed overflow UB বলে Clang এটিকে সত্য বানাতে পারে (অংশ ৩-এর grows). তৃতীয় লাইনে সবচেয়ে ছোট Int-এর ঋণাত্মক সে নিজেই (সিদ্ধান্ত ১৩), তাই true. আমাদের fold তিনটিকেই সরাসরি ধ্রুবক বানায় (t4 = const 9223372036854775807, t7 = const false, t13 = const true), কারণ সে বীজগণিতের নিয়ম নয়, arith দিয়ে আসল wrap-এর হিসাব করে; optimize-এর পরের আউটপুট reference-এর সঙ্গে হুবহু।

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

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

ক্রমLocal value numbering-এ একটি নির্দেশ d = a op b-এর জন্য ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. a আর b-এর value number খোঁজা (নতুন নাম হলে নতুন নম্বর দেওয়া)
  2. বিনিময়যোগ্য operator হলে দুই নম্বর সাজিয়ে key (op, VN, VN) বানানো
  3. টেবিলে key আছে কি না দেখা
  4. থাকলে সেই value number এখনো কোন নামে আছে, তা খোঁজা
  5. পাওয়া গেলে নির্দেশটিকে d = সেই নাম copy বানানো, নইলে নতুন নম্বর দিয়ে key টেবিলে তোলা
  6. d-এর value number হালনাগাদ করা

একটি ভাষায় Int ৬৪-bit-এ wrap করে আর শূন্য দিয়ে ভাগ একটি runtime error. নিচের কোন algebraic simplification সেই ভাষায় বৈধ নয়?

  • x * 0 → 0
  • x - x → 0
  • x / x → 1
  • x / 1 → x

শুধু Int-এর একটি block: a = b * c, d = c * b, b = d + 1, e = b * c. বিনিময়যোগ্যতা মেনে local value numbering কোন নির্দেশকে copy বানাবে?

  • কোনোটিকে নয়
  • শুধু d = c * b (হয় d = a)
  • শুধু e = b * c
  • d আর e দুটিই

একটি function-এ t = a / b, আর t পরে কোথাও পড়া হয় না; b-এর মান compile-এর সময় অজানা। Dead code elimination কী করবে?

  • নির্দেশটি মুছে দেবে, কারণ t মৃত
  • নির্দেশটি function-এর শেষে সরিয়ে দেবে
  • t = const 0 বসাবে
  • নির্দেশটি রেখে দেবে

Global common subexpression elimination কেন available expressions (forward, must, ∩) ব্যবহার করে, reaching definitions-এর মতো may (∪) বিশ্লেষণ নয়?

  • আগের ফল নিতে হলে সেটি পৌঁছানোর প্রতিটি পথে হিসাব হয়ে থাকতে হবে
  • ∪ দিয়ে solver কখনো থামে না
  • forward বিশ্লেষণে সবসময় ∩ লাগে
  • reaching definitions শুধু একটি block-এ কাজ করে

Stack bytecode-এ একটি peephole নিয়ম CONST 2; CONST 3; ADD → CONST 5. কোন অবস্থায় নিয়মটি খাটানো চলবে না?

  • কোনো jump যদি প্রথম CONST 2-তে আসে
  • ADD-এর পরে একটি PRINT থাকলে
  • কোনো jump যদি সরাসরি CONST 3-তে আসে
  • যোগফল ৬৪-bit-এ wrap করতে পারলে

একটি function-এ: let express = false; var fee = 60; if express { fee = 120; } return fee;. সাধারণ (CFG-র সব edge সম্ভব ধরা) constant propagation আর sparse conditional constant propagation (SCCP) return-এ fee সম্পর্কে কী বলে?

  • দুটিই বলে fee = 60
  • সাধারণটি বলে ⊥ (ধ্রুবক নয়), SCCP বলে 60
  • সাধারণটি বলে 60, SCCP বলে ⊥
  • দুটিই বলে fee = 120

C-তে Clang -O2-এ long r(long x) { return x / x; }-কে ret i64 1 বানায়। কেন এটি C-তে বৈধ, কিন্তু Haat-এর মতো ভাষায় নয়?

  • C-তে শূন্য দিয়ে ভাগ undefined behavior, Haat-এ তা নির্ধারিত runtime error
  • C-তে long আসলে floating-point
  • Clang চালিয়ে দেখে যে x কখনো শূন্য নয়
  • Haat-এ ভাগ wrap করে বলে

শব্দকোষ

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

মনে রাখুন

  1. সঠিকতার চুক্তি: ছাপা লাইন, error-এর বার্তা ও অবস্থান আর থামা হুবহু থাকবে; শূন্য হতে পারে এমন ভাজকের ভাগ কখনো fold, মোছা বা সরানো নয়; call আর print-এর ক্রম অটুট।
  2. Constant folding ও propagation: forward, must; constant lattice-এ meet; ধ্রুবক শর্তের branch → jump, অগম্য block মোছা; SCCP অগম্য edge আগেই বাদ রাখে।
  3. CSE: block-এ LVN (op, VN, VN) key দিয়ে; block পেরিয়ে available expressions আর নতুন temp; + Str-এ বিনিময়যোগ্য নয়; call কখনো নয়।
  4. DCE: জরুরি নির্দেশ থেকে use-def chain ধরে mark, তারপর sweep; faint শিকলসহ সব মৃত কোড এক ধাপে।
  5. যাচাই আর ক্রম: pass একে অপরের সুযোগ তৈরি করে, তাই fixpoint পর্যন্ত ঘোরানো; প্রতিটি বদল differential test আর সীমার উদাহরণে চালিয়ে দেখা।

পরের পর্বে: পর্ব ৬৬ (Loop optimization — invariant code motion, strength reduction আর unrolling). bazar-এর loop-এর ভেতরের const 5000 আর const 1250 বাইরে আনা, আর একটি ভাগকে loop-এর বাইরে আনা কখন নিরাপদ নয়।

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

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