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

Loop optimization — invariant code motion, strength reduction আর unrolling

Loop Optimization — Invariant Code Motion, Strength Reduction and Unrolling

Taught in Bangla, this lesson finds natural loops from back edges and dominators, then hoists loop-invariant code into a preheader under safe conditions and shows why moving a division can change output. It covers induction variables and strength reduction that stays exact under 64-bit wrap, loop unrolling, and further transforms from unswitching to vectorization. A combined pipeline is checked by differential testing, and real Clang 22 remarks and assembly show the same transformations.

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

  • Dominator থেকে back edge, natural loop, nested loop আর preheader খুঁজে বের করা, হাতে আর কোডে
  • Loop-invariant code motion: কোন নির্দেশ সরানো যায়, পাঁচটি শর্ত, আর কেন শূন্য দিয়ে ভাগ সবচেয়ে বড় ফাঁদ
  • Induction variable আর strength reduction, wrap-এর হিসাবসহ সঠিকতার প্রমাণ
  • Loop unrolling, unswitching, fusion, interchange আর vectorization: কী লাভ, কী দাম
  • প্রতিটি রূপান্তর চালিয়ে যাচাই, আর সত্যিকারের Clang-এর -Rpass remark আর assembly পড়া

১ · কেন loop — program-এর সময় যেখানে কাটে

বাজারঘরের একজন ডেলিভারি কর্মীর কথা ভাবুন। ৩০টি বাড়ির প্রতিটিতে ঢোকার আগে তিনি অফিসে ফোন করে জানতে চান, আজ কিলোমিটারপ্রতি ভাড়া কত; উত্তর সারাদিন একই। বুদ্ধিমান কর্মী বেরোনোর আগে একবার জেনে কাগজে লিখে রাখেন। Compiler-এর ভাষায় এটি loop-invariant code motion: loop-এর ভেতরে যে হিসাব প্রতিবার একই ফল দেয়, তাকে loop-এর আগে একবার করা। আরেকটি চেনা কৌশল: ৪টি করে ডিমের ট্রে গুনতে কেউ প্রতিবার “ট্রে নম্বর × ৪” গুণ করেন না, আগের সংখ্যায় ৪ যোগ করেন। এর নাম strength reduction.

Loop নিয়ে আলাদা পর্ব কেন? কারণ একটি program-এর চলার সময়ের বড় অংশ সাধারণত কয়েকটি loop-এর ভেতরে কাটে: loop-এর বাইরের একটি নির্দেশ একবার চলে, ভেতরেরটি হাজারবার। পর্ব ৬৫-এর শেষে এর একটি সত্যিকারের প্রমাণ এসেছে: bazar.haat-এ পর্ব ৬৫-এর পুরো pipeline চলা নির্দেশ ৭৪ থেকে নামিয়েছে মাত্র ৭২-এ। বাকি সম্ভাবনা loop-এর ভেতরে: পর্ব ৬২-এর lowering প্রতিটি ধ্রুবককে তার ব্যবহারের ঠিক আগে নিজের temp-এ বসায়, তাই while total < 5000 { total = total + 1250; rounds = rounds + 1; }-এর তিনটি const প্রতি ঘুরে আবার চলে। পর্ব ৬৫-এর কোনো pass কোড এক block থেকে অন্য block-এ সরায় না, তাই এগুলো ছোঁয়নি।

এই পর্বে চারটি কাজ: loop খোঁজা, invariant কোড বাইরে আনা, গুণকে যোগে নামানো আর দেহ দুবার লেখা (unrolling); বাকি রূপান্তর অংশ ৭-এ। আগের পর্বের কোড হুবহু নেওয়া: Haat IR আর run_ir পর্ব ৬২-এর, dominator পর্ব ৬৩-এর, liveness পর্ব ৬৪-এর, আর copy propagation, DCE ও block জোড়া পর্ব ৬৫-এর haat_opt.py থেকে। নতুন কোড haat_loop.py-তে।

রূপান্তরকী করেএই পর্বে
Loop-invariant code motion (LICM)প্রতি ঘুরে একই ফলের হিসাব loop-এর আগেকোড, অংশ ৩–৪
Strength reductioni * k-এর বদলে প্রতি ঘুরে যোগকোড, অংশ ৫
Unrollingদেহ কয়েকবার পরপর, কম jump আর বড় blockকোড, অংশ ৬
Unswitchinginvariant শর্তের if loop-এর বাইরে, loop দুই কপিঅনুশীলন ১
Fusion, fission, interchangeloop জোড়া, ভাঙা, বা nested loop-এর ক্রম বদলনাম আর কারণ, অংশ ৭
Vectorizationকয়েকটি ঘোরা একটি SIMD নির্দেশেসত্যিকারের Clang, অংশ ৭

২ · Natural loop — dominator দিয়ে loop চেনা

Haat-এর source-এ loop দেখা সহজ: while. কিন্তু IR-এ পৌঁছে সেটি শুধু কয়েকটি block আর edge, একটি চক্র। Optimizer-কে তাই CFG থেকেই loop আবার খুঁজে বের করতে হয়, আর এমনভাবে, যাতে C-এর goto বা অন্য ভাষার break/continue দিয়ে বানানো loop-ও ধরা পড়ে। চাবিকাঠি পর্ব ৬৩-এর dominator: block a, block b-কে dominate করে, যদি entry থেকে b-তে যাওয়ার প্রতিটি পথ a দিয়ে যায়।

সংজ্ঞা ৬৬.১ — back edge আর natural loop
  1. Back edge: CFG-র একটি edge n → h, যেখানে h, n-কে dominate করে। h হলো loop-এর header, আর n একটি latch.
  2. Natural loop: back edge n → h-এর loop হলো h, আর সেই সব block, যেখান থেকে h না ছুঁয়ে n-এ পৌঁছানো যায়। একই header-এর একাধিক back edge থাকলে তাদের loop জুড়ে একটি loop.
  3. Exit: loop-এর ভেতরের block u থেকে বাইরের block e-তে যাওয়া edge (u, e). u-কে বলে exiting block.
  4. Preheader: header-এর ঠিক আগের একটি block, যার একমাত্র successor header, আর loop-এর বাইরে থেকে header-এ আসার প্রতিটি পথ যার মধ্য দিয়ে যায়। Loop-এ ঢোকার আগে এটি ঠিক একবার চলে।

পর্ব ৬২-এ back edge এসেছিল DFS দিয়ে; Haat-এর মতো structured কোডের reducible CFG-তে dominator-এর সংজ্ঞা একই edge দেয়, আর DFS-এর ক্রমের ওপর নির্ভর করে না। goto দিয়ে বানানো irreducible চক্রে (দুই দিক থেকে ঢোকা যায়) natural loop নেই, তাই বেশির ভাগ loop optimization সেখানে চুপ থাকে। মূল গুণটি মনে রাখুন: header loop-এর প্রতিটি block-কে dominate করে, অর্থাৎ এটিই একমাত্র দরজা।

অ্যালগরিদম ৬৬.২ — natural loop খোঁজা
  1. Dominator হিসাব করুন (পর্ব ৬৩-এর Cooper–Harvey–Kennedy পদ্ধতি)।
  2. প্রতিটি edge n → h দেখুন: h যদি n-কে dominate করে, এটি back edge.
  3. Loop-এর body শুরু {h} দিয়ে; n যোগ করে একটি stack-এ রাখুন।
  4. Stack থেকে একটি block তুলে তার প্রতিটি predecessor, যা body-তে নেই, body আর stack-এ যোগ করুন। Header আগে থেকেই body-তে, তাই খোঁজা header পেরিয়ে বাইরে যায় না।
  5. একই header-এর loop জুড়ুন; ছোট loop আগে রাখুন, যাতে ভেতরের loop আগে optimize হয়।

দুটি nested loop-ওয়ালা একটি উদাহরণ নিন, বাজারঘরের গুদামের তাক গোনা। Reference এটি চালালে ছাপে 12 (সত্যিকারের run).

// বাজারঘর: গুদামের তাক — সারি আর কলামের দুই loop
fn boxes(rows: Int, cols: Int) -> Int {
    var r = 0;
    var n = 0;
    while r < rows {
        var c = 0;
        while c < cols {
            n = n + 1;
            c = c + 1;
        }
        r = r + 1;
    }
    return n;
}
print(boxes(3, 4));

Haat IR-এ boxes-এর সাতটি block: B0 (শুরু), B1 (বাইরের শর্ত), B2 (c = const 0), B3 (ভেতরের শর্ত), B4 (ভেতরের দেহ), B5 (r = r + 1), B6 (return n). নিচের stepper অ্যালগরিদম ৬৬.২ চালায়; প্রতিটি মান লেখকের lab-এ haat_loop.py দিয়ে মেলানো।

1B0 → B12B1 → B2, B63B2 → B34B3 → B4, B55B4 → B36B5 → B17B6: return n
হিসাব
ধাপ
ফল
  1. Dominator. পর্ব ৬৩-এর dominators দুই pass-এ স্থির। যেমন B5-এর idom B3: B5-এ যেতে সবসময় B3 পেরোতে হয়।
  2. B4 → B3. B3, B4-কে dominate করে: back edge. Header B3, latch B4.
  3. B5 → B1. idom-এর শিকল B5 → B3 → B2 → B1, তাই B1, B5-কে dominate করে: এটিও back edge.
  4. বাকি edge. যেমন B3 → B5: B5, B3-কে dominate করে না, তাই সামনের edge. মোট back edge দুটি, loop দুটি।
  5. ভেতরের body. {B3} আর latch B4; B4-এর predecessor শুধু B3. Body = {B3, B4}.
  6. বাইরের body. {B1} আর latch B5; তারপর B3, তার predecessor B2 আর B4; B2-এর predecessor B1-এ খোঁজা থামে। ভেতরের loop পুরোটাই এর ভেতরে।
  7. Exit আর preheader. ভেতরেরটি বেরোয় B3 → B5 দিয়ে, বাইরেরটি B1 → B6 দিয়ে। Header-এর বাইরের predecessor একটিই আর jump-এ শেষ, তাই নতুন block লাগে না: preheader B2 আর B0.

ছবি ৬৬.১ — boxes-এর CFG, দুটি nested loop

লাল তীর: back edge; jump-এর লাইন বাদ, তীরই jump

CFG of boxes: outer loop B1 to B5 shaded blue, inner loop B3 and B4 shaded yellow, back edges in red B0 B1 · বাইরের header B2 · preheader B3 · ভেতরের header B4 · latch B5 · latch B6 r = const 0n = const 0 t1 = r < rowsbranch t1 B2 B6 c = const 0 t2 = c < colsbranch t2 B4 B5 t3 = const 1n = n + t3t4 = const 1c = c + t4 t5 = const 1r = r + t5 return n বাইরের loop: B1–B5 ভেতরের loop: B3, B4 লাল তীর: back edge
ছবি ৬৬.১ — নীল ছায়া বাইরের loop {B1, …, B5}, হলুদ ছায়া ভেতরের {B3, B4}; ভেতরেরটি পুরোপুরি বাইরেরটির মধ্যে, এটিই nesting. B2 ভেতরের loop-এর preheader: loop-এ ঢোকার আগে ঠিক একবার চলে, অথচ নিজে বাইরের loop-এর অংশ। লক্ষ করুন const 1-গুলো: B4-এর দুটি প্রতিটি ভেতরের ঘোরায় চলে।

এবার কোড। natural_loops অ্যালগরিদম ৬৬.২-এর সরাসরি অনুবাদ; পাশের preheader (পুরো ফাইলে) আগে থেকে উপযুক্ত block থাকলে সেটিই ফেরত দেয়, না থাকলে header-এর ঠিক আগে একটি নতুন block বানিয়ে loop-এর বাইরের সব edge সেদিকে ঘোরায়। একটি বিশেষ ক্ষেত্র: function-এর শুরুতেই while থাকলে header নিজেই B0, অথচ run_ir সবসময় B0 থেকে চালায়; তখন header-এর দেহ নতুন নামে যায়, আর B0 হয় খালি preheader.

@dataclass
class Loop:
    header: str                                  # loop-এর একমাত্র ঢোকার দরজা
    body: set                                    # header-সহ সব block
    latches: list                                # back edge-এর উৎস: এখান থেকে আবার header-এ
    exits: list                                  # (u, e): loop-এর u থেকে বাইরের e-তে যাওয়ার edge

def bnum(b): return int(b[1:])

def back_edges(fn, idom):                        # b → h, যেখানে h, b-কে dominate করে
    return [(b, h) for b in sorted(idom, key=bnum) for h in succs(fn, b) if h in idom and dominates(idom, h, b)]

def natural_loops(fn):                           # প্রতিটি header-এর একটি loop; ভেতরের (ছোট) loop আগে
    idom, P, loops = dominators(fn), preds(fn), {}
    for b, h in back_edges(fn, idom):
        L = loops.setdefault(h, Loop(h, {h}, [], []))
        L.latches.append(b); stack = [b] if b not in L.body else []
        L.body |= set(stack)
        while stack:                             # latch থেকে predecessor ধরে পেছনে; header-এ এসে থামে
            for p in P[stack.pop()]:
                if p not in L.body and p in idom: L.body.add(p); stack.append(p)
    for L in loops.values():
        L.exits = [(u, e) for u in sorted(L.body, key=bnum) for e in succs(fn, u) if e not in L.body]
    return sorted(loops.values(), key=lambda L: (len(L.body), bnum(L.header)))

পুরো haat_loop.py (preheader-এর বিশেষ ক্ষেত্রসহ) অংশ ৮-এর ভাঁজে। নিচের ব্লক boxes আর bazar.haat-এর <main>-এ loop খোঁজে, তারপর একটি ছোট function-এ দেখায় কখন নতুন preheader বানাতে হয়।

# ধাপ ১: dominator থেকে back edge, natural loop আর preheader
from haat_loop import *                          # natural_loops, preheader … (+ haat_ir, haat_ssa, haat_dfa)
for path, name in [("boxes.haat", "boxes"), ("examples/bazar.haat", "<main>")]:
    fn = compile_ir(open(path, encoding="utf-8").read()).funcs[name]
    idom = dominators(fn)
    print(f"{name}: idom", ", ".join(f"{b}→{idom[b]}" for b in sorted(idom, key=bnum) if b != "B0"))
    print("  back edge:", ", ".join(f"{b}→{h}" for b, h in back_edges(fn, idom)))
    for L in natural_loops(fn):
        print(f"  loop {L.header}: body {sorted(L.body, key=bnum)}")
        print(f"    latch {L.latches}, exit {L.exits}")
src = """fn fill(n: Int) -> Int {
    var s = 0;
    if n > 5 { s = 1; }
    while s < n { s = s + 2; }
    return s;
}"""
fn = compile_ir(src).funcs["fill"]
L = natural_loops(fn)[0]
print("fill: header", L.header, "· বাইরের predecessor", [p for p in preds(fn)[L.header] if p not in L.body])
print("নতুন preheader:", preheader(fn, L))
print(show_ir(fn))

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

boxes: idom B1→B0, B2→B1, B3→B2, B4→B3, B5→B3, B6→B1
  back edge: B4→B3, B5→B1
  loop B3: body ['B3', 'B4']
    latch ['B4'], exit [('B3', 'B5')]
  loop B1: body ['B1', 'B2', 'B3', 'B4', 'B5']
    latch ['B5'], exit [('B1', 'B6')]
<main>: idom B1→B0, B2→B1, B3→B1
  back edge: B2→B1
  loop B1: body ['B1', 'B2']
    latch ['B2'], exit [('B1', 'B3')]
fill: header B2 · বাইরের predecessor ['B0', 'B1']
নতুন preheader: B5
fn fill(n):
B0:
  s = const 0
  t1 = const 5
  t2 = n > t1
  branch t2 B1 B5
B1:
  s = const 1
  jump B5
B5:
  jump B2
B2:
  t3 = s < n
  branch t3 B3 B4
B3:
  t4 = const 2
  s = s + t4
  jump B2
B4:
  return s

boxes-এর ফল stepper-এর সঙ্গে হুবহু এক; ভেতরের loop আগে, কারণ তালিকা আকার অনুযায়ী সাজানো। bazar-এর <main>-এ একটিই loop. fill-এ header B2-তে বাইরে থেকে দুটি পথ আসে (then-শাখা B1 আর সরাসরি B0), তাই নতুন block B5 দুটিকেই নেয়; এখন খালি, কিন্তু অংশ ৩-এ সরানো নির্দেশ এখানেই বসবে।

৩ · Loop-invariant code motion — কী সরানো যায়

একটি নির্দেশ loop-invariant, যদি loop-এর প্রতিটি ঘোরায় সে একই মান দেয়। সংজ্ঞাটি নিজের ওপর ভর করে, তাই হিসাব হয় fixpoint পর্যন্ত:

সংজ্ঞা ৬৬.৩ — loop-invariant নির্দেশ

Loop L-এর ভেতরের নির্দেশ x = a op b (বা x = op a, x = a, x = const k) invariant, যদি তার প্রতিটি operand হয় (ক) L-এর ভেতরে কোথাও লেখা হয় না, অথবা (খ) L-এর ভেতরে ঠিক একবার লেখা হয়, আর সেই লেখাটি নিজেই invariant. const-এর কোনো operand নেই, তাই সেটি সবসময় invariant.

Invariant হলেই সরানো চলে না: নির্দেশটি এখন preheader-এ একবার চলবে, আর program-এর দেখা যায় এমন আচরণ (ছাপা লাইন, error, ফেরত মান) বদলালে চলবে না। Haat IR-এর জন্য চারটি শর্ত:

শর্ত ৬৬.৪ — s: x = …-কে preheader-এ সরানো যায়, যদি
  1. ধরন: s একটি const, copy, bin বা un, যার কোনো side effect নেই। call, print, শাখা আর @x ধরনের global কখনো নয়: call ছাপতে বা global বদলাতে পারে, আর global পড়া নিজেই error দিতে পারে ('k' is not initialized yet, সিদ্ধান্ত ১৮)।
  2. একটিই লেখা: x loop-এর ভেতরে শুধু s-এ লেখা হয়।
  3. পুরোনো মান লাগে না: header-এর শুরুতে x live নয় (পর্ব ৬৪-এর liveness). অর্থাৎ loop-এর ভেতরে বা loop-এর পরে x-এর এমন কোনো পড়া নেই, যা loop-এর আগের মান দেখতে পারে।
  4. নতুন error নয়: s চালালে এমন কোনো runtime error হতে পারে না, যা আগে হতো না। Haat-এ একমাত্র এমন operator / আর % (সিদ্ধান্ত ২৬); এদের শুধু তখনই সরানো যায়, যখন ভাজক একটি নিশ্চিত অশূন্য ধ্রুবক।

লেখকের lab-এ একেকটি শর্ত কোড থেকে বাদ দিয়ে চালানো হয়েছে, সত্যিকারের run. শর্ত ২ ছাড়া while i < 2 { var x = 1; print(x); x = 2; i = i + 1; }-এ x-এর দুটি লেখাই বাইরে যায়, আর 1, 1-এর জায়গায় ছাপা হয় 2, 2. শর্ত ৩ ছাড়া var x = 0;-এর পরে while i < 2 { print(x); x = 5; i = i + 1; } ছাপে 5, 5, reference ছাপে 0, 5. শর্ত ৩ শূন্যবার ঘোরাও ধরে: loop-এর ভেতরে x = 7 আর পরে return x থাকলে n = 0-তে উত্তর হতো 7, ঠিক উত্তর 0.

Aho–Lam–Sethi–Ullman-এর “Dragon book”-এ আরেকটি শর্ত আছে: s-এর block প্রতিটি exiting block-কে dominate করবে, অথবা loop-এর পরে x লাগবে না। শর্ত ৩ “header-এ x live নয়” রূপে লেখায় এটি আপনাআপনি আসে (প্রমাণ অনুশীলন ৪-এ)। Lab-এ শর্তটির একটি মোটা দাগের রূপ রেখে আর বাদ দিয়ে ৬,০০০টি এলোমেলো program চালানো হয়েছে: বাদ দিলে ১৭টিতে বাড়তি নির্দেশ সরে, আউটপুট একটিতেও বদলায় না।

নিচের kisti.haat-এ একটি বাজারঘরের কিস্তির হিসাব। প্রতি মাসে দামের ১০% আর, যদি কিস্তি ভাগ করার লোক থাকে, মাথাপিছু একটি অংশ যোগ হয়। Reference ছাপে 630, 180, 0 (সত্যিকারের run).

// বাজারঘর: কিস্তিতে বিল — loop-এর ভেতরে না বদলানো হিসাব
fn bill(unit: Int, qty: Int, people: Int, months: Int) -> Int {
    var m = 0;
    var paid = 0;
    while m < months {
        let base = unit * qty;
        paid = paid + base / 10;
        if people > 0 {
            paid = paid + base / people;
        }
        m = m + 1;
    }
    return paid;
}
print(bill(120, 5, 4, 3));
print(bill(120, 5, 0, 3));
print(bill(120, 5, 0, 0));

Haat IR-এ loop-এর header B1, দেহ B2 থেকে B4, আর B0 নিজেই preheader (header-এর বাইরের একমাত্র predecessor, jump-এ শেষ)। Header-এর শুরুতে live: m, months, paid, people, qty, unit. Stepper-টি licm-কে নির্দেশে নির্দেশে অনুসরণ করে।

1B1: t1 = m < months2    branch t1 B2 B53B2: base = unit * qty4    t2 = const 105    t3 = base / t26    paid = paid + t37    t4 = const 08    t5 = people > t49    branch t5 B3 B410B3: t6 = base / people11    paid = paid + t612B4: t7 = const 113    m = m + t7
licm-এর সিদ্ধান্ত
সিদ্ধান্ত
B0-তে নতুন
  1. t1 = m < months. m loop-এ লেখা হয়, তাই invariant নয়। Loop-এর শর্ত প্রায় কখনো invariant হয় না।
  2. base = unit * qty. unit, qty loop-এ লেখা হয় না; base একবার লেখা, header-এ live নয়, আর * কখনো error দেয় না। চারটি শর্তই সত্য: B0-তে।
  3. t2 = const 10. ধ্রুবক: সরে। পর্ব ৬২-এর lowering এটি প্রতি ঘোরায় চালাত।
  4. t3 = base / t2. ভাজক t2 পুরো function-এ একবার লেখা const 10, নিশ্চিত অশূন্য: সরে। months = 0 হলেও এটি চলবে, কিন্তু দেখা যায় এমন কিছু বদলায় না।
  5. paid = paid + t3. paid loop-এ দুবার লেখা আর আগের মান পড়ে: থাকে। B3-এর paid = paid + t6-ও থাকে।
  6. t4, t5 = people > t4. তুলনা error দেয় না: দুটিই সরে। শাখাটি থাকে, যদিও তার শর্ত এখন invariant (অনুশীলন ১)।
  7. t6 = base / people. Operand invariant, তবু people শূন্য হতে পারে। Loop-এ ভাগটি চলে শুধু people > 0 হলে; preheader-এ সরালে people = 0-তে নতুন error. শর্ত ৪ ভাঙে।
  8. t7 = const 1. সরে; m = m + t7 থাকে। মোট ছয়টি; দ্বিতীয় রাউন্ডে কিছু বদলায় না।

কেন আউটপুট বদলায় না? (প্রমাণের রূপরেখা) ধরুন s: x = e চারটি শর্ত মেনে preheader P-তে সরানো হলো।

  1. Header loop-এর একমাত্র দরজা, তাই loop-এ প্রতিবার ঢোকার আগে P ঠিক একবার চলে।
  2. e-এর operand-গুলো loop-এ লেখা হয় না (বা আগে সরানো invariant নির্দেশে লেখা), তাই P-তে আর loop-এর প্রতিটি ঘোরায় তাদের মান এক; e-এর মান v একই।
  3. Loop-এর ভেতরে x-এর প্রতিটি পড়া আগের মডেলে s-এর লেখা মানই দেখত: x-এর আর কোনো লেখা নেই (শর্ত ২), আর loop-এর আগের মান কোনো পড়ায় পৌঁছায় না (শর্ত ৩)। সেই মান v; এখনো v.
  4. Loop-এর পরে x-এর যে পড়া loop-এর আগের মান দেখতে পারত, তা শর্ত ৩-এ বাদ; বাকি পড়াগুলো s-এর মান দেখে, যা v (অনুশীলন ৪)।
  5. s-এর side effect নেই আর error দিতে পারে না (শর্ত ১, ৪), তাই যেসব পথে আগে s চলত না (শূন্যবার ঘোরা, বা শর্তের ভেতরে), সেখানে এখন চলায় দেখা যায় এমন কিছু বদলায় না। ∎

কোডে শর্ত ১ আর ২ প্রথম দুটি continue-এ, শর্ত ৩ liveness দিয়ে, শর্ত ৪ risk-এ। একটি নির্দেশ সরলে তার ওপর নির্ভর করা নির্দেশও invariant হতে পারে, তাই রাউন্ড চলে কিছু না বদলানো পর্যন্ত।

def single_consts(fn):                           # যে নাম পুরো function-এ একবারই লেখা, আর তা `const k` দিয়ে
    n = Counter(d for body in fn.blocks.values() for i in body for d in defs(i))
    return {i.dst: i.sym for body in fn.blocks.values() for i in body if i.kind == "const" and n[i.dst] == 1}

def risk(ins, consts):                           # আগে বা বেশিবার চালালে কি নতুন error বা ভুল মান হতে পারে? কারণ, নইলে None
    if ins.kind == "bin" and ins.sym in ("/", "%"):
        k = consts.get(ins.args[1])              # শুধু নিশ্চিত অশূন্য ধ্রুবক ভাজক নিরাপদ
        return None if type(k) is int and k != 0 else "ভাজক শূন্য হতে পারে"
    if ins.kind == "copy" and ins.args[0][0] == "@": return "global: call বদলায়, পড়া error দিতে পারে"
    return None

def licm(fn, unsafe=False, log=None):            # loop-invariant code motion; unsafe=True: ভাগের নিয়ম ভাঙা (ভুল!)
    moved, done = 0, set()
    while (L := next((L for L in natural_loops(fn) if L.header not in done), None)):
        P = preheader(fn, L); done.add(L.header); changed = True
        while changed:                           # একটি সরলে তার ওপর নির্ভর করা নির্দেশও invariant হতে পারে
            changed, live = False, solve(LIVENESS, fn).IN
            inside = Counter(d for b in L.body for i in fn.blocks[b] for d in defs(i))
            consts = single_consts(fn)
            for b in [x for x in rpo(fn) if x in L.body]:
                for ins in list(fn.blocks[b]):
                    x = ins.dst
                    if ins.kind not in ("const", "copy", "bin", "un") or not x or x[0] == "@": continue
                    if inside[x] != 1 or any(inside[a] for a in ins.args): continue    # x একবার লেখা, operand অপরিবর্তিত
                    why = "loop-এর শুরুতে পুরোনো মান লাগে" if x in live[L.header] else risk(ins, consts)
                    if unsafe and why == "ভাজক শূন্য হতে পারে": why = None            # জেনেশুনে ভুল
                    if log is not None: log.append((b, str(ins), why or f"→ {P}"))
                    if why: continue
                    fn.blocks[b].remove(ins); fn.blocks[P].insert(-1, ins); inside[x] = 0
                    moved += 1; changed = True
    return moved
# ধাপ ২: kisti.haat-এর bill-এ LICM — কী সরল, কী সরল না আর কেন; তারপর আউটপুট আর গোনা মেলানো
from haat_loop import *
src = open("kisti.haat", encoding="utf-8").read()
mod = compile_ir(src)
before, steps0 = run_lines(mod), run_ir(mod, out=lambda s: None)
log = []
moved = licm(mod.funcs["bill"], log=log)
seen = {}
for b, ins, why in log: seen[ins] = (b, why)    # একই নির্দেশ একাধিক রাউন্ডে এলে শেষ সিদ্ধান্ত
for ins, (b, why) in seen.items():
    print(f"{b}: {ins:20} {why}")
print(show_ir(mod.funcs["bill"]))
after = run_lines(mod)
print("আউটপুট:", after, "· আগের সঙ্গে এক:", after == before)
print(f"সরানো নির্দেশ: {moved} · চলা নির্দেশ: {steps0} → {run_ir(mod, out=lambda s: None)}")

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

B2: base = unit * qty    → B0
B2: t2 = const 10        → B0
B2: t3 = base / t2       → B0
B2: t4 = const 0         → B0
B2: t5 = people > t4     → B0
B3: t6 = base / people   ভাজক শূন্য হতে পারে
B4: t7 = const 1         → B0
fn bill(unit, qty, people, months):
B0:
  m = const 0
  paid = const 0
  base = unit * qty
  t2 = const 10
  t3 = base / t2
  t4 = const 0
  t5 = people > t4
  t7 = const 1
  jump B1
B1:
  t1 = m < months
  branch t1 B2 B5
B2:
  paid = paid + t3
  branch t5 B3 B4
B3:
  t6 = base / people
  paid = paid + t6
  jump B4
B4:
  m = m + t7
  jump B1
B5:
  return paid
আউটপুট: ['630', '180', '0'] · আগের সঙ্গে এক: True
সরানো নির্দেশ: 6 · চলা নির্দেশ: 119 → 101

সাতটি সিদ্ধান্ত stepper-এর সঙ্গে হুবহু: ছয়টি B0-তে, t6 = base / people থাকে। নতুন IR-এ loop-এর ভেতরে বাকি শুধু সেই নির্দেশ, যারা সত্যিই প্রতি ঘোরায় বদলায় বা যাদের সরানো নিরাপদ নয়। তিনটি call মিলিয়ে চলা নির্দেশ ১১৯ থেকে ১০১; আউটপুট reference-এর সঙ্গে এক। লক্ষ করুন branch t5 B3 B4: শর্তটি এখন loop-এর আগেই জানা, তবু প্রতি ঘোরায় পরীক্ষা হয়।

৪ · ভাগ সরানোর বিপদ — জেনেশুনে একটি ভুল

শর্ত ৪ কতটা জরুরি, তা দেখতে licm-এ একটি সুইচ আছে: unsafe=True দিলে ভাগের নিয়ম উপেক্ষা হয়। kisti.haat-এ তখন t6 = base / people-ও B0-তে যায়, আর ফল (লেখকের lab-এ, সত্যিকারের run):

reference:     630
               180
               0
unsafe LICM:   630
               9:32: runtime error: division by zero

দ্বিতীয় call-এ people = 0: আগে ভাগটি if people > 0-এর পাহারায় কখনো চলত না, এখন preheader-এ শর্তের আগেই চলে। তৃতীয় call-এ (months = 0) loop একবারও ঘোরে না, তবু preheader চলে, তাই সেখানেও একই error হতো। আরেকটি ঝুঁকি: error আগে ঘটলে তার আগের ছাপাগুলোও বদলায়, কারণ error-এর আগের আউটপুট program-এর অংশ (সিদ্ধান্ত ২৬)।

এটি শুধু Haat-এর খুঁতখুঁতে নিয়ম নয়। শূন্য দিয়ে ভাগের ফল প্রতিটি স্তরে আলাদা: x86-64-এর idiv নির্দেশ একটি divide-error exception তোলে, Linux-এ যা সাধারণত SIGFPE-তে program থামায়; ARM-এর AArch64-এ sdiv চুপচাপ 0 দেয়; RISC-V-এর div দেয় সব bit 1, অর্থাৎ −১, কোনো trap ছাড়া। LLVM IR-এ sdiv শূন্য দিয়ে হলে undefined behavior (পর্ব ৬৮-এর অংশ ৫), আর Haat-এ একটি নির্দিষ্ট runtime error. তাই “ভাগ সরানো নিরাপদ কি না” প্রশ্নের উত্তর দেয় ভাষার semantics, hardware নয়।

বাস্তব compiler-ও এই নিয়ম মানে। নিচের C function-এ total / people invariant, কিন্তু শর্তের ভেতরে:

long share(long total, long people, long n, const long *w) {
    long s = 0;
    for (long i = 0; i < n; i++)
        if (w[i] > 0) s += total / people;
    return s;
}

PyPI-র ziglang 0.17.1-এর ভেতরের Clang 22.1.8, -O2 -S -emit-llvm, x86-64 Linux target, লেখকের lab-এ সত্যিকারের run. Loop দুবার করে unroll হয়েছে, কিন্তু ভাগটি প্রতিটি কপির নিজের if.then-এ রইল, preheader-এ নয় (block-এর নাম আর sdiv-এর লাইন বেছে নেওয়া):

for.body.preheader:         ; preds = %entry
if.then:                    ; preds = %for.body
  %div = sdiv i64 %total, %people
if.then.1:                  ; preds = %for.inc
  %div.1 = sdiv i64 %total, %people
if.then.epil:               ; preds = %for.body.epil.preheader
  %div.epil = sdiv i64 %total, %people

LLVM-এর LICM-এর documentation আর source অনুযায়ী (version-ভেদে খুঁটিনাটি বদলায়), একটি নির্দেশ তখনই loop-এর বাইরে যায়, যখন সেটি speculate করা নিরাপদ, অর্থাৎ বাড়তি পথে চালালেও UB হয় না, অথবা যখন loop-এ ঢুকলে সেটি নিশ্চিতভাবে চলে। এখানে কোনোটিই খাটে না: people শূন্য হতে পারে, আর w[i] > 0 কখনো সত্য না-ও হতে পারে।

এলোমেলো test সব ধরে না। লেখকের lab-এ ৩,০০০টি haat_gen আর ৩,০০০টি loop-ভরা haat_loopgen program-এ unsafe=True চালানো হয়েছে, সত্যিকারের run. ২,৩৭১টি program-এ সেটি এমন একটি ভাগ সরিয়েছে, যা নিরাপদ LICM সরায় না; কিন্তু আউটপুট বদলেছে মাত্র ৪০০টিতে। বাকিগুলোতে ভাজক কখনো শূন্য হয়নি, বা loop অন্তত একবার ঘুরেছে আর শর্তের পথটি চলেছে। ভুল optimization-কে ধরতে হলে সীমার মান নিয়ে হাতে বাছা উদাহরণ (যেমন bill(120, 5, 0, 0)) রাখতেই হবে।

৫ · Induction variable আর strength reduction

ডিমের ট্রের উদাহরণ: ট্রে নম্বর i (০ থেকে), প্রতি ট্রেতে ৪টি ডিম, প্রথম ডিমের ক্রমিক নম্বর i * 4 + 1. Reference ছাপে 1, 5, 9, 12 (সত্যিকারের run).

// বাজারঘর: ডিমের ট্রে — প্রতি ট্রেতে ৪টি ডিম
fn label_trays(trays: Int) -> Int {
    var i = 0;
    var last = 0;
    while i < trays {
        let first = i * 4 + 1;
        print(first);
        last = first + 3;
        i = i + 1;
    }
    return last;
}
print(label_trays(3));

i প্রতি ঘোরায় 1 করে বাড়ে, i * 4 বাড়ে 4 করে: দুটিই induction variable, তবে আলাদা জাতের।

সংজ্ঞা ৬৬.৫ — basic আর derived induction variable
  1. Basic: i, যার loop-এর ভেতরে একমাত্র লেখা i = i + d বা i = i - d, আর d loop-invariant.
  2. Derived: t, যার loop-এর ভেতরে একমাত্র লেখা t = i * k (বা k * i), যেখানে i basic আর k invariant. প্রতি ঘোরায় t বাড়ে d · k করে।
অ্যালগরিদম ৬৬.৬ — t = i * k-এর strength reduction
  1. দুটি নতুন temp s আর step নিন। Preheader-এ: s = i * k আর step = d * k.
  2. i-এর লেখা i = i + d-এর ঠিক পরে বসান s = s + step (- হলে s = s - step).
  3. t = i * k-এর জায়গায় t = s. একই (i, k)-এর আরও গুণ থাকলে সেগুলোও s নেয়।
  4. এখন t = s একটি copy; পর্ব ৬৫-এর copy propagation আর DCE সেটি মুছে দেবে।

Wrap-এর জগতে এটি কেন হুবহু ঠিক? (প্রমাণ) দাবি: loop-এর ভেতরে, s-এর লেখার পরে আর i-এর পরের লেখার আগে, সবসময় s = i · k, যেখানে সব হিসাব ৬৪-bit wrap-এর (সিদ্ধান্ত ১৩)।

  1. Haat-এর +, - আর * হলো wrap করা, অর্থাৎ mod 264-এর হিসাব, প্রতিনিধি −263 থেকে 263 − 1-এর মধ্যে। Mod 264-এর পূর্ণসংখ্যা একটি ring, তাই বণ্টন-নিয়ম খাটে: (i + d) · k ≡ i · k + d · k.
  2. শুরু: preheader-এ s = i · k, loop-এ ঢোকার মুহূর্তের i দিয়ে।
  3. ধাপ: i-এর একমাত্র লেখা i' = i + d, আর ঠিক পরেই s' = s + d · k = i · k + d · k ≡ (i + d) · k = i' · k. মাঝে কোনো নির্দেশ নেই, তাই কোনো পড়া অমিল দেখে না।
  4. অতএব যেখানে আগে t = i * k চলত, সেখানে s-এর মান হুবহু একই; Int-এর প্রতিনিধি একটিই, তাই ছাপা সংখ্যাও এক। ∎

C-এর unsigned-এও একই যুক্তি খাটে। Signed long-এ overflow undefined behavior, তাই সেখানে compiler “overflow হবে না” ধরে নেয়, nsw-এর প্রতিশ্রুতিতে (পর্ব ৬৮-এর অংশ ৪)।

1B0: t2 = const 42    t6 = const 13    t7 = i * t24    t8 = t6 * t25B1: t1 = i < trays6B2: t3 = t77    first = t3 + t48    print first9    i = i + t610    t7 = t7 + t8
চলার সময়ের মান (trays = 3)
i
t7 (s)
t3
i * 4
  1. খোঁজা. LICM-এর পরে t2 = const 4 আর t6 = const 1 loop-এর বাইরে। i-এর loop-এ একমাত্র লেখা i = i + t6, আর t6 invariant: i একটি basic induction variable, d = t6. t3 = i * t2-এ t2 invariant: t3 derived, k = t2.
  2. রূপান্তর. Preheader-এ t7 = i * t2 (s) আর t8 = t6 * t2 (step); i = i + t6-এর ঠিক পরে t7 = t7 + t8; আর গুণটি হয়ে যায় copy t3 = t7. Loop-এর ভেতরে আর কোনো * নেই।
  3. Preheader চলে. i = 0, তাই t7 = 0 · 4 = 0, আর t8 = 1 · 4 = 4. এখানে দুটি গুণ, কিন্তু loop-এ ঢোকার আগে একবারই।
  4. প্রথম ঘোরা. t3 = t7 = 0, first = 1, ছাপা 1. তারপর i = 1, আর সঙ্গে সঙ্গে t7 = 0 + 4 = 4 = 1 · 4.
  5. দ্বিতীয় ঘোরা. t3 = 4, first = 5, ছাপা 5; i = 2, t7 = 8.
  6. তৃতীয় ঘোরা. t3 = 8, first = 9, ছাপা 9; i = 3, t7 = 12. প্রতিটি বিন্দুতে t7 = i · 4, ঠিক প্রমাণের দাবি।
  7. বেরোনো. 3 < 3 মিথ্যা, loop শেষ; return last দেয় 12, আর <main> ছাপে 12. আউটপুট 1, 5, 9, 12: reference-এর সঙ্গে হুবহু।
def fresh_temp(fn):                              # function-এ এখনো ব্যবহার না হওয়া পরের temp
    used = [int(x[1:]) for body in fn.blocks.values() for i in body for x in [i.dst, *i.args] if x and is_temp(x)]
    return f"t{max(used, default=0) + 1}"

def strength_reduce(fn, log=None):               # derived induction variable t = i * k -> যোগ দিয়ে চলা s
    n = 0
    for L in preheaders(fn):
        where = {}                               # loop-এর ভেতরে প্রতিটি নামের লেখা: [(b, ins)]
        for b in L.body:
            for i in fn.blocks[b]:
                for d in defs(i): where.setdefault(d, []).append((b, i))
        inv = lambda a: a[0] != "@" and a not in where                   # loop-এ লেখা হয় না
        basic = {i.dst: (b, i) for x, [(b, i)] in [(x, w) for x, w in where.items() if len(w) == 1]
                 if i.kind == "bin" and i.sym in "+-" and i.args[0] == i.dst and inv(i.args[1])}   # i = i ± d
        made = {}
        for b in sorted(L.body, key=bnum):
            for ins in list(fn.blocks[b]):
                if ins.kind != "bin" or ins.sym != "*" or len(where.get(ins.dst, ())) != 1: continue
                a, c = ins.args
                iv, m = (a, c) if a in basic and inv(c) else (c, a) if c in basic and inv(a) else (None, None)
                if iv is None or ins.dst == iv: continue
                if (iv, m) not in made:          # প্রথমবার: preheader-এ s = i * m আর step = d * m
                    P = preheader(fn, L); ub, upd = basic[iv]
                    s = fresh_temp(fn); fn.blocks[P].insert(-1, Ins("bin", s, [iv, m], "*"))
                    st = fresh_temp(fn); fn.blocks[P].insert(-1, Ins("bin", st, [upd.args[1], m], "*"))
                    body = fn.blocks[ub]; body.insert(body.index(upd) + 1, Ins("bin", s, [s, st], upd.sym))
                    made[iv, m] = s
                    if log is not None: log.append((P, f"{s} = {iv} * {m}", f"{st} = {upd.args[1]} * {m}", f"{s} = {s} {upd.sym} {st}"))
                fn.blocks[b][fn.blocks[b].index(ins)] = Ins("copy", ins.dst, [made[iv, m]]); n += 1
    return n

Haat IR interpreter গুণ আর যোগকে সমান এক ধরে গোনে, তাই strength reduction-এর লাভ দেখতে হয় নির্দেশের ধরন ধরে। profile প্রতিটি block-এর list-কে একটি গোনা subclass দিয়ে মুড়ে run_ir চালায় (পর্ব ৬৪-এর Spy-এর মতো), haat_ir.py না বদলে।

# ধাপ ৩: tray.haat — LICM, তারপর i * 4-এর strength reduction, তারপর unrolling; প্রতি ধাপে চালিয়ে গোনা
from haat_loop import *
from haat_opt import optimize                    # পর্ব ৬৫-এর pipeline, হুবহু: copy_prop, dce, cleanup …
src = open("tray.haat", encoding="utf-8").read()
mod = compile_ir(src); fn = mod.funcs["label_trays"]
want = run_lines(mod)
def report(step):
    p = profile(mod); got = run_lines(mod)
    print(f"{step:15} চলা {sum(p.values())} · * {p['*']} · + {p['+']} · jump {p['jump']}",
          "· আউটপুট এক" if got == want else "· আউটপুট আলাদা!")
report("শুরু")
licm(fn); report("LICM")
log = []; strength_reduce(fn, log); report("strength red.")
print("   preheader", log[0][0] + ":", log[0][1], "·", log[0][2])
print("   i-এর পরে:", log[0][3])
optimize(fn); report("+ পর্ব ৬৫")
unroll2(fn); optimize(fn); report("unroll ×2 + ৬৫")
print("\n".join(show_ir(fn).split("\n")[9:]))

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

শুরু            চলা 47 · * 3 · + 9 · jump 4 · আউটপুট এক
LICM            চলা 39 · * 3 · + 9 · jump 4 · আউটপুট এক
strength red.   চলা 44 · * 2 · + 12 · jump 4 · আউটপুট এক
   preheader B0: t7 = i * t2 · t8 = t6 * t2
   i-এর পরে: t7 = t7 + t8
+ পর্ব ৬৫       চলা 39 · * 0 · + 12 · jump 4 · আউটপুট এক
unroll ×2 + ৬৫  চলা 37 · * 0 · + 12 · jump 2 · আউটপুট এক
B1:
  t1 = i < trays
  branch t1 B2 B3
B2:
  first = t7 + t4
  print first
  last = first + t5
  i = i + t4
  t7 = t7 + t2
  t1 = i < trays
  branch t1 B4 B3
B3:
  return last
B4:
  first = t7 + t4
  print first
  last = first + t5
  i = i + t4
  t7 = t7 + t2
  jump B1

LICM চারটি const বের করে: ৪৭ থেকে ৩৯। Strength reduction-এর পরে মোট ৪৪, কারণ গুণের বদলে এখন একটি copy আর একটি যোগ, আর preheader-এ দুটি গুণ; কিন্তু loop-এ গুণ শূন্য। পর্ব ৬৫-এর pipeline copy t3 = t7 মোছে, i = 0 জানা বলে t7 = i * t2-কে const 0 করে, আর t8 (= 4) আগের t2-এর সমান বলে value numbering সেটিও মোছে: ৩৯টি নির্দেশ, একটিও গুণ নেই। শেষের IR অংশ ৬-এর: দেহ দুবার, jump ৪ থেকে ২।

বাস্তব compiler-এ strength reduction সবচেয়ে বেশি দেখা যায় array-র ঠিকানায়। C-তে s += tray[i * 4]-এর ঠিকানা tray + i * 32 বাইট। Clang 22.1.8 -O2 -S (সত্যিকারের run) loop-এ কোনো গুণ রাখেনি; loop চারবার করে unroll করা, আর pointer %r8 প্রতি ঘোরায় 128 বাইট এগোয়:

.LBB2_9:                                # =>This Inner Loop Header: Depth=1
	addq	-96(%r8), %rax
	addq	-64(%r8), %rax
	addq	-32(%r8), %rax
	addq	(%r8), %rax
	addq	$4, %rdx
	subq	$-128, %r8
	cmpq	%rdx, %rsi
	jne	.LBB2_9

চারটি পড়া ৩২ বাইট ব্যবধানে (−৯৬, −৬৪, −৩২, ০): এটিই i * 4, যোগে নামানো। subq $-128 মানে 128 যোগ, ছোট encoding-এর কৌশল। বাকি ঘোরার ছোট loop-টিতে offset বাড়ে addq $32, %rdx করে।

৬ · Loop unrolling — দেহ দুবার, পরীক্ষা কম

প্রতিটি ঘোরার শেষে একটি jump header-এ ফেরে, আর header-এ একটি তুলনা আর শাখা। দেহ ছোট হলে এই খরচ দেহের কাজের তুলনায় বড়। Loop unrolling দেহটি কয়েকবার পরপর লিখে ঘোরার সংখ্যা কমায়। বাস্তব CPU-তে লাভ আরও আছে: বড় block-এ scheduler পাশাপাশি চালানোর মতো স্বাধীন নির্দেশ বেশি পায়, আর শাখা কম মানে pipeline-এ ভুল অনুমানের ঝুঁকিও কম (কম্পিউটার আর্কিটেকচারের পর্ব ৩৬)। দাম: কোড বড় হয়, instruction cache-এ চাপ বাড়ে, আর বেশি register লাগে।

ঘোরার সংখ্যা চলার সময়ে জানা গেলে (যেমন trays) দুটি পথ। Clang মূল loop-এ দুই বা চার ঘোরা একসঙ্গে চালায়, আর বাকি ঘোরার জন্য একটি ছোট “epilogue” loop রাখে। সহজ আর সবসময় সঠিক পথটি unroll2-এর: দেহের একটি কপি, শর্তসহ; আসল দেহের back edge যায় কপির header-এ, কপিরটি আসল header-এ। প্রতিটি কপিতে শর্ত থাকে, তাই বিজোড় সংখ্যায়ও ভুল নেই।

def unroll2(fn, limit=40):                       # ভেতরের প্রতিটি ছোট loop-এর দেহ দুবার; শর্ত দুই কপিতেই থাকে
    n = 0
    for L in natural_loops(fn):
        if any(M.header in L.body and M.header != L.header for M in natural_loops(fn)): continue   # ভেতরে আরেক loop
        if sum(len(fn.blocks[b]) for b in L.body) > limit: continue
        top = max(map(bnum, fn.blocks)); ren = {b: f"B{top + k + 1}" for k, b in enumerate(sorted(L.body, key=bnum))}
        for b in sorted(L.body, key=bnum):       # কপি: loop-এর ভেতরের লক্ষ্য কপিতে, শুধু back edge আসল header-এ
            fn.blocks[ren[b]] = [replace(i, args=list(i.args), targets=[L.header if t == L.header else ren.get(t, t)
                                 for t in i.targets]) for i in fn.blocks[b]]
        for b in L.latches:                      # আসল দেহের back edge এখন কপির header-এ
            fn.blocks[b][-1].targets = [ren[L.header] if t == L.header else t for t in fn.blocks[b][-1].targets]
        n += 1
    return n

কপি করা loop নিজে নির্দেশ কমায় না। কিন্তু আসল দেহের শেষ jump এখন কপির header-এ যায়, আর সেখানে আসার পথ এটিই; তাই পর্ব ৬৫-এর cleanup দুটি block জুড়ে একটি jump মুছে দেয়। অংশ ৫-এর ব্লকের শেষ IR-এ ঠিক এটি: চলা নির্দেশ ৩৯ থেকে ৩৭। নাম বদলানো লাগে না: কোড SSA নয়, আর প্রতিটি কপি নিজের লেখা নিজেই পড়ে।

Clang কী করে, দেখা যায় তার optimization remark-এ। চারটি C loop (অংশ ৪-এর share, ডিমের ট্রে, প্রতিটি দামে price[i] * (vat * base) / 100 যোগ, আর কার্টের যোগফল) একটি ফাইলে, -O2, সত্যিকারের run. সতর্কতা: -Rpass= একটিই regex নেয়, আলাদা আলাদা দিলে শুধু শেষেরটি খাটে (লেখকের প্রথম চেষ্টায় সত্যিই ঘটেছে); আর zig-এর cache একই ফাইল আবার compile না করে আগের ফল দেয়, তাই remark চাইলে cache খালি করে চালাতে হয়।

~/loop $ python -m ziglang cc -O2 -c --target=x86_64-linux-gnu -fno-sanitize=undefined \
    '-Rpass=licm|loop-unroll|loop-vectorize' '-Rpass-missed=licm|loop-vectorize' loops.c -o loops.o
loops.c:4:45: remark: hoisting mul [-Rpass=licm]
loops.c:3:5: remark: the cost-model indicates that vectorization is not beneficial [-Rpass-missed=loop-vectorize]
loops.c:3:5: remark: the cost-model indicates that interleaving is not beneficial [-Rpass-missed=loop-vectorize]
loops.c:3:5: remark: unrolled loop by a factor of 2 with run-time trip count [-Rpass=loop-unroll]
loops.c:9:5: remark: the cost-model indicates that vectorization is not beneficial [-Rpass-missed=loop-vectorize]
loops.c:9:5: remark: the cost-model indicates that interleaving is not beneficial [-Rpass-missed=loop-vectorize]
loops.c:9:5: remark: unrolled loop by a factor of 2 with run-time trip count [-Rpass=loop-unroll]
loops.c:16:5: remark: the cost-model indicates that vectorization is not beneficial [-Rpass-missed=loop-vectorize]
loops.c:16:5: remark: the cost-model indicates that interleaving is not beneficial [-Rpass-missed=loop-vectorize]
loops.c:16:5: remark: unrolled loop by a factor of 4 with run-time trip count [-Rpass=loop-unroll]
loops.c:23:5: remark: vectorized loop (vectorization width: 2, interleaved count: 2) [-Rpass=loop-vectorize]

(source-লাইনের অংশ বাদ।) লাইন ৩, ৯ আর ১৬-এর loop “run-time trip count” নিয়ে unroll হয়েছে, তাই epilogue লাগে; share-এর IR-এ তার চিহ্ন %xtraiter = and i64 %n, 1. প্রথম loop-এ hoisting mul: vat * base বাইরে গেছে, assembly-তেও imulq %rcx, %r8 loop-এর আগের block-এ। শুধু শেষ loop vectorize হয়েছে (অংশ ৭)।

ঘোরার সংখ্যা ধ্রুবক আর ছোট হলে compiler পুরো loop খুলে ফেলতে পারে, আর ফল একটি সূত্রে লেখা গেলে loop-টিই মুছে দিতে পারে: পর্ব ৬৮-এ Clang একটি rounds loop-কে udiv-এর সূত্রে নামিয়েছে, আর সেখানেই দেখা গেছে কেন Haat-এর wrap সেটি আটকায়।

৭ · আরও loop রূপান্তর — unswitching থেকে vectorization

Loop unswitching. অংশ ৩-এর bill-এ branch t5 B3 B4-এর শর্ত loop-invariant, তবু প্রতি ঘোরায় পরীক্ষা হয়। Unswitching শাখাটি loop-এর বাইরে আনে আর loop-কে দুই কপি করে: একটিতে শর্ত সবসময় সত্য, অন্যটিতে মিথ্যা। দাম কোডের আকার; অনুশীলন ১-এ আপনি এটি লিখবেন।

Loop fusion আর fission. একই array-র ওপর পরপর দুটি loop জুড়লে প্রতিটি উপাদান cache-এ থাকতে থাকতেই দুটি কাজ হয়; fission উল্টো, বড় loop ভেঙে ছোট কয়েকটি, যাতে সহজে vectorize হয়। দুটিই বৈধ শুধু যদি ঘোরাগুলোর নির্ভরতার ক্রম না বদলায়; এটি dependence analysis-এর প্রশ্ন।

Loop interchange. সারি ধরে রাখা দুই মাত্রার array-তে ভেতরের loop কলাম ধরে ঘুরলে প্রতিটি পড়া নতুন cache line-এ পড়ে; loop দুটির ক্রম উল্টালে পড়া পাশাপাশি হয়, ফল একই। কারণ আর মাপ কম্পিউটার আর্কিটেকচারের পর্ব ৪৫ আর পর্ব ৪৮-এ।

Vectorization. কার্টের যোগফলের loop (s += price[i]) Clang vectorize করেছে: “vectorized loop (vectorization width: 2, interleaved count: 2)”. অর্থাৎ একটি SIMD নির্দেশ একসঙ্গে দুটি long যোগ করে, আর দুটি আলাদা যোগফল পাশাপাশি চলে। Assembly-র মূল loop (সত্যিকারের run):

.LBB3_6:                                # =>This Inner Loop Header: Depth=1
	movdqu	(%rdi,%rax,8), %xmm2
	paddq	%xmm2, %xmm1
	movdqu	16(%rdi,%rax,8), %xmm2
	paddq	%xmm2, %xmm0
	addq	$4, %rax
	cmpq	%rax, %rcx
	jne	.LBB3_6

প্রতি ঘোরায় চারটি দাম: paddq একটি ১২৮-bit register-এ দুটি ৬৪-bit সংখ্যা যোগ করে। Width ২, কারণ zig এই target-এ সাধারণ x86-64 CPU ধরে (-###-এ -target-cpu x86-64), যেখানে SSE2 পর্যন্ত নিশ্চিত; AVX2-এর জন্য ফল আলাদা হতো (চালানো হয়নি)। SIMD-এর hardware দিক কম্পিউটার আর্কিটেকচারের পর্ব ৪২-এ। যোগফল দুই ভাগে যোগ করা মানে যোগের ক্রম বদলানো: পূর্ণসংখ্যায় নিরাপদ, floating point-এ ফল বদলাতে পারে, তাই সেখানে compiler এটি করে শুধু অনুমতি পেলে (যেমন -ffast-math).

Bounds-check elimination. Java বা Rust-এর মতো ভাষায় array-র প্রতিটি পড়ায় সীমা পরীক্ষা থাকে। Index-টি একটি induction variable হলে আর loop-এর শর্ত থেকে তার সীমা প্রমাণ করা গেলে, compiler পরীক্ষাটি মুছে দেয় বা loop-এর আগে একবারে করে। Haat v1-এ array নেই, তাই এখানে শুধু নাম; Haat-এর বর্ধিত রূপে array এলে এই প্রশ্ন উঠবে।

আরও গভীরে: LLVM-এ loop pass-গুলো একটি নির্দিষ্ট আকারের loop চায়: LoopSimplify প্রতিটি loop-এ একটি preheader আর একটি latch নিশ্চিত করে, আর LCSSA নিয়ম loop-এর বাইরে ব্যবহৃত প্রতিটি মানের জন্য exit block-এ একটি phi বসায়। Induction variable-এর হিসাব করে ScalarEvolution (SCEV), যা প্রতিটি মানকে “শুরু, প্রতি ঘোরায় বাড়া” ধরনের বীজগাণিতিক রূপে লেখে; পর্ব ৬৮-এর udiv-এর সূত্রও সেখান থেকে। Nested loop-এর ক্রম বদল আর tiling-এর গাণিতিক কাঠামো polyhedral model (Paul Feautrier-এর ১৯৯০-এর দশকের শুরুর কাজ থেকে), যা LLVM-এর Polly প্রকল্পে আছে। Loop-এর চলার সময়ের তথ্য (কোন শাখা বেশি নেওয়া হয়) দিয়ে JIT আরও সাহসী রূপান্তর করে, যা পর্ব ৬১-এর বিষয়।

৮ · সব একসঙ্গে — pipeline আর differential test

প্রতিটি pass আলাদাভাবে ঠিক, কিন্তু একসঙ্গে? পর্ব ৬৫-এর মতো উত্তর differential testing: একই program reference-এর haat.py run-এ আর optimize করা IR-এ চালিয়ে আউটপুট মেলানো, error-এর বার্তা আর line:col সহ। Pipeline: পর্ব ৬৫-এর optimize, তারপর licm, strength_reduce, unroll2, শেষে আবার optimize.

এলোমেলো program আসে পর্ব ৬২-এর haat_gen থেকে, আর এই পর্বের haat_loopgen থেকে, যা ইচ্ছা করে loop-ভরা program বানায়: nested loop, invariant হিসাব, i * k, শর্তের ভেতরে parameter দিয়ে ভাগ, loop-এর ভেতরে return আর print. তুলনার জন্য reference-আউটপুটের digest লেখকের lab-এ বানিয়ে loop_ref.txt-এ রাখা।

# ধাপ ৪: পুরো pipeline (৬৫ → LICM → SR → unroll → ৬৫), reference-এর আউটপুটের সঙ্গে মিলিয়ে; আর একটি জেনেশুনে ভুল
import hashlib
from haat_loop import *
from haat_opt import optimize
from haat_gen import gen_program
from haat_loopgen import gen_loopy
def digest(lines): return hashlib.sha256("\n".join(lines).encode()).hexdigest()[:10]
def build(src, f):
    mod = compile_ir(src)
    for fn in mod.funcs.values(): f(fn)
    return mod
FULL = lambda fn: (optimize(fn), licm(fn), strength_reduce(fn), unroll2(fn), optimize(fn))
BAD = lambda fn: licm(fn, unsafe=True)           # ভুল: শূন্য হতে পারা ভাজকের ভাগও সরায়
read = lambda p: open(p, encoding="utf-8").read()
cases = []                                       # (source, আউটপুট ঠিক কি না বলার function)
for n in ["examples/" + n for n in ("bazar", "mutual", "shadowing", "shortcircuit", "strings",
          "loops", "err_divzero", "counter", "nested")] + ["kisti", "tray", "boxes"]:
    cases.append((read(n + ".haat"), lambda got, w=read(n + ".out").split("\n")[:-1]: got == w))
for gen, ref in ((gen_program, read("random_ref.txt").split()), (gen_loopy, read("loop_ref.txt").split())):
    cases += [(gen(s), lambda got, d=ref[s]: digest(got) == d) for s in range(25)]   # seed 0–24
ok = skip = caught = 0; n = [0, 0, 0]
for src, good in cases:
    try: base = compile_ir(src)
    except Unsupported: skip += 1; continue      # closure: Haat IR v1-এর বাইরে
    full = build(src, FULL); ok += good(run_lines(full))
    caught += not good(run_lines(build(src, BAD)))
    try: c = [run_ir(m, out=lambda s: None) for m in (base, build(src, optimize), full)]
    except HaatError: continue                   # error-এ থামা program গোনায় বাদ
    n = [x + y for x, y in zip(n, c)]
print(f"program: {len(cases) - skip} (বাদ {skip}) · reference-এর সঙ্গে হুবহু: {ok}")
print(f"চলা নির্দেশ (error ছাড়া শেষ হওয়া): শুরু {n[0]:,} · পর্ব ৬৫ {n[1]:,} · ৬৫ + ৬৬ {n[2]:,}")
print(f"জেনেশুনে ভুল LICM: {caught}টি program-এ আউটপুট আলাদা — ধরা পড়ল")

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

program: 60 (বাদ 2) · reference-এর সঙ্গে হুবহু: 60
চলা নির্দেশ (error ছাড়া শেষ হওয়া): শুরু 11,441 · পর্ব ৬৫ 9,380 · ৬৫ + ৬৬ 8,346
জেনেশুনে ভুল LICM: 3টি program-এ আউটপুট আলাদা — ধরা পড়ল

counter আর nested closure ও nested function-এর জন্য Haat IR v1-এর বাইরে, তাই বাদ; বাকি ৬০টি হুবহু মেলে, error-এ থামা program-সহ। চলা নির্দেশ পর্ব ৬৫-তে ১৮% কমে, আর এই পর্বের pass তার ওপর আরও ১১%. জেনেশুনে ভুল LICM ধরা পড়ে তিনটিতে, যার একটি kisti.haat: এলোমেলো test এমন ভুল কমই ধরে (অংশ ৪)।

লেখকের lab-এ (CPython 3.14.4) পরীক্ষাটি বড় করে, reference সরাসরি চালিয়ে: ১১টি উদাহরণ (পর্ব ৬২-এর দশটির আটটি আর এই পর্বের তিনটি) আর দুই উৎসের ৩,০০০টি করে, মোট ৬,০১১টি program, ১৬,৫৩১টি function, ১৫,০২৮টি natural loop. আটটি আলাদা বিন্যাসে (প্রতিটি pass একা, তিনটি একসঙ্গে, পুরো pipeline, প্রতিটি pass দুবার করে) একটিও অমিল নেই। ৬,০০০টি এলোমেলো program-এ পুরো pipeline ৮০,৯১১টি নির্দেশ loop-এর বাইরে এনেছে, ৩,৭৬১টি গুণকে যোগে নামিয়েছে আর ১১,৩০৯টি loop unroll করেছে। সব program মিলিয়ে চলা নির্দেশ (error-এ থামা program-এ error পর্যন্ত):

মাপশুরুপর্ব ৬৫৬৫ + ৬৬
সব চলা নির্দেশ১৭,৩৮,৫১০১৪,৬৮,৮১৩১২,৭৮,৭৭৪
গুণ (*)৯৪,৫৯১৬৬,৯২০৩৬,০৭৩
jump১,২১,৮২০১,১৭,৯২২৮৭,৬২১
const৪,৯৫,৬২৪৩,৭৬,৮১১২,৫৪,৪৯৬

এগুলো গোনা নির্দেশ, সময় নয়। Test-এর নিজের পরীক্ষাও হয়েছে mutation testing দিয়ে: strength_reduce থেকে “k loop-invariant” পরীক্ষা মুছলে mix.haat ছাপে 6, reference ছাপে 46 (অনুশীলন ২)।

সহায়ক module haat_loop.py পুরোটা দেখুন (এই পর্বের সব নতুন কোড; আগের পর্বের ফাইলগুলো হুবহু)
# haat_loop.py — পর্ব ৬৬: Haat IR-এর loop optimization — natural loop, preheader, LICM, induction variable আর
# strength reduction, unrolling. লাগে পর্ব ৬২-এর haat_ir.py, ৬৩-এর haat_ssa.py (dominator) আর ৬৪-এর haat_dfa.py
# (liveness), সব হুবহু। SSA নয়, সাধারণ CFG-র ওপর কাজ; প্রতিটি pass fn বদলায়, ফেরত দেয় কয়টি বদল।
# স্থায়ী নিয়ম: যে / বা % শূন্য দিয়ে ভাগ করতে পারে, তা loop-এর বাইরে সরে না (সরলে নতুন runtime error আসতে পারে)।
from collections import Counter
from haat_dfa import *
from haat_ssa import dominators, dominates

@dataclass
class Loop:
    header: str                                  # loop-এর একমাত্র ঢোকার দরজা
    body: set                                    # header-সহ সব block
    latches: list                                # back edge-এর উৎস: এখান থেকে আবার header-এ
    exits: list                                  # (u, e): loop-এর u থেকে বাইরের e-তে যাওয়ার edge

def bnum(b): return int(b[1:])

def back_edges(fn, idom):                        # b → h, যেখানে h, b-কে dominate করে
    return [(b, h) for b in sorted(idom, key=bnum) for h in succs(fn, b) if h in idom and dominates(idom, h, b)]

def natural_loops(fn):                           # প্রতিটি header-এর একটি loop; ভেতরের (ছোট) loop আগে
    idom, P, loops = dominators(fn), preds(fn), {}
    for b, h in back_edges(fn, idom):
        L = loops.setdefault(h, Loop(h, {h}, [], []))
        L.latches.append(b); stack = [b] if b not in L.body else []
        L.body |= set(stack)
        while stack:                             # latch থেকে predecessor ধরে পেছনে; header-এ এসে থামে
            for p in P[stack.pop()]:
                if p not in L.body and p in idom: L.body.add(p); stack.append(p)
    for L in loops.values():
        L.exits = [(u, e) for u in sorted(L.body, key=bnum) for e in succs(fn, u) if e not in L.body]
    return sorted(loops.values(), key=lambda L: (len(L.body), bnum(L.header)))

def preheader(fn, L):                            # header-এর ঠিক আগে একটি block, যা loop-এ ঢোকার আগে একবার চলে
    h, P = L.header, preds(fn)
    out = [p for p in P[h] if p not in L.body]
    if len(out) == 1 and fn.blocks[out[0]][-1].kind == "jump": return out[0]     # আগে থেকেই আছে
    new = f"B{max(map(bnum, fn.blocks)) + 1}"
    if h == "B0":                                # entry নিজেই header: তার দেহ নতুন নামে, B0 হয় preheader
        for body in fn.blocks.values():
            for ins in body: ins.targets = [new if t == "B0" else t for t in ins.targets]
        fn.blocks[new], fn.blocks["B0"] = fn.blocks["B0"], [Ins("jump", targets=[new])]
        L.body = L.body - {"B0"} | {new}; L.latches = [new if b == "B0" else b for b in L.latches]
        L.exits = [(new if u == "B0" else u, e) for u, e in L.exits]; L.header = new
        return "B0"
    for p in out: fn.blocks[p][-1].targets = [new if t == h else t for t in fn.blocks[p][-1].targets]
    blocks = {}
    for b, body in fn.blocks.items():            # নতুন block-টি header-এর ঠিক আগে, পড়তে সুবিধা
        if b == h: blocks[new] = [Ins("jump", targets=[h])]
        blocks[b] = body
    fn.blocks = blocks
    return new

def preheaders(fn):                              # প্রতিটি loop-এর preheader নিশ্চিত করে, তারপর loop-গুলো নতুন করে
    done = set()
    while (L := next((L for L in natural_loops(fn) if L.header not in done), None)):
        preheader(fn, L); done.add(L.header)
    return natural_loops(fn)

def single_consts(fn):                           # যে নাম পুরো function-এ একবারই লেখা, আর তা `const k` দিয়ে
    n = Counter(d for body in fn.blocks.values() for i in body for d in defs(i))
    return {i.dst: i.sym for body in fn.blocks.values() for i in body if i.kind == "const" and n[i.dst] == 1}

def risk(ins, consts):                           # আগে বা বেশিবার চালালে কি নতুন error বা ভুল মান হতে পারে? কারণ, নইলে None
    if ins.kind == "bin" and ins.sym in ("/", "%"):
        k = consts.get(ins.args[1])              # শুধু নিশ্চিত অশূন্য ধ্রুবক ভাজক নিরাপদ
        return None if type(k) is int and k != 0 else "ভাজক শূন্য হতে পারে"
    if ins.kind == "copy" and ins.args[0][0] == "@": return "global: call বদলায়, পড়া error দিতে পারে"
    return None

def licm(fn, unsafe=False, log=None):            # loop-invariant code motion; unsafe=True: ভাগের নিয়ম ভাঙা (ভুল!)
    moved, done = 0, set()
    while (L := next((L for L in natural_loops(fn) if L.header not in done), None)):
        P = preheader(fn, L); done.add(L.header); changed = True
        while changed:                           # একটি সরলে তার ওপর নির্ভর করা নির্দেশও invariant হতে পারে
            changed, live = False, solve(LIVENESS, fn).IN
            inside = Counter(d for b in L.body for i in fn.blocks[b] for d in defs(i))
            consts = single_consts(fn)
            for b in [x for x in rpo(fn) if x in L.body]:
                for ins in list(fn.blocks[b]):
                    x = ins.dst
                    if ins.kind not in ("const", "copy", "bin", "un") or not x or x[0] == "@": continue
                    if inside[x] != 1 or any(inside[a] for a in ins.args): continue    # x একবার লেখা, operand অপরিবর্তিত
                    why = "loop-এর শুরুতে পুরোনো মান লাগে" if x in live[L.header] else risk(ins, consts)
                    if unsafe and why == "ভাজক শূন্য হতে পারে": why = None            # জেনেশুনে ভুল
                    if log is not None: log.append((b, str(ins), why or f"→ {P}"))
                    if why: continue
                    fn.blocks[b].remove(ins); fn.blocks[P].insert(-1, ins); inside[x] = 0
                    moved += 1; changed = True
    return moved

def fresh_temp(fn):                              # function-এ এখনো ব্যবহার না হওয়া পরের temp
    used = [int(x[1:]) for body in fn.blocks.values() for i in body for x in [i.dst, *i.args] if x and is_temp(x)]
    return f"t{max(used, default=0) + 1}"

def strength_reduce(fn, log=None):               # derived induction variable t = i * k -> যোগ দিয়ে চলা s
    n = 0
    for L in preheaders(fn):
        where = {}                               # loop-এর ভেতরে প্রতিটি নামের লেখা: [(b, ins)]
        for b in L.body:
            for i in fn.blocks[b]:
                for d in defs(i): where.setdefault(d, []).append((b, i))
        inv = lambda a: a[0] != "@" and a not in where                   # loop-এ লেখা হয় না
        basic = {i.dst: (b, i) for x, [(b, i)] in [(x, w) for x, w in where.items() if len(w) == 1]
                 if i.kind == "bin" and i.sym in "+-" and i.args[0] == i.dst and inv(i.args[1])}   # i = i ± d
        made = {}
        for b in sorted(L.body, key=bnum):
            for ins in list(fn.blocks[b]):
                if ins.kind != "bin" or ins.sym != "*" or len(where.get(ins.dst, ())) != 1: continue
                a, c = ins.args
                iv, m = (a, c) if a in basic and inv(c) else (c, a) if c in basic and inv(a) else (None, None)
                if iv is None or ins.dst == iv: continue
                if (iv, m) not in made:          # প্রথমবার: preheader-এ s = i * m আর step = d * m
                    P = preheader(fn, L); ub, upd = basic[iv]
                    s = fresh_temp(fn); fn.blocks[P].insert(-1, Ins("bin", s, [iv, m], "*"))
                    st = fresh_temp(fn); fn.blocks[P].insert(-1, Ins("bin", st, [upd.args[1], m], "*"))
                    body = fn.blocks[ub]; body.insert(body.index(upd) + 1, Ins("bin", s, [s, st], upd.sym))
                    made[iv, m] = s
                    if log is not None: log.append((P, f"{s} = {iv} * {m}", f"{st} = {upd.args[1]} * {m}", f"{s} = {s} {upd.sym} {st}"))
                fn.blocks[b][fn.blocks[b].index(ins)] = Ins("copy", ins.dst, [made[iv, m]]); n += 1
    return n

def unroll2(fn, limit=40):                       # ভেতরের প্রতিটি ছোট loop-এর দেহ দুবার; শর্ত দুই কপিতেই থাকে
    n = 0
    for L in natural_loops(fn):
        if any(M.header in L.body and M.header != L.header for M in natural_loops(fn)): continue   # ভেতরে আরেক loop
        if sum(len(fn.blocks[b]) for b in L.body) > limit: continue
        top = max(map(bnum, fn.blocks)); ren = {b: f"B{top + k + 1}" for k, b in enumerate(sorted(L.body, key=bnum))}
        for b in sorted(L.body, key=bnum):       # কপি: loop-এর ভেতরের লক্ষ্য কপিতে, শুধু back edge আসল header-এ
            fn.blocks[ren[b]] = [replace(i, args=list(i.args), targets=[L.header if t == L.header else ren.get(t, t)
                                 for t in i.targets]) for i in fn.blocks[b]]
        for b in L.latches:                      # আসল দেহের back edge এখন কপির header-এ
            fn.blocks[b][-1].targets = [ren[L.header] if t == L.header else t for t in fn.blocks[b][-1].targets]
        n += 1
    return n

def profile(mod):                                # চালিয়ে প্রতিটি ধরনের নির্দেশ কতবার চলল: {"*": …, "jump": …}
    seen = Counter()
    class Count(list):
        def __getitem__(self, i):
            ins = super().__getitem__(i)
            if isinstance(i, int): seen[ins.sym if ins.kind == "bin" else ins.kind] += 1
            return ins
    for f in mod.funcs.values(): f.blocks = {b: Count(body) for b, body in f.blocks.items()}
    try: run_ir(mod, out=lambda s: None)
    except HaatError: pass
    for f in mod.funcs.values(): f.blocks = {b: list(body) for b, body in f.blocks.items()}
    return seen

পরীক্ষা ও ইন্টারভিউতে: এই প্রশ্নগুলো প্রায়ই আসে, বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায়। Back edge কী? → edge n → h, যেখানে h, n-কে dominate করে। Natural loop কীভাবে বের করবেন? → back edge-এর latch থেকে predecessor ধরে পেছনে, header-এ থেমে। LICM-এর শর্ত? → operand loop-এ বদলায় না, নামটি loop-এ একবার লেখা, পুরোনো মান লাগে না, আর নির্দেশটি side effect বা নতুন error আনে না। Strength reduction-এর উদাহরণ? → i * 4-এর বদলে প্রতি ঘোরায় s = s + 4. Unrolling-এর দাম? → বড় কোড, instruction cache আর register-এ চাপ।

৯ · AI-এর যুগে loop optimization

AI assistant-কে “এই loop দ্রুত করো” বললে সে প্রায়ই সুন্দর, আত্মবিশ্বাসী উত্তর দেয়। কিন্তু loop-এর রূপান্তর ভুল হলে তা ধরা পড়ে শুধু বিশেষ মানে: শূন্যবার ঘোরা, শূন্য ভাজক, overflow-এর কাছের সংখ্যা।

AI-এর ভুলকীভাবে ধরবেন
শর্তের ভেতরের ভাগ বা call loop-এর বাইরে আনাশূন্য ভাজক আর শূন্যবার ঘোরা loop নিয়ে আগে-পরে চালানো
Loop-এ দুবার লেখা নাম, বা loop-এর পরে লাগা নাম সরানোLiveness দিয়ে শর্ত ৩ যাচাই; loop-এর পরে নামটি ছাপিয়ে দেখা
Overflow-এর কথা না ভেবে loop-কে সূত্রে বদলানো বা exit-শর্ত বদলানোসীমার কাছের মান (যেমন ২৬৩ − ১) দিয়ে test; ভাষার overflow-এর নিয়ম পড়া
Floating point-এর যোগের ক্রম বদলে vectorize করাফল bit ধরে মেলানো; compiler-এর অনুমতির flag কী, তা documentation-এ দেখা
বানানো compiler flag বা remark-এর নামনিজের compiler-এর version-এ চালিয়ে দেখা; -Rpass একটিই regex নেয়
“Compiler এটি নিশ্চয় করে” বলে assembly-র দাবি-S বা -emit-llvm দিয়ে আসল আউটপুট পড়া

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

আমি Python 3.14-এ একটি ছোট IR-এর (Haat IR, non-SSA CFG) জন্য loop-invariant code motion লিখছি। আমার কাছে dominator, natural loop আর liveness আছে। ১. একটি নির্দেশ preheader-এ সরানোর প্রতিটি শর্ত লেখো, আর প্রতিটি ভাঙলে আউটপুট বদলায় এমন একটি ৫–৬ লাইনের উদাহরণ দাও। ২. ভাগ আর ভাগশেষ শূন্য ভাজকে runtime error দেয়; শর্তের ভেতরের বা শূন্যবার ঘোরা loop-এর ভাগ কখনো সরাবে না। call, print আর global পড়াও নয়। ৩. কোডের পাশে একটি differential test দাও: একই program আগে-পরে চালিয়ে আউটপুট মেলাবে, error-এর বার্তাসহ। ৪. কোনো বাস্তব compiler-এর flag বা pass-এর নাম বললে version বলো; নিশ্চিত না হলে অনুমান করবে না।

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

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

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

প্র ০১Dominator আর natural loop-এর ধারণা কোথা থেকে এল, আর Frances Allen-এর কাজ কেন loop optimization-এর ভিত্তি?

Flow diagram-এ “এই বিন্দুতে আসতে হলে ওই বিন্দু পেরোতেই হবে” ধারণাটি সাধারণত Reese Prosser-এর ১৯৫৯ সালের একটি প্রবন্ধের সঙ্গে যুক্ত করা হয়, যেখানে Boolean matrix দিয়ে flow diagram বিশ্লেষণ করা হয়েছিল। Compiler-এ একে কাজে লাগানোর প্রথম বড় উদাহরণ হিসেবে প্রায়ই নাম আসে IBM-এর FORTRAN H compiler-এর, যার optimizer নিয়ে Edward Lowry আর C. W. Medlock ১৯৬৯ সালে Communications of the ACM-এ লেখেন; সেখানে dominator দিয়ে loop খুঁজে কোড loop-এর বাইরে আনা হতো। ইতিহাসের খুঁটিনাটি নিয়ে উৎসভেদে পার্থক্য আছে, তবে মূল ধারাটি এই।

IBM-এর Frances Allen এই ছড়ানো কৌশলগুলোকে একটি তত্ত্বে দাঁড় করান। ১৯৭০ সালের দিকে প্রকাশিত “Control Flow Analysis” প্রবন্ধে তিনি CFG-কে interval-এ ভাগ করে loop-এর কাঠামো বের করার পদ্ধতি দেন, আর John Cocke-এর সঙ্গে ১৯৭১–৭২ সালের দিকের “A Catalogue of Optimizing Transformations”-এ code motion, strength reduction, constant propagation-এর মতো রূপান্তরের একটি তালিকা, প্রতিটির শর্তসহ। এই পর্বের চারটি শর্তের পূর্বপুরুষ সেখানে। Allen ২০০৬ সালে Turing Award পান, প্রথম নারী হিসেবে, optimizing compiler-এর তত্ত্ব আর চর্চায় অবদানের জন্য।

কেন এই তত্ত্ব জরুরি ছিল? Source-এর DO বা while দেখে loop চেনা সহজ, কিন্তু GOTO-ভরা পুরোনো FORTRAN কোডে loop লুকিয়ে থাকত শাখার জালে। Dominator-ভিত্তিক সংজ্ঞা source-এর গড়ন ভুলে শুধু graph দেখে, তাই যে ভাষা বা যে কোড থেকেই CFG আসুক, একই অ্যালগরিদম চলে। আজকের LLVM-এর LoopInfo-ও ঠিক এই সংজ্ঞায় loop চেনে।

মূল উপলব্ধি: loop-কে source-এর শব্দ না ধরে graph-এর গুণ (header সব block-কে dominate করে) ধরলে, একবার লেখা optimizer সব ভাষার সব loop-এ খাটে।

প্র ০২প্রথম FORTRAN compiler (১৯৫৭) loop-এর হিসাব নিয়ে এত মাথা ঘামিয়েছিল কেন?

১৯৫০-এর দশকে প্রোগ্রামাররা assembly-তে লিখতেন, আর “যন্ত্রের লেখা কোড মানুষের লেখার মতো দ্রুত হবে না” ছিল প্রচলিত বিশ্বাস। John Backus-এর IBM দল FORTRAN-এর সঙ্গে সঙ্গে প্রমাণ করতে চেয়েছিল যে একটি compiler প্রায় হাতে লেখা কোডের মতো কোড বানাতে পারে; না হলে কেউ ভাষাটি নিত না, এমনটাই Backus পরে তাঁর ইতিহাস-প্রবন্ধে (১৯৭৮-৮১ সালের দিকে) লেখেন।

বিজ্ঞানের হিসাবে সময় কাটে array-ওয়ালা DO loop-এ, যেমন A(I, J)-এর ঠিকানা: শুরু + (I − 1) + (J − 1) × সারির দৈর্ঘ্য। প্রতিটি পড়ায় এই গুণ করলে কোড ধীর হতো, যখন সেই যুগের যন্ত্রে গুণ ছিল বেশ ব্যয়বহুল। ইতিহাসের বর্ণনা অনুযায়ী FORTRAN I-এর compiler loop-এর ভেতরে subscript-এর হিসাব index register-এ রেখে প্রতি ঘোরায় শুধু একটি যোগ দিয়ে এগোত, যা এই পর্বের strength reduction-এরই পূর্বরূপ; আর কোন register কোথায় রাখা হবে, তা ঠিক করতে loop-এর কোন অংশ কতবার চলবে তার একটি আনুমানিক হিসাবও করত। খুঁটিনাটি নিয়ে উৎসভেদে পার্থক্য আছে, তাই এগুলো সাবধানে পড়ুন।

ফলটি ঐতিহাসিক: FORTRAN-এর কোড অনেক ক্ষেত্রে হাতে লেখা কোডের কাছাকাছি গতিতে চলায় উচ্চস্তরের ভাষা মেনে নেওয়া সহজ হয়, আর “optimizing compiler” একটি আলাদা ক্ষেত্র হয়ে ওঠে। আজকের tray[i * 4]-এর assembly-তে (অংশ ৫) pointer-এর ১২৮ বাইট লাফ সেই একই চিন্তার বংশধর।

মূল উপলব্ধি: একটি ভাষার গ্রহণযোগ্যতা অনেক সময় তার compiler-এর মানের ওপর দাঁড়ায়, আর সেই মানের বড় অংশ loop-এর ভেতরে।

প্র ০৩C-তে signed overflow undefined behavior হওয়ায় loop optimization সহজ হয় কেন, আর Haat-এর wrap কী হারায়, কী পায়?

৬৪-bit যন্ত্রে একটি C loop ভাবুন: for (int i = 0; i < n; i++) s += a[i];. int ৩২-bit, কিন্তু ঠিকানা ৬৪-bit; তাই প্রতি ঘোরায় i-কে ৬৪-bit-এ বাড়িয়ে নিতে হয়। C-তে signed overflow undefined behavior, তাই compiler ধরে নিতে পারে i কখনো wrap করবে না: তখন i-কে শুরু থেকেই একটি ৬৪-bit induction variable বানানো যায়, প্রতি ঘোরায় রূপান্তর ছাড়া। একই যুক্তিতে i <= n-এর loop থামবে বলে ধরে নেওয়া যায়, আর ঘোরার সংখ্যা একটি সূত্রে লেখা যায়। LLVM-এ এই প্রতিশ্রুতি nsw পতাকা।

Haat সিদ্ধান্ত ১৩-এ উল্টো পথ নিয়েছে: সব Int wrap করে, কোনো undefined behavior নেই। লাভ: একই program সব যন্ত্রে, সব optimization-স্তরে একই ফল দেয়; একটি overflow নিরাপত্তার ফাঁক হয়ে দাঁড়ায় না। দাম: কিছু রূপান্তর আর বিনা প্রমাণে চলে না। পর্ব ৬৮-এ দেখা গেছে Clang C-এর rounds loop-কে একটি udiv-এর সূত্রে নামিয়েছে, অথচ Haat-এর একই loop রয়ে গেছে, কারণ wrap-এর জগতে সূত্রটি ভুল হতে পারে।

তবে এই পর্বের strength reduction-এ wrap কোনো বাধা নয়: mod 264-এর হিসাবে বণ্টন-নিয়ম খাটে, তাই (i + d) · k ≡ i · k + d · k. অন্য ভাষাও নানা পথ নিয়েছে: Java-র int সবসময় wrap করে; Rust debug build-এ overflow-তে panic করে আর release build-এ ডিফল্টভাবে wrap করে, কোনোটিই UB নয়; C-তে GCC আর Clang-এর -fwrapv signed overflow-কে wrap বানায়, তখন nsw আসে না। কোন পথ ভালো, তা নির্ভর করে ভাষা নিরাপত্তা আর অনুমেয়তাকে কতটা দাম দেয় তার ওপর।

মূল উপলব্ধি: undefined behavior optimizer-কে প্রমাণ ছাড়া অনুমানের অধিকার দেয়; নির্দিষ্ট wrap সেই অধিকার কেড়ে নেয়, বিনিময়ে প্রতিটি program-এর অর্থ সবসময় এক থাকে।

প্র ০৪Duff’s device থেকে আজকের compiler: হাতে unroll করা কি এখনো বুদ্ধিমানের কাজ?

১৯৮৩ সালে Lucasfilm-এ Tom Duff একটি copy loop দ্রুত করতে C-র একটি অদ্ভুত কৌশল লেখেন: একটি switch-এর case-গুলো একটি do … while-এর ভেতরে ছড়িয়ে, যাতে বাকি থাকা ঘোরাগুলো (epilogue) আর মূল unroll করা দেহ একই কোডে চলে। এটি বৈধ C, আর “Duff’s device” নামে বিখ্যাত হয়। সেই যুগের compiler নিজে unroll করত না বললেই চলে, তাই প্রোগ্রামাররা হাতে করতেন।

আজ ছবিটি বদলেছে। এই পর্বের সত্যিকারের run-এ Clang 22 -O2-তেই তিনটি loop নিজে থেকে unroll করেছে, ঘোরার সংখ্যা না জেনেও, epilogue-সহ। GCC-র documentation অনুযায়ী তার -funroll-loops কোনো -O স্তরে আপনাআপনি চালু হয় না (profile feedback দিলে হয়), যদিও ঘোরার সংখ্যা জানা ছোট loop পুরো খুলে ফেলার (complete peeling) মতো সীমিত কাজ অন্য স্তরেও হতে পারে; কোন compiler কোন স্তরে কী করে, তা version-ভেদে বদলায়, তাই নিজের compiler-এ remark দিয়ে দেখাই নিরাপদ। দুটিতেই #pragma দিয়ে নির্দিষ্ট loop-এ নির্দেশ দেওয়া যায়।

হাতে unroll-এর ঝুঁকি আছে। কোড বড় হয়, instruction cache-এ চাপ বাড়ে; অস্বাভাবিক গড়নের কোড compiler-এর vectorizer চিনতে না-ও পারে, ফলে হাতের unroll আসলে ধীর কোড দিতে পারে; আর epilogue-এ ভুল (বিজোড় সংখ্যার শেষ ঘোরা বাদ) খুব সাধারণ bug. ভালো চর্চা হলো আগে মাপা: profiler দিয়ে গরম loop খোঁজা, compiler-এর remark পড়া, তারপর দরকার হলে pragma বা হাতের কৌশল, আর প্রতিটি বদলের পরে differential test.

মূল উপলব্ধি: যে কৌশল একসময় মানুষের হাতের কাজ ছিল, তা এখন compiler-এর নিয়মিত কাজ; মানুষের কাজ এখন মাপা, remark পড়া আর যাচাই করা।

প্র ০৫CPU তো সারাক্ষণ নির্দেশ আগেভাগে চালায়; তাহলে compiler একটি ভাগ আগেভাগে চালাতে পারে না কেন?

আধুনিক CPU শাখার ফল জানার আগেই অনুমানে পরের নির্দেশ চালায় (কম্পিউটার আর্কিটেকচারের পর্ব ৪০)। ভুল পথের কোনো নির্দেশে শূন্য দিয়ে ভাগ হলেও program থামে না: CPU সেই নির্দেশের ফল আর exception দুটিই ধরে রাখে, আর নির্দেশটি সত্যিই “অবসর” (retire) নেওয়ার মুহূর্তে, অর্থাৎ পথটি ঠিক প্রমাণ হলে, তবেই exception জানায়। ভুল পথের সব কাজ ফেলে দেওয়া হয়, তাই architecture-এর স্তরে কিছুই দেখা যায় না।

Compiler-এর speculation আলাদা: সে কোডটিই বদলে দেয়। Preheader-এ সরানো ভাগ এখন program-এর অংশ, তার error সত্যিকারের error, ফেরানোর কোনো যন্ত্র নেই। তাই compiler-কে আগে প্রমাণ করতে হয় যে বাড়তি পথে চালালেও কিছু বদলায় না (শর্ত ৪)। কিছু JIT compiler (পর্ব ৬১) মাঝামাঝি পথ নেয়: অনুমানে কোড বানিয়ে পাহারা বসায়, আর অনুমান ভাঙলে deoptimize করে সাধারণ কোডে ফেরে।

CPU-র লুকানোও নিখুঁত নয়। ২০১৮ সালে প্রকাশিত Spectre আর Meltdown দেখায় যে ভুল পথের নির্দেশ ফেলে দেওয়া হলেও cache-এ তাদের ছাপ থেকে যায়, আর সময় মেপে সেই ছাপ পড়া যায়। প্রতিরোধে compiler আর OS-এ নতুন কৌশল আসে, যেমন সংবেদনশীল কোডে speculation আটকানোর নির্দেশ বসানো। অর্থাৎ “অনুমানে চালানো” প্রশ্নটি দুই স্তরেই নিরাপত্তার প্রশ্ন: compiler-এ অর্থের, hardware-এ গোপনীয়তার।

মূল উপলব্ধি: hardware ভুল অনুমান মুছে ফেলতে পারে বলে সাহসী, compiler পারে না বলে সাবধানী; তাই compiler-এর প্রতিটি speculation-এর আগে একটি নিরাপত্তার প্রমাণ লাগে।

অনুশীলন

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

  1. নকশা ও বাস্তবায়ন — loop unswitching: haat_loop.py-র ওপর একটি unswitch(fn) লিখুন: loop-এর ভেতরে এমন একটি branch খুঁজুন, যার শর্ত loop-এ লেখা হয় না; loop-এর সব block কপি করুন; আসল কপিতে শাখাটি সবসময় সত্য, নতুন কপিতে সবসময় মিথ্যা; আর preheader-এর শেষে শর্ত দেখে দুই loop-এর একটিতে যান। kisti.haat-এর bill-এ (LICM-এর পরে) ফল কী, আর চলা নির্দেশ কত?
    from haat_loop import *
    
    def unswitch(fn, limit=40):                      # loop-এর ভেতরে invariant শর্তের branch -> loop-টিকেই দুই কপি
        for L in preheaders(fn):
            inside = {d for b in L.body for i in fn.blocks[b] for d in defs(i)}
            size = sum(len(fn.blocks[b]) for b in L.body)
            br = next((b for b in sorted(L.body, key=bnum) if b != L.header and fn.blocks[b][-1].kind == "branch"
                       and fn.blocks[b][-1].args[0] not in inside), None)
            if br is None or size > limit: continue
            P = preheader(fn, L); c, (yes, no) = fn.blocks[br][-1].args[0], fn.blocks[br][-1].targets
            top = max(map(bnum, fn.blocks)); ren = {b: f"B{top + k + 1}" for k, b in enumerate(sorted(L.body, key=bnum))}
            for b in sorted(L.body, key=bnum):       # কপির ভেতরের সব লক্ষ্য (back edge-সহ) কপিতেই
                fn.blocks[ren[b]] = [replace(i, args=list(i.args), targets=[ren.get(t, t) for t in i.targets]) for i in fn.blocks[b]]
            fn.blocks[br][-1] = Ins("jump", targets=[yes])                       # আসল: শর্ত সবসময় সত্য
            fn.blocks[ren[br]][-1] = Ins("jump", targets=[ren.get(no, no)])      # কপি: সবসময় মিথ্যা
            fn.blocks[P][-1] = Ins("branch", args=[c], targets=[L.header, ren[L.header]])
            return 1
        return 0

    unroll2-এর সঙ্গে পার্থক্য একটিই: কপির back edge কপির নিজের header-এ যায়, কারণ এখানে দুটি আলাদা loop. লেখকের lab-এ সত্যিকারের run: bill-এ শাখাটি আসলে jump B3, কপিতে jump B9, আর B0-এর শেষে branch t5 B1 B6. শুধু কপিতে নির্দেশ কমে না (১০১), কিন্তু পর্ব ৬৫-এর optimize-এর পরে ১০১ থেকে ৯২, আউটপুট 630, 180, 0. people > 0-এর কপিতে base / people এখন শর্ত ছাড়াই চলে, তবু LICM সেটি সরায় না: “এই কপিতে people অশূন্য” তথ্যটি শুধু পথ থেকে জানা যায়। ৬,০০০টি এলোমেলো program-এ (LICM-এর পরে) ২,১১৭টি function-এ একটি করে loop unswitch হয়েছে; আউটপুট একটিতেও আলাদা নয়।

  2. ভুল খুঁজুন — strength reduction-এ একটি বাদ পড়া পরীক্ষা: একজন সহকর্মী strength_reduce “সরল” করলেন: t = i * k-এ i basic induction variable হলেই চলবে, k loop-invariant কি না দেখার দরকার নেই। নিচের program-এ কী হবে, আর কেন?
    fn mix(n: Int) -> Int {
        var i = 0;
        var j = 1;
        var s = 0;
        while i < n {
            j = j + 2;
            s = s + i * j;
            i = i + 1;
        }
        return s;
    }
    print(mix(4));

    Reference ছাপে 46: j হয় 3, 5, 7, 9, আর s = 0·3 + 1·5 + 2·7 + 3·9 = 46. ভুল সংস্করণ preheader-এ t5 = i * j আর t6 = t4 * j বসায়, যেখানে j = 1; তারপর প্রতি ঘোরায় t5 বাড়ে 1 করে, অথচ j বদলাচ্ছে। লেখকের lab-এ সত্যিকারের run: ছাপা হয় 6. প্রমাণের কোন ধাপ ভেঙেছে? ধাপ ৩: s' = s + d · k ধরে নেয় k এক থাকে; j বদলালে (i + d) · j' ≠ i · j + d · j. সঠিক কোডে inv(c) পরীক্ষা ঠিক এটি আটকায়। ৬,০০০টি এলোমেলো program-এ ভুল সংস্করণ ২,৫৪১টিতে অন্তত একটি গুণ বদলায়, আর ভুল ধরা পড়ে ৩০৪টিতে: ৬৫টিতে আউটপুট আলাদা, আর ২৩৯টিতে IR interpreter চলতেই পারে না, কারণ preheader-এ এমন একটি k পড়া হয়, যা loop-এর ভেতরে প্রথম লেখা হয়, তখনো যার কোনো মানই নেই।

  3. হিসাব — পরীক্ষার ধাঁচে পুরো loop optimization: নিচের function-এর Haat IR দেওয়া। (ক) back edge আর প্রতিটি natural loop-এর body; (খ) licm কোন নির্দেশ কোন preheader-এ সরায় (ভেতরের loop আগে); (গ) basic আর derived induction variable, আর strength reduction-এর পরে ভেতরের loop; (ঘ) print(stock(2, 10)) কী ছাপে?
    fn stock(days: Int, rate: Int) -> Int {
        var d = 0;
        var total = 0;
        while d < days {
            let daily = rate * 12;
            var h = 0;
            while h < 3 {
                total = total + daily + h * 5;
                h = h + 1;
            }
            d = d + 1;
        }
        return total;
    }
    B0: d = const 0; total = const 0; jump B1
    B1: t1 = d < days; branch t1 B2 B6
    B2: t2 = const 12; daily = rate * t2; h = const 0; jump B3
    B3: t3 = const 3; t4 = h < t3; branch t4 B4 B5
    B4: t5 = total + daily; t6 = const 5; t7 = h * t6;
        total = t5 + t7; t8 = const 1; h = h + t8; jump B3
    B5: t9 = const 1; d = d + t9; jump B1
    B6: return total

    (ক) idom: B1→B0, B2→B1, B3→B2, B4→B3, B5→B3, B6→B1. Back edge B4 → B3 (ভেতরের loop {B3, B4}, preheader B2) আর B5 → B1 (বাইরের loop {B1, B2, B3, B4, B5}, preheader B0).

    (খ) ভেতরের loop আগে: t3 = const 3, t6 = const 5, t8 = const 1 যায় B2-তে। তারপর বাইরের loop: B2 এখন বাইরের loop-এর ভেতরে, তাই t2 = const 12, daily = rate * t2, আর সদ্য আসা t3, t6, t8 আবার এক ধাপ বেরিয়ে B0-তে; সঙ্গে B5-এর t9 = const 1. মোট ৯টি সরানো (তিনটি দুবার), h = const 0 থাকে, কারণ ভেতরের loop h বদলায়, তাই বাইরের loop-এ h দুবার লেখা।

    (গ) ভেতরের loop-এ h basic (h = h + t8, d = 1), আর t7 = h * t6 derived (k = 5). Strength reduction ভেতরের preheader B2-তে বসায় t10 = h * t6 আর t11 = t8 * t6, h-এর পরে t10 = t10 + t11, আর t7 = t10. পর্ব ৬৫-এর পরে B2-তে t10 = const 0, t11 = const 5, আর ভেতরের loop-এ total = t5 + t10, t10 = t10 + t11. বাইরের loop-এ d basic, কিন্তু d দিয়ে কোনো গুণ নেই।

    (ঘ) daily = 120; প্রতিদিন 120 + 125 + 130 = 375; দুই দিনে 750, reference আর প্রতিটি ধাপের পরের IR-এ একই, সত্যিকারের run. চলা নির্দেশ ৯৬ → ৭৬ (LICM) → ৮৬ (strength reduction) → ৭৮ (পর্ব ৬৫), আর গুণ ৮ → ৭ → ৫ → ১: শেষ গুণটি daily = rate * t2, এখন পুরো function-এ একবার।

  4. প্রমাণ — “exit-কে dominate করা” শর্তটি আপনাআপনি আসে: Dragon book-এর একটি শর্ত বলে, s: x = e-কে সরাতে হলে s-এর block b-কে loop-এর সেই প্রতিটি exiting block u dominate করবে, যার exit-লক্ষ্য e-তে x live. দেখান যে শর্ত ৬৬.৪-এর ২ (x loop-এ শুধু s-এ লেখা) আর ৩ (header h-এর শুরুতে x live নয়) সত্য হলে এটি সবসময় সত্য।

    বিপরীত ধরে নিই: একটি exit (u, e) আছে, যেখানে x, e-তে live, অথচ b, u-কে dominate করে না।

    1. b, u-কে dominate করে না, তাই entry থেকে u-তে একটি পথ P আছে, যা b ছোঁয় না।
    2. h loop-এর সব block-কে dominate করে, তাই P-তে h আছে। P-এর শেষবার h থেকে u পর্যন্ত অংশ P' নিই; P' আর h-এ ফেরে না, আর b ছোঁয় না।
    3. P' loop-এর বাইরে যেতে পারে না: বাইরে থেকে loop-এ ফেরার একমাত্র দরজা h, আর P' আর h-এ ফেরে না অথচ শেষ হয় u-তে, যা loop-এর ভেতরে।
    4. অতএব P'-এর প্রতিটি block loop-এর ভেতরে, আর তাদের কেউ x লেখে না: loop-এ x-এর একমাত্র লেখা s, যা b-তে (শর্ত ২)।
    5. x, e-তে live: e থেকে একটি পথ আছে, যেখানে x নতুন করে লেখার আগেই পড়া হয়। P', তারপর edge (u, e), তারপর সেই পথ: h থেকে একটি পথ, যেখানে x লেখার আগে পড়া হয়। অর্থাৎ h-এর শুরুতে x live, যা শর্ত ৩-এর বিরোধী। ∎

    প্রমাণটি এটাও দেখায় কেন শর্ত ৩ “loop-এর ভেতরের পড়া” নয়, “header-এ live” হিসেবে লেখা হলো: loop-এর পরের পড়াও এতে ধরা পড়ে, শূন্যবার ঘোরার ক্ষেত্রসহ। লেখকের lab-এ পরীক্ষা: শর্তটির একটি মোটা দাগের রূপ কোডে রেখে আর বাদ দিয়ে ৬,০০০টি program, আউটপুট একটিতেও আলাদা নয় (অংশ ৩)।

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

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

ক্রমএকটি function-এ loop-invariant code motion-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. প্রতিটি block-এর dominator হিসাব করা
  2. Back edge খুঁজে প্রতিটি natural loop-এর body বের করা
  3. সবচেয়ে ভেতরের loop বেছে তার preheader নিশ্চিত করা
  4. Liveness হিসাব করা, যাতে header-এ কোন নাম live জানা যায়
  5. শর্ত মেনে invariant নির্দেশগুলো preheader-এ সরানো
  6. কিছু না বদলানো পর্যন্ত আবার, তারপর বাইরের loop-এ যাওয়া

একটি CFG-র edge: B0→B1, B1→B2, B2→B3, B3→B1, B1→B4. কোনটি back edge?

  • B1→B2
  • B3→B1
  • B1→B4
  • B0→B1

একটি CFG-র edge: B0→B1, B1→B2, B1→B5, B2→B3, B2→B4, B3→B4, B4→B1. Back edge B4→B1-এর natural loop-এর body কী?

  • {B1, B4}
  • {B1, B2, B3, B4}
  • {B1, B2, B3, B4, B5}
  • {B2, B3, B4}

Haat-এ while i < n { if d != 0 { let x = a / d; s = s + x; } let y = a * b; s = s + y; i = i + 1; }; loop-এ a, b, d, n লেখা হয় না, আর x, y loop-এর পরে পড়া হয় না। LICM কোনটি loop-এর বাইরে আনতে পারে?

  • x = a / d আর y = a * b দুটিই
  • শুধু x = a / d
  • শুধু y = a * b
  • কোনোটিই নয়

একটি loop-এ i-এর একমাত্র লেখা i = i + 2, আর t = i * 3. Strength reduction-এর পরে s = i * 3 রাখতে প্রতি ঘোরায় s-এ কত যোগ হবে?

  • 2
  • 3
  • 5
  • 6

Haat-এর Int ৬৪-bit-এ wrap করে। তবু i * k-কে প্রতি ঘোরায় s = s + d * k দিয়ে বদলানো হুবহু ঠিক কেন?

  • Mod 264-এর হিসাবে বণ্টন-নিয়ম খাটে, তাই দুই হিসাবের ফল সবসময় এক
  • কারণ Haat-এ loop-এর ভেতরে overflow কখনো ঘটে না
  • কারণ overflow undefined behavior, তাই compiler যা খুশি করতে পারে
  • কারণ Haat-এর Int আসলে সীমাহীন

Clang-এ -Rpass=licm -Rpass=loop-unroll দিয়ে compile করলে শুধু unroll-এর remark দেখা গেল, LICM-এর একটিও নয়। সবচেয়ে সম্ভাব্য কারণ?

  • -O2-তে LICM চলে না
  • একটি ফাইলে একটির বেশি pass-এর remark আসে না
  • -Rpass একটিই regex নেয়; শেষ পতাকাটি আগেরটিকে বদলে দিয়েছে
  • LICM কোনো remark দেয় না

শব্দকোষ

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

মনে রাখুন

  1. Loop চেনা: n → h back edge, যদি h, n-কে dominate করে; natural loop = h আর h না ছুঁয়ে n-এ পৌঁছানো সব block. ভেতরের loop আগে।
  2. Preheader: loop-এ ঢোকার আগে ঠিক একবার চলা block; সরানো কোড এখানে বসে।
  3. LICM-এর চার শর্ত: side effect নেই, নামটি loop-এ একবার লেখা, header-এ live নয়, আর নতুন error নয়; শূন্য হতে পারা ভাজকের ভাগ কখনো নয়।
  4. Strength reduction: t = i · k-এর বদলে preheader-এ s = i · k, আর i-এর পরে s += d · k; mod 264-এর ring-এ হুবহু ঠিক।
  5. চালিয়ে যাচাই: প্রতিটি pass-এর পরে আউটপুট মেলানো, আর জেনেশুনে ভুল বসিয়ে দেখা যে test সেটি ধরে; সীমার মান হাতে বাছা।

পরের পর্বে: পর্ব ৬৭ (Inlining আর interprocedural optimization). Function-এর সীমা পেরিয়ে: call graph, inlining আর interprocedural constant propagation; inline করার পরে এই পর্বের loop pass-গুলো আরও বড় loop আর আরও বেশি invariant দেখতে পায়।

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

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