এই পর্বে যা শিখবেন
- LLVM IR-এর গঠন: module, global, function, basic block, type আর মূল নির্দেশগুলো পড়তে পারা
- SSA রূপের Haat IR থেকে LLVM IR লেখার একটি সম্পূর্ণ অনুবাদক, আর তার নকশার সিদ্ধান্ত
nsw/nuw, poison আরsdiv-এর undefined behavior: কেন Haat-এর অনুবাদে এগুলো সাবধানে লাগে- Clang-এর পথ:
alloca,load,storeথেকে SROA আর mem2reg দিয়ে SSA - সত্যিকারের Clang দিয়ে
.llcompile,-print-after,-Rpassআর verifier-এর error পড়া
১ · LLVM IR কী — বাস্তব, type-ওয়ালা একটি SSA IR
বাজারঘর সারা দেশের ছোট দোকান থেকে মাল কেনে। প্রত্যেক দোকান যদি নিজের মাপের বস্তায় মাল পাঠায়, তবে প্রতিটি কুরিয়ারকে প্রতিটি বস্তার নিয়ম শিখতে হয়। বাজারঘর তাই একটি নিয়ম করেছে: সবাই একই মাপের, একই লেবেলের কার্টনে মাল দেবে। এখন নতুন দোকান যোগ হলে শুধু কার্টনে ভরা শিখলেই চলে, আর নতুন কুরিয়ার শুধু কার্টন বইতে জানলেই চলে। LLVM-এর IR ঠিক সেই কার্টন।
পর্ব ০৫-এ দেখেছেন m-টি ভাষা আর n-টি যন্ত্রের জন্য m × n compiler না লিখে m + n টুকরো লেখা যায়, যদি মাঝখানে একটি সাধারণ intermediate representation থাকে। পর্ব ৬২ Haat-এর নিজের IR বানিয়েছে, পর্ব ৬৩ তাকে SSA রূপে এনেছে। এবার বাস্তব জগতের সবচেয়ে পরিচিত সাধারণ IR: LLVM IR. C আর C++-এর Clang, Rust-এর rustc, Swift আর আরও অনেক compiler এতেই নামে, আর LLVM-এর back end সেখান থেকে x86-64, AArch64, RISC-V বা WebAssembly-র machine code বানায়।
একটি module (সাধারণত একটি source ফাইলের অনুবাদ) ধরে রাখে global variable (@নাম), বাইরের function-এর ঘোষণা (declare) আর function-এর সংজ্ঞা (define). প্রতিটি function কয়েকটি basic block; প্রথমটি entry, যেখানে কেউ লাফাতে পারে না। প্রতিটি block শেষ হয় ঠিক একটি terminator দিয়ে (br, ret, unreachable). প্রতিটি মানের একটি type: i64 (৬৪-বিট পূর্ণসংখ্যা), i1 (Bool), ptr (ঠিকানা), [N x i8] (byte-এর সারি), {} (খালি struct). Local নাম % দিয়ে শুরু, আর প্রতিটির সংজ্ঞা লেখায় একবার: LLVM IR SSA form-এ।
একই IR-এর তিনটি রূপ আছে, অর্থ একই: পড়ার মতো text (.ll ফাইল, এই পর্বে আমরা এটিই লিখব), ছোট binary bitcode (.bc), আর compiler-এর memory-র ভেতরের C++ object. LLVM-এর শুরু Chris Lattner আর Vikram Adve-র হাতে, University of Illinois-এ, মোটামুটি ২০০০ সালে; ২০০৪ সালের CGO সম্মেলনের একটি প্রবন্ধে কাঠামোটি বিস্তারিত বর্ণিত হয়, আর পরে Apple-এ Clang-এর কাজ শুরু হয় (তারিখগুলো উৎসভেদে একটু আলাদা বলা হয়)।
ছবি ৬৮.১ — Haat থেকে চলমান program, LLVM দিয়ে
বাঁ দিকে Haat-এর পথ; ডান দিকে একই LLVM IR-এ আসা অন্য front end আর বেরোনো অন্য back end
২ · LLVM IR পড়া — price, লাইন ধরে
পড়তে শেখার সবচেয়ে ভালো উপায় একটি চেনা function. নিচে bazar.haat-এর price, এই পর্বের অনুবাদকের সত্যিকারের আউটপুট থেকে (অংশ ৩-এর ব্লক)। Haat IR-এর সঙ্গে মিলিয়ে পড়ুন: block-এর নাম সেই একই B0, B1, B2.
define i64 @price(i64 %qty, i64 %unit) {
B0:
%p = mul i64 %qty, %unit
%t2 = icmp sge i64 %p, 1000
br i1 %t2, label %B1, label %B2
B1:
%t4 = call i64 @haat.div(i64 %p, i64 10, i64 4, i64 33)
%t5 = sub i64 %p, %t4
ret i64 %t5
B2:
ret i64 %p
}
তিনটি নিয়ম চোখে পড়ে। এক, প্রতিটি operand-এর আগে তার type: mul i64 %qty, %unit. দুই, ধ্রুবক সরাসরি বসে (1000, 10); Haat IR-এ এর জন্য আলাদা t = const k লাগত। তিন, তুলনার ফল i1, আর br-এর দুটি লক্ষ্য, ঠিক Haat IR-এর branch-এর মতো। নিচের stepper price(2, 520) চালিয়ে প্রতিটি লাইনের অর্থ আর মান দেখায়।
1define i64 @price(…)2%p = mul i64 %qty, %unit3%t2 = icmp sge i64 %p, 10004br i1 %t2, label %B1, …5%t4 = call @haat.div(…)6%t5 = sub i64 %p, %t47ret i64 %t58B2: ret i64 %p
| %qty, %unit | |
| %p | |
| %t2 | |
| %t4, %t5 |
define. ফেরত typei64, global নাম@price, আর দুটি parameter, প্রতিটির type লেখা:(i64 %qty, i64 %unit). Haat-এ দুটিইInt, আর Haat-এর Int ৬৪-বিট, তাইi64. প্রথম block B0 হলো entry.mul.%p = mul i64 %qty, %unit: ২ × ৫২০ = ১০৪০.%p-এর সংজ্ঞা এই একটিই নির্দেশ। কোনোnswপতাকা নেই, কারণ Haat-এ overflow হলে wrap (অংশ ৪)।icmp sge. “signed greater or equal”: ১০৪০ ≥ ১০০০, তাই%t2= true, typei1. LLVM-এর পূর্ণসংখ্যায় নিজে কোনো চিহ্ন নেই; signed আর unsigned-এর পার্থক্য থাকে নির্দেশে (sgeবনামuge).br.br i1 %t2, label %B1, label %B2: সত্য হলে B1, মিথ্যা হলে B2. এটি B0-এর terminator; এর পরে B0-তে আর কিছু থাকতে পারে না।call @haat.div. ভাগ সরাসরিsdivনয়, একটি ছোট সহায়ক function-এ যায়, শেষের দুটি argument ভাগ চিহ্নের অবস্থান4:33. সেখানে শূন্য আর −১-এর পরীক্ষা হয় (অংশ ৫); এখানে ১০৪০ / ১০ = ১০৪.sub. ১০৪০ − ১০৪ = ৯৩৬. আবার সাধারণsub,nswছাড়া।ret. B1-এর terminator: ৯৩৬ ফেরত। bazar.haat-এprice(2, 520) + delivery(…)= ৯৩৬ + ৬০ = ৯৯৬, প্রথম ছাপা লাইন।- অন্য পথ.
price(1, 520)-এ%p= ৫২০,%t2= false, তাই B2:ret i64 %p. B1-এর%t4,%t5তখন কখনো তৈরিই হয় না। প্রতিটি নামের সংজ্ঞা একবার, আর প্রতিটি ব্যবহারকে তার সংজ্ঞা dominate করে; Clang-এর verifier compile-এর শুরুতেই এই দুটি শর্ত যাচাই করে।
এই পর্বে যে নির্দেশগুলো আসবে, তাদের এক জায়গায় দেখুন। বাঁয়ের কলাম LLVM IR, ডানে Haat IR-এর সবচেয়ে কাছের রূপ।
| LLVM IR | অর্থ | Haat IR-এ |
|---|---|---|
add sub mul | ৬৪-বিট হিসাব, ফল 264-এর modulo-তে (পতাকা না থাকলে) | t = a + b … |
sdiv srem udiv | signed ভাগ (শূন্যের দিকে কাটা), signed ভাগশেষ, unsigned ভাগ | t = a / b, % |
icmp slt … eq ne | তুলনা, ফল i1 | t = a < b … |
xor i1 %b, true | Bool উল্টানো | t = ! a |
br, ret, unreachable | terminator: লাফ, ফেরা, “এখানে কখনো আসা যায় না” | jump, branch, return |
phi i64 [ v, %B ] … | কোন block থেকে এলেন, সেই মান | x = phi(B: v, …) |
call | function ডাকা, argument-এর type-সহ | t = call f(a) |
alloca load store | stack-এ জায়গা, memory থেকে পড়া, memory-তে লেখা | নেই (global @x ছাড়া) |
select, getelementptr | শর্ত দেখে দুটির একটি মান; ঠিকানার হিসাব | নেই |
৩ · অনুবাদক — SSA রূপের Haat IR থেকে LLVM IR
পর্ব ৬৩-এর to_ssa আমাদের হাতে SSA রূপ দিয়েছে, তাই LLVM IR-এ পৌঁছানো মূলত লাইন ধরে অনুবাদ। কিন্তু পাঁচটি জায়গায় দুই IR-এর নিয়ম মেলে না, আর প্রতিটির জন্য একটি সিদ্ধান্ত লাগে। কোড পুরোটা পাতার শেষের haat_llvm.py-তে; haat_front.py, haat_ir.py আর haat_ssa.py পর্ব ৬২ আর ৬৩ থেকে হুবহু, অপরিবর্তিত।
(ক) Type. Haat IR-এ type লেখা থাকে না, কিন্তু LLVM-এর প্রতিটি operand-এ লাগে। তথ্যটি হারায়নি: front end-এর AST-এ প্রতিটি function-এর parameter আর ফেরত type আছে, আর Haat-এর type checker (পর্ব ৫২) আগেই নিশ্চিত করেছে যে program-টি ঠিক। infer সেখান থেকে শুরু করে ধ্রুবক (5 মানে Int, true মানে Bool), তুলনা (ফল Bool), call (callee-র ফেরত type) আর copy বা φ (argument-এর type) ধরে একটি fixpoint পর্যন্ত চলে। Int → i64, Bool → i1, Str → ptr, Unit → {}.
(খ) const আর copy উধাও. LLVM IR-এ copy-র কোনো নির্দেশ নেই, আর ধ্রুবক সরাসরি operand হতে পারে। তাই অনুবাদক t1 = const 1000 বা x#1 = items-এর জন্য কিছু লেখে না; শুধু মনে রাখে “t1 মানে 1000”, “x#1 মানে %items”, আর পরের প্রতিটি ব্যবহারে সেটি বসায়। SSA-তে প্রতিটি নামের সংজ্ঞা একটিই, তাই এই বদল সব জায়গায় নিরাপদ; এটি আসলে copy propagation-এর সবচেয়ে সরল রূপ (পর্ব ৬৫-এর বিষয়)।
(গ) নাম. LLVM-এর উদ্ধৃতিহীন নামে শুধু অক্ষর, অঙ্ক আর $ . _ - চলে, # চলে না। তাই x#1 হয় %"x#1", উদ্ধৃতির ভেতরে যেকোনো চিহ্ন বৈধ। একটি সহজ বিকল্প লোভনীয়: #-কে . বানানো। কিন্তু পর্ব ৬২-এর lowering ভেতরের block-এর shadowing-এ ঠিক x.1 নাম দেয়, তাই x#1 আর ছায়া-variable x.1 একই নামে মিশে যেত। (ঘ) Entry. LLVM-এর entry block-এ কেউ লাফাতে পারে না। Haat-এর function যদি সরাসরি while দিয়ে শুরু হয়, B0 নিজেই loop-এর মাথা; তখন অনুবাদক আগে একটি entry: block বসায়, যাতে শুধু br label %B0. (B0-তে φ লাগলে পর্ব ৬৩-এর to_ssa আগেই error দেয়।)
(ঙ) Runtime. ছাপা, ভাগ আর Str-এর কাজ ছোট LLVM function-এ, যাদের নাম @haat. দিয়ে শুরু: @haat.print.Int (printf দিয়ে), @haat.print.Bool (select দিয়ে “true” বা “false” বেছে puts), @haat.div, @haat.rem, @haat.concat (strlen, malloc, memcpy) আর @haat.need. C library-র function শুধু declare করা; link-এর সময় আসে (পর্ব ৭৪)। Str হলো শেষে \00-ওয়ালা UTF-8 byte; Haat-এর string-এ \0 লেখার কোনো escape নেই, তাই strcmp দিয়ে তুলনা ঠিক। জোড়া লাগানো string কখনো মুক্ত হয় না: সেটি garbage collector-এর কাজ (পর্ব ৭৫)। Top-level variable হয় LLVM global @x, সঙ্গে @x.init পতাকা, যাতে সিদ্ধান্ত ১৮-এর 'k' is not initialized yet পরীক্ষা থাকে। <main> হয় C-এর @main, ফেরত i32 0.
নির্দেশ ধরে অনুবাদের মূল অংশ, haat_llvm.py থেকে হুবহু:
def ins_llvm(i, v, T, sig, main): # একটি Haat IR নির্দেশ → ০, ১ বা ২টি LLVM নির্দেশ
k, a, d = i.kind, i.args, local(i.dst) if i.dst else None
pos = f"i64 {i.pos[0]}, i64 {i.pos[1]}" if i.pos else ""
if k == "const" or k == "copy" and "@" not in (i.dst[0], a[0][0]): return []
if k == "copy" and a[0][0] == "@": # global পড়া: আগে "initialized কি না" পরীক্ষা (সিদ্ধান্ত ১৮)
g = a[0]; return [f"call void @haat.need(ptr {g}.init, {pos}, ptr {g}.name)", f"{d} = load {T(g)}, ptr {g}"]
if k == "copy": # global-এ লেখা; pos থাকলে assignment, না থাকলে প্রথম সংজ্ঞা
g = i.dst; st = f"store {T(g)} {v(a[0])}, ptr {g}"
return [f"call void @haat.need(ptr {g}.init, {pos}, ptr {g}.name)", st] if i.pos else [st, f"store i1 true, ptr {g}.init"]
if k == "bin":
x, y, t = v(a[0]), v(a[1]), T(a[0])
if i.sym in ARITH and t == "ptr": return [f"{d} = call ptr @haat.concat(ptr {x}, ptr {y})"]
if i.sym in ARITH: return [f"{d} = {ARITH[i.sym]} i64 {x}, {y}"]
if i.sym in "/%": return [f"{d} = call i64 @haat.{'div' if i.sym == '/' else 'rem'}(i64 {x}, i64 {y}, {pos})"]
if t == "ptr": # Str-এর == আর !=: strcmp-এর ফল ০ কি না
c = local(i.dst + "$"); return [f"{c} = call i32 @strcmp(ptr {x}, ptr {y})", f"{d} = icmp {CMP[i.sym]} i32 {c}, 0"]
return [f"{d} = icmp {CMP[i.sym]} {t} {x}, {y}"]
if k == "un": return [f"{d} = sub i64 0, {v(a[0])}" if i.sym == "-" else f"{d} = xor i1 {v(a[0])}, true"]
if k == "call":
ps = sig[i.sym][0]; args = ", ".join(f"{LL[t]} {v(x)}" for t, x in zip(ps, a))
return [f"{d} = call {LL[sig[i.sym][1]]} @{i.sym}({args})"]
if k == "print": return [f"call void @haat.print.{ {'i64': 'Int', 'i1': 'Bool', 'ptr': 'Str'}[T(a[0])] }({T(a[0])} {v(a[0])})"]
if k == "return": return ["ret i32 0" if main else f"ret {T(a[0])} {v(a[0])}"]
if k == "jump": return [f"br label %{i.targets[0]}"]
if k == "branch": return [f"br i1 {v(a[0])}, label %{i.targets[0]}, label %{i.targets[1]}"]
if k == "phi": return [f"{d} = phi {T(i.dst)} " + ", ".join(f"[ {v(x)}, %{b} ]" for x, b in zip(a, i.targets))]
raise Unsupported(k)v(x) নামটির LLVM মান দেয়: copy-র শিকল ধরে মূল নাম, বা সরাসরি ধ্রুবক। T(x) দেয় তার LLVM type. ARITH-এ + - * থেকে add sub mul, কোনো পতাকা ছাড়া; CMP-এ < থেকে slt ইত্যাদি। Str-এর তুলনায় একটি বাড়তি নাম লাগে (%t5$); Haat-এর কোনো নামে $ থাকে না, তাই সংঘর্ষ নেই। এবার চালিয়ে দেখুন।
# bazar.haat → Haat IR → SSA (পর্ব ৬২–৬৩) → LLVM IR text; prelude বাদে শুধু Haat-এর function-গুলো
from haat_llvm import *
src = open("examples/bazar.haat", encoding="utf-8").read() # চাইলে নিজের Haat program লিখুন
text, ssa = to_llvm(src)
print("SSA-তে <main>-এর B1:", *ssa.funcs["<main>"].blocks["B1"], sep="\n ")
print("type:", {x: t for (f, x), t in infer(ssa, signatures(src)).items() if f == "price"})
mine = text[text.index("\ndefine i32 @main"):] # এর আগে prelude: @haat.* আর C library
print(mine)
print("নির্দেশ: Haat IR", sum(len(b) for f in ssa.funcs.values() for b in f.blocks.values()),
"· LLVM", mine.count("\n "), "· nsw:", mine.count(" nsw "), "· sdiv:", mine.count("sdiv"))আসল আউটপুট (ব্রাউজারের Python; price আর delivery বাদ দিয়ে, সেগুলো অংশ ২-এ):
SSA-তে <main>-এর B1:
rounds#2 = phi(B0: rounds#1, B2: rounds#3)
total#2 = phi(B0: total#1, B2: total#3)
t8 = const 5000
t9 = total#2 < t8
branch t9 B2 B3
type: {'qty': 'Int', 'unit': 'Int', 'p': 'Int', 't1': 'Int', 't2': 'Bool', 't3': 'Int', 't4': 'Int', 't5': 'Int'}
define i32 @main() {
B0:
%t3 = call i64 @price(i64 2, i64 520)
%t6 = call i64 @price(i64 2, i64 520)
%t7 = call i64 @delivery(i64 %t6)
%first = add i64 %t3, %t7
call void @haat.print.Int(i64 %first)
br label %B1
B1:
%"rounds#2" = phi i64 [ 0, %B0 ], [ %"rounds#3", %B2 ]
%"total#2" = phi i64 [ 0, %B0 ], [ %"total#3", %B2 ]
%t9 = icmp slt i64 %"total#2", 5000
br i1 %t9, label %B2, label %B3
B2:
%"total#3" = add i64 %"total#2", 1250
%"rounds#3" = add i64 %"rounds#2", 1
br label %B1
B3:
call void @haat.print.Int(i64 %"total#2")
%t13 = sub i64 %"rounds#2", 1
call void @haat.print.Int(i64 %t13)
ret i32 0
}
…
নির্দেশ: Haat IR 44 · LLVM 28 · nsw: 0 · sdiv: 0
SSA-র φ rounds#2 = phi(B0: rounds#1, B2: rounds#3) হয়েছে %"rounds#2" = phi i64 [ 0, %B0 ], [ %"rounds#3", %B2 ]: জোড়ার ক্রম উল্টো ([ মান, %block ]), আর rounds#1-এর জায়গায় সরাসরি 0, কারণ rounds#1 ছিল একটি ধ্রুবকের copy. t8 = const 5000 হারিয়ে icmp slt i64 %"total#2", 5000-এর ভেতরে ঢুকেছে। পর্ব ৬৩-এর ৪৪টি Haat IR নির্দেশ (দুটি φ-সহ) হয়েছে ২৮টি LLVM নির্দেশ: সব const আর copy উধাও। Haat-এর function-এ কোনো nsw নেই, কোনো সরাসরি sdiv-ও নেই।
৪ · nsw, nuw আর poison — Haat-এর wrap কেন সাধারণ add চায়
পর্ব ৬২-এ Clang-এর C অনুবাদে mul nsw আর sub nsw দেখেছিলেন। এই nsw (no signed wrap) আর nuw (no unsigned wrap) পতাকা কোনো নির্দেশকে দ্রুত করে না; এগুলো একটি প্রতিশ্রুতি: “এই যোগে signed overflow হবে না।” LLVM-এর ভাষা-নির্দেশিকা (LangRef) বলে, প্রতিশ্রুতি ভাঙলে ফল একটি poison value.
Poison-কে একটি জাল নোট ভাবুন। হাতে হাতে ঘুরলে কেউ টের পায় না, আর শুধু ঘোরানোতে কোনো ক্ষতিও নেই। কিন্তু যে মুহূর্তে কেউ সেটি দিয়ে সত্যিকারের কেনাকাটা করে (একটি br-এর শর্ত, একটি ঠিকানা, বা বাইরের function-এ পাঠানো), তখনই আচরণ undefined behavior. আর optimizer আগে থেকেই ধরে নেয় “জাল নোট কখনো আসবে না”।
C-তে signed overflow undefined behavior (C17 আর C23 দুটিতেই), তাই Clang নির্ভয়ে nsw দেয়, আর সেই প্রতিশ্রুতি থেকে বড় optimization পায়। Haat-এ সিদ্ধান্ত ১৩ উল্টো: প্রতিটি Int ফল ৬৪ বিটে wrap করে, two's complement নিয়মে। add পতাকা ছাড়া ঠিক সেটিই করে: ফল 264-এর modulo-তে। তাই Haat-এর অনুবাদে nsw দেওয়া মানে এমন প্রতিশ্রুতি দেওয়া, যা Haat রাখে না। সত্যিকারের run-এ দেখুন। একটি ছোট Haat program:
fn bigger(x: Int) -> Bool {
return x + 1 > x;
}
print(bigger(5));
print(bigger(9223372036854775807));
Reference-এর haat.py run ছাপে true আর false: সবচেয়ে বড় Int-এর সঙ্গে ১ যোগ করলে wrap করে সবচেয়ে ছোট Int হয়। লেখকের lab-এ একটি ইচ্ছাকৃত ভুল অনুবাদক বানানো হলো, যা Haat-এর function-এ প্রতিটি add-কে add nsw করে; দুই রূপই PyPI-র ziglang 0.17.1-এর ভেতরের Clang 22.1.8 দিয়ে compile করে চালানো হলো (সত্যিকারের run):
~/llvm $ python -m ziglang cc -O2 -Wno-override-module bigger.ll -o bigger.exe
-O0 -O2
ঠিক অনুবাদ (add) true, false true, false
ভুল অনুবাদ (add nsw) true, false true, true
; ভুল অনুবাদের -O2 IR (-S -emit-llvm), প্রথম InstCombine pass-এর পরেই:
define noundef i1 @bigger(i64 %x) local_unnamed_addr #1 {
B0:
ret i1 true
}
; ঠিক অনুবাদের -O2 IR:
define i1 @bigger(i64 %x) local_unnamed_addr #1 {
B0:
%t3 = icmp ne i64 %x, 9223372036854775807
ret i1 %t3
}
দুটিই যুক্তিতে নিখুঁত। nsw থাকলে x + 1 কখনো overflow করে না ধরা যায়, তাই x + 1 > x সবসময় সত্য: ret i1 true. nsw ছাড়া InstCombine ঠিক হিসাবটি করে: wrap-এর জগতে x + 1 > x মিথ্যা শুধু একটি মানে, সবচেয়ে বড় Int-এ; তাই icmp ne i64 %x, 9223372036854775807. লক্ষ করুন, -O0-এ ভুলটি ধরা পড়েনি; শুধু -O2-এ optimizer প্রতিশ্রুতিটি ব্যবহার করল। C-তেও একই জিনিস, সত্যিকারের run: int bigger(long x) { return x + 1 > x; } -O2-এ হয় ret i32 1, আর -fwrapv (signed overflow-কে wrap ধরার Clang/GCC পতাকা) দিলে হয় সেই একই icmp ne.
প্রতিশ্রুতির দাম আছে, প্রতিশ্রুতি না দেওয়ারও। নিচের C loop (long, Clang 22.1.8, -O2, সত্যিকারের run) পুরোটাই একটি সূত্রে নেমে গেল: (target - 1) / 1250 + 1, udiv দিয়ে। Haat-এ একই loop-এর অনুবাদ -O2-এর পরেও loop থাকল (rotate করা, কিন্তু loop). কারণ wrap-এর জগতে সূত্রটি ভুল: target = 9223372036854775807 হলে Haat-এর loop কখনো শেষ হয় না (অনুশীলন ৩), অথচ সূত্র একটি উত্তর দিয়ে দেয়।
long rounds(long target) { // Haat-এ একই দেহ, fn rounds(target: Int) -> Int
long total = 0, n = 0;
while (total < target) { total = total + 1250; n = n + 1; }
return n;
}
; C, -O2: ; Haat-এর অনুবাদ, -O2:
%0 = add nsw i64 %target, -1 B2:
%1 = udiv i64 %0, 1250 %"total#23" = phi i64 [ %"total#3", %B2 ], [ 0, %B0 ]
%2 = add nuw nsw i64 %1, 1 %"n#22" = phi i64 [ %"n#3", %B2 ], [ 0, %B0 ]
%"total#3" = add i64 %"total#23", 1250
%"n#3" = add i64 %"n#22", 1
%t1 = icmp slt i64 %"total#3", %target
br i1 %t1, label %B2, label %B3
তবে wrap মানে সব optimization বন্ধ নয়। LLVM নিজে যা প্রমাণ করতে পারে, তা করে: bags-এর অনুবাদে (left ধনাত্মক থেকে ৬ করে কমে, তাই overflow অসম্ভব) -O2 loop-টি udiv-এর সূত্রে নামিয়েছে, আর price-এর sub i64 %p, %t4-এ LLVM নিজেই nsw যোগ করেছে, কারণ p > 999 জানা থাকলে p - p/10 overflow করতে পারে না। পতাকা আমরা দিই না; দরকার হলে প্রমাণ করে compiler নিজে দেয়।
৫ · sdiv, শূন্য আর INT_MIN / -1 — স্পষ্ট পরীক্ষা
LangRef অনুযায়ী sdiv-এ দুটি অবস্থা undefined behavior: শূন্য দিয়ে ভাগ, আর overflow, অর্থাৎ সবচেয়ে ছোট মানকে −১ দিয়ে ভাগ (৬৪ বিটে −9223372036854775808 / −1-এর উত্তর +9223372036854775808, যা i64-এ ধরে না)। srem-এরও একই দুই অবস্থা। এগুলো poison নয়, সরাসরি UB: optimizer ধরে নিতে পারে এমন ভাগ কখনো হয় না। Haat-এ দুটির অর্থ নির্দিষ্ট: শূন্য দিয়ে ভাগ বা ভাগশেষ হলো runtime error division by zero (সিদ্ধান্ত ২৬, অবস্থান ভাগ চিহ্নে, সিদ্ধান্ত ২৪), আর INT_MIN / -1 = INT_MIN, INT_MIN % -1 = 0 (সিদ্ধান্ত ১৩)। তাই অনুবাদ নিজে পরীক্ষা বসায়। @haat.div, prelude থেকে হুবহু:
define internal i64 @haat.div(i64 %a, i64 %b, i64 %line, i64 %col) {
entry:
%zero = icmp eq i64 %b, 0 ; সিদ্ধান্ত ২৬: শূন্য দিয়ে ভাগ = runtime error
br i1 %zero, label %fail, label %ok
fail:
call i32 (ptr, ...) @printf(ptr @.div0, i64 %line, i64 %col)
call void @exit(i32 1)
unreachable
ok:
%minus1 = icmp eq i64 %b, -1 ; সিদ্ধান্ত ১৩: INT_MIN / -1 = INT_MIN (wrap), sdiv-এ যা UB
br i1 %minus1, label %neg, label %div
neg:
%n = sub i64 0, %a
ret i64 %n
div:
%q = sdiv i64 %a, %b
ret i64 %q
}
1%zero = icmp eq %b, 02br %zero: fail বা ok3fail: printf; exit(1)4ok: %minus1 = icmp eq %b, -15br %minus1: neg বা div6neg: %n = sub 0, %a; ret7div: %q = sdiv %a, %b; ret
| a, b | |
| %zero | |
| %minus1 | |
| ফল |
- ১০০০ / ৪: শূন্য?
%b= ৪, তাই%zero= false;okblock-এ যাওয়া। - −১? না, তাই
divblock. এই দুটি তুলনাই সাধারণ পথে বাড়তি খরচ: দুটিicmpআর দুটিbr. sdiv. এখন ভাগটি নিরাপদ: ভাজক শূন্য নয়, আর ভাজক −১ নয় বলে overflow অসম্ভব।sdivশূন্যের দিকে কেটে ২৫০ দেয়, ঠিক C-ধাঁচেরc_div-এর মতো।- INT_MIN / −১. শূন্য নয়, কিন্তু
%minus1= true:negblock. sub i64 0, %a. ০ − INT_MIN, 264-এর modulo-তে, আবার INT_MIN: Haat যা চায়। এখানে সরাসরিsdivথাকলে x86-64-এরidivনির্দেশ একটি hardware exception তুলত (নিচের run).- ১০০০ / ০.
%zero= true:failblock. এখানে কোনো ভাগই হয় না। - Error.
printfলেখে2:18: runtime error: division by zero(শেষের দুটি argument থেকে line আর col), তারপরexit(1);unreachableবলে এর পরে আর কিছু চলে না। Reference-ও ঠিক এই লাইন লেখে।
পরীক্ষা ছাড়া কী হয়, তা অনুমান নয়, সত্যিকারের run. Program: fn share(total: Int, people: Int) -> Int { return total / people; }, তারপর print(share(1000, 4));, print(share(-9223372036854775807 - 1, -1));, print(share(1000, 0));. ইচ্ছাকৃত ভুল অনুবাদক @haat.div-এর জায়গায় সরাসরি sdiv বসায়:
reference (haat.py run) 250 / -9223372036854775808 / 2:18: runtime error: division by zero
ঠিক অনুবাদ, -O0 ও -O2 250 / -9223372036854775808 / 2:18: runtime error: division by zero
সরাসরি sdiv, -O0 (কিছুই ছাপা হয়নি) exit code 3221225621 = 0xC0000095
সরাসরি sdiv, -O2 250 / 140716954219752 / 140716954219752
-O0-এ idiv INT_MIN / −১-এ hardware exception তুলেছে; Windows-এর exit code 0xC0000095 হলো STATUS_INTEGER_OVERFLOW. আগের লাইনের 250-ও হারাল: আউটপুট pipe-এ যাচ্ছিল, তাই C library সেটি buffer-এ রেখেছিল, আর program ভাঙায় buffer কখনো লেখা হয়নি। -O2-এ optimizer ভাগ দুটিকে UB জেনে কিছু একটা বসিয়েছে, আর ছাপা হলো একটি অর্থহীন সংখ্যা, সম্ভবত কোনো register-এ পড়ে থাকা মান। একই source, একই compiler, দুই রকম ভুল: UB-র এটিই চরিত্র (পর্ব ০৬-এর overflow-এর তুলনাও দেখুন)।
পরীক্ষার খরচ কতটা? বেশির ভাগ ক্ষেত্রে শূন্যের কাছাকাছি। price-এ ভাজক ধ্রুবক ১০; -O2-এ @haat.div inline হলো, দুটি পরীক্ষা মুছে গেল, আর রইল শুধু udiv i64 %p, 10. অনুশীলন ২-এর avg-এ ভাগ হয় if n > 0-এর ভেতরে; সেখানেও -O2 দুটি পরীক্ষাই মুছে সরাসরি sdiv রেখেছে। পরীক্ষা থাকে শুধু সেখানে, যেখানে compiler সত্যিই জানে না, আর ঠিক সেখানেই পরীক্ষাটি দরকার। Rust-ও এই পথে চলে: ভাগে শূন্য আর overflow-এর পরীক্ষা বসায়, আর ধরা পড়লে panic করে, debug আর release দুই build-এই।
৬ · alloca, mem2reg আর SROA — Clang-এর পথ
আমাদের অনুবাদক SSA পেয়েছে পর্ব ৬৩ থেকে: dominator, frontier, φ বসানো, নাম বদল। Clang অন্য পথে হাঁটে। তার front end SSA বানায় না; প্রতিটি local variable-এর জন্য stack-এ একটি ঘর নেয় (alloca), লেখে store দিয়ে, পড়ে load দিয়ে। Memory-তে বহুবার লেখায় SSA ভাঙে না, কারণ SSA-র শর্ত শুধু %নাম-এর ওপর। তারপর একটি pass ঘরগুলোকে register-এর নামে তোলে আর দরকারি জায়গায় phi বসায়: ধ্রুপদী pass-টি mem2reg, আর আধুনিক pipeline-এ একই কাজ আগেই করে SROA (scalar replacement of aggregates). পর্ব ৬৩-এর bags-এ SROA-র ফল দেখেছিলেন; এবার একটি নতুন loop, rounds, ধাপে ধাপে (Clang 22.1.8, -O0 আর -O1 -mllvm -print-after=sroa, সত্যিকারের run).
1alloca: %total, %n2store 0 → %total, %n3cond: %0 = load %total4%cmp = icmp slt %0, %15body: load, add nsw6store %add → %total7end: load %n; ret8SROA-র পরে: শুধু phi
| total | |
| n | |
| নির্দেশ |
- ঘর নেওয়া.
-O0-এ Clang তিনটিallocaলেখে:%target.addr,%total,%n. Parameter-ও প্রথমে নিজের ঘরে কপি হয়। Front end-এর কাজ সহজ: কোনো φ ভাবতে হয় না। - শুরুর মান.
store i64 0, ptr %totalআর%n-এ একই। Variable-এর মান এখন memory-তে, কোনো নামে নয়। - পড়া. Loop-এর শর্তে
%0 = load i64, ptr %total: প্রতিবার ঘর থেকে নতুন করে পড়া। - তুলনা.
%cmp = icmp slt i64 %0, %1, যেখানে%1হলো%target.addrথেকে পড়া। SSA-র শর্ত ঠিক আছে: প্রতিটি%-নাম একবার। - শরীর.
%add = add nsw i64 %2, 1250, তারপরstore. একই ঘরে বহুবার লেখা হয়, কিন্তু সেটি memory, নাম নয়। - SROA-র সিদ্ধান্ত. কোনো ঘরের ঠিকানা বাইরে যায় না (শুধু সরাসরি
load/store), তাই তিনটিই তোলা যায়।while.cond-এ দুই পথ মেলে (entryআরwhile.body), তাই সেখানে φ:%total.0 = phi i64 [ 0, %entry ], [ %add, %while.body ], আর%n.0-এর একই রকম। পর্ব ৬৩-এর ভাষায়: সংজ্ঞার iterated dominance frontier. - ফল. প্রতিটি
load-এর জায়গায় সেই বিন্দুতে পৌঁছানো মান, প্রতিটিstoreআরallocaমুছে গেল;ret i64 %n.0. এটি আমাদের অনুবাদের সঙ্গে প্রায় হুবহু, শুধু নাম আলাদা (%n.0বনাম%"n#2"). -O2. পরের pass-গুলো loop-টিই মুছে দেয়:%1 = udiv i64 %0, 1250দিয়ে ঘোরার সংখ্যা সরাসরি, অংশ ৪-এর C কলামের মতো। এটি সম্ভব হলোadd nsw-এর প্রতিশ্রুতির জন্য।
দুই পথের তুলনা শিক্ষণীয়। Clang-এর পথে front end সরল থাকে, আর SSA বানানোর কঠিন কাজ একবার, একটি pass-এ, সব ভাষার জন্য লেখা হয়; আরও অনেক front end-ও অন্তত বেশির ভাগ local-এর জন্য এভাবেই alloca লেখে। আমাদের পথে SSA বানানো front end-এর দায়িত্ব, কারণ পর্ব ৬৩-এর লক্ষ্যই ছিল সেটি নিজে শেখা। দুটিই বৈধ LLVM IR দেয়, আর -O2-এর পরে প্রায় একই কোড। আসল pipeline-টা কেমন? -mllvm -print-pipeline-passes দিলে Clang পুরো pass pipeline এক লম্বা লাইনে ছাপে; price.c-এর -O2-এর সত্যিকারের run-এ লাইনটির শুরু:
memprof-remove-attributes,annotation2metadata,forceattrs,declare-to-assign,inferattrs,
coro-early,function<eager-inv>(ee-instrument<>,lower-expect,simplifycfg<…>,sroa<modify-cfg>,
early-cse<>),openmp-opt,ipsccp,called-value-propagation,globalopt,function<eager-inv>(mem2reg,
instcombine<max-iterations=1;no-verify-fixpoint>, …
সেই লাইনে sroa ৪ বার, instcombine ৯ বার, আর mem2reg একবার, SROA-র পরে। অর্থাৎ এই pipeline-এ alloca তোলার কাজ প্রথমে করে SROA; mem2reg পরে আসে, তখন সাধারণত তোলার কিছু বাকি থাকে না। Pass-এর তালিকা আর ক্রম LLVM-এর version আর লক্ষ্য-যন্ত্রভেদে বদলায়, তাই নিজের version-এ নিজে ছাপিয়ে দেখুন।
৭ · সত্যিকারের Clang-এ চালানো — differential test আর verifier
অনুবাদকের আউটপুট একটি সাধারণ .ll ফাইল। PyPI-র ziglang প্যাকেজে (প্যাকেজের licence MIT; ভেতরের LLVM আর Clang-এর licence Apache 2.0, LLVM ব্যতিক্রমসহ) Zig 0.17.1 আর তার ভেতরে Clang 22.1.8 আছে, আর Clang সরাসরি .ll input নেয়: verifier চালায়, pass pipeline চালায়, machine code বানায়, link করে। Module-এ আমরা কোনো target triple লিখিনি, তাই Clang নিজের ডিফল্ট x86_64-unknown-windows-gnu নেয় (-Wno-override-module সেই সতর্কবার্তা চুপ করায়)। লেখকের lab-এ সত্যিকারের run:
~/llvm $ python -m ziglang cc -O2 -Wno-override-module bazar.ll -o bazar.exe
~/llvm $ ./bazar.exe
996
5000
3
তারপর differential testing, এই মডিউলের স্থায়ী নিয়ম। প্রতিটি program অনুবাদ করে -O0 আর -O2-এ আলাদা exe বানিয়ে চালানো হলো, আর ছাপা প্রতিটি লাইন reference-এর python -B haat.py run-এর stdout আর stderr-এর সঙ্গে মেলানো হলো (আমাদের runtime error stdout-এ যায়, reference-এর stderr-এ; লাইনগুলো ক্রমে জুড়ে তুলনা)। ফল:
| Program | -O0-এ হুবহু | -O2-এ হুবহু |
|---|---|---|
| reference-এর ৮টি উদাহরণ (bazar, recursion, mutual, shadowing, shortcircuit, strings, loops, err_divzero) | ৮ | ৮ |
haat_gen.py-র seed ০–২,৯৯৯ (৯,০০১টি function, LLVM-এ ১৫,৬৭০টি phi, ৩২৫টি division by zero-এ শেষ) | ৩,০০০ | ৩,০০০ |
বাছাই করা কিনারা: global-এর আগে call ('k' is not initialized yet), বাংলা Str, a / (a - a), while দিয়ে শুরু হওয়া Unit function (আলাদা entry block) | ৪ | ৪ |
counter, nested (closure) | বাদ: Haat IR v1-এর বাইরে, পর্ব ৬২-এর মতোই | |
একটি সৎ সীমা: reference-এর ১,০০০-call সীমা (stack overflow, সিদ্ধান্ত ২৬) এই অনুবাদকে নেই। কোনো উদাহরণ বা এলোমেলো program সেই সীমা ছোঁয় না, তাই উপরের test এটি ধরেনি; অনুশীলন ১-এ এটি যোগ করবেন। আর ইচ্ছাকৃত ভুল অনুবাদক দুটি একই test-এ কেমন করে? প্রথম ১,০০০টি এলোমেলো program-এ, সত্যিকারের run:
| ভুল অনুবাদক | -O0-এ অমিল | -O2-এ অমিল |
|---|---|---|
সব add/sub/mul-এ nsw (১,০০০টিতেই লেখা বদলেছে) | ০ | ৮১, একটিও ভাঙেনি, শুধু ভুল আউটপুট |
পরীক্ষা ছাড়া সরাসরি sdiv/srem (৯৭৩টিতে অন্তত একটি ভাগ) | ১২২, তার ৯৮টি ভেঙে থেমেছে | ১২২, তার ৩৩টি ভেঙে থেমেছে |
nsw-এর ভুল -O0-এ একটিও ধরা পড়েনি: সেখানে কোনো optimizer প্রতিশ্রুতিটি ব্যবহার করে না, আর x86-এর add এমনিতেই wrap করে। তাই differential test সবসময় অন্তত দুই opt স্তরে চালান।
-O2-এ bazar.haat-এর কী রইল? -Rpass=inline একটি optimization remark চায়: প্রতিটি inline হওয়া call-এর জন্য Clang একটি লাইন লেখে। সত্যিকারের run, বিস্তারিত সংক্ষেপে:
~/llvm $ python -m ziglang cc -O2 -Wno-override-module -S -emit-llvm bazar.ll -o bazar_O2.ll -Rpass=inline
remark: 'haat.div' inlined into 'price' with (cost=-15045, threshold=337) [-Rpass=inline]
remark: 'price' inlined into 'main' with (cost=-40, threshold=337) [-Rpass=inline]
remark: 'price' inlined into 'main' with (cost=-40, threshold=337) [-Rpass=inline]
remark: 'delivery' inlined into 'main' with (cost=-35, threshold=337) [-Rpass=inline]
remark: 'haat.print.Int' inlined into 'main' with (cost=5, threshold=337) [-Rpass=inline]
…
define noundef i32 @main() local_unnamed_addr #0 {
B0:
%0 = tail call i32 (ptr, ...) @printf(ptr nonnull dereferenceable(1) @.int, i64 996)
%1 = tail call i32 (ptr, ...) @printf(ptr nonnull dereferenceable(1) @.int, i64 5000)
%2 = tail call i32 (ptr, ...) @printf(ptr nonnull dereferenceable(1) @.int, i64 3)
ret i32 0
}
পুরো program তিনটি ধ্রুবক ছাপায় নেমে এসেছে। Inlining-এর পরে price(2, 520)-এর সব মান জানা, তাই constant folding ৯৯৬ বের করেছে; আর while loop-টি compile-এর সময়েই চালিয়ে ৫০০০ আর ৩ পাওয়া গেছে। কোন pass কী করল, তা পর্ব ৬৫ থেকে ৬৭-এর বিষয়।
অনুবাদকে ভুল থাকলে কী হয়? LLVM-এর verifier compile-এর আগে IR-এর গঠন যাচাই করে। লেখকের lab-এ bazar.ll-এ তিনটি ইচ্ছাকৃত ভুল, তিনটি সত্যিকারের Clang বার্তা:
; ১. উদ্ধৃতি ছাড়া %rounds#2
bad1.ll:96:10: error: expected '=' after instruction name
96 | %rounds#2 = phi i64 [ 0, %B0 ], [ %rounds#3, %B2 ]
; ২. একই নামের দুটি সংজ্ঞা
bad2.ll:93:3: error: multiple definition of local value named 'first'
; ৩. φ-তে একটি predecessor-এর জোড়া বাদ
error: invalid LLVM IR input: PHINode should have one entry for each predecessor of its parent basic block!
%"rounds#2" = phi i64 [ 0, %B0 ]
প্রথম দুটি parser-এর বার্তা, তৃতীয়টি verifier-এর। কিন্তু অংশ ৪-এর add nsw বা অংশ ৫-এর সরাসরি sdiv কোনো verifier ধরে না: গঠনে সেগুলো নিখুঁত, শুধু অর্থ ভুল। সেগুলো ধরে শুধু চালিয়ে মেলানো।
এবার ব্রাউজারে। এখানে Clang নেই, তাই প্রথমে দেখুন অনুবাদে global, Str আর % কী রূপ নেয়:
# global (সিদ্ধান্ত ১৮), Str আর % — অনুবাদে কী আসে
from haat_llvm import *
src = """var paid = 0;
fn pay(n: Int) -> Int {
paid = paid + n;
return paid % 7;
}
print("হাট" + "!");
print(pay(10) == 3);
"""
text, ssa = to_llvm(src)
print(text[text.index("\n@.s0"):].strip())
print("x#1 →", local("x#1"), "· x.1 →", local("x.1"), "· t7$ →", local("t7$"))আসল আউটপুট (ব্রাউজারের Python):
@.s0 = private unnamed_addr constant [10 x i8] c"\E0\A6\B9\E0\A6\BE\E0\A6\9F\00"
@.s1 = private unnamed_addr constant [2 x i8] c"!\00"
@paid = internal global i64 zeroinitializer
@paid.init = internal global i1 false
@paid.name = private unnamed_addr constant [5 x i8] c"paid\00"
define i32 @main() {
B0:
store i64 0, ptr @paid
store i1 true, ptr @paid.init
%t4 = call ptr @haat.concat(ptr @.s0, ptr @.s1)
call void @haat.print.Str(ptr %t4)
%t6 = call i64 @pay(i64 10)
%t8 = icmp eq i64 %t6, 3
call void @haat.print.Bool(i1 %t8)
ret i32 0
}
define i64 @pay(i64 %n) {
B0:
call void @haat.need(ptr @paid.init, i64 3, i64 12, ptr @paid.name)
%t1 = load i64, ptr @paid
%t2 = add i64 %t1, %n
call void @haat.need(ptr @paid.init, i64 3, i64 5, ptr @paid.name)
store i64 %t2, ptr @paid
call void @haat.need(ptr @paid.init, i64 4, i64 12, ptr @paid.name)
%t3 = load i64, ptr @paid
%t5 = call i64 @haat.rem(i64 %t3, i64 7, i64 4, i64 17)
ret i64 %t5
}
x#1 → %"x#1" · x.1 → %x.1 · t7$ → %t7$
“হাট” তিনটি বাংলা অক্ষর, UTF-8-এ প্রতিটি ৩ byte, শেষে \00: মোট ১০ byte, তাই [10 x i8] (UTF-8-এর বিস্তার পর্ব ২১-এ)। paid একটি function পড়ে আর লেখে, তাই সেটি LLVM global, memory-তে; SSA-র নাম বদল একে ছোঁয় না (পর্ব ৬৩-এর ভাবনার প্রশ্ন ৫)। প্রতিটি পড়া আর assignment-এর আগে @haat.need, অবস্থানসহ: 3:12 ডান দিকের paid, 3:5 assignment-এর লক্ষ্য। <main>-এর প্রথম store-এর কোনো পরীক্ষা নেই, কারণ সেটিই সংজ্ঞা, আর তার পরেই পতাকা true. লেখকের lab-এ এই program-ও Clang দিয়ে চালানো হয়েছে: -O0 আর -O2 দুটিতেই হাট! আর true, reference-এর মতো।
দ্বিতীয় ব্লক অনুবাদের অর্থ যাচাই করে। Clang ছাড়া চালাতে পাতার শেষে একটি ছোট সহায়ক ll_mini.py: শুধু এই অনুবাদকের লেখা LLVM-এর উপসেট বোঝে এমন একটি interpreter, যেখানে @haat.* function-গুলো Python-এ (c_div, c_mod ইত্যাদি)। এটি আসল যাচাইয়ের বিকল্প নয়, সেটি উপরের Clang-এর run; এটি দেখায় যে text-টির অর্থ ঠিক, আর যেকোনো Haat program বসিয়ে আপনি নিজে মেলাতে পারেন।
# ব্রাউজারে clang নেই: অনুবাদের LLVM IR-কে ll_mini.py-র ছোট interpreter দিয়ে চালিয়ে reference-এর সঙ্গে মেলানো
import hashlib, re
from haat_llvm import *
from ll_mini import run_ll
from haat_gen import gen_program
def digest(lines): return hashlib.sha256("\n".join(lines).encode()).hexdigest()[:10]
same = flags = 0
for name in ("bazar", "recursion", "mutual", "shadowing", "shortcircuit", "strings", "loops", "err_divzero"):
src = open(f"examples/{name}.haat", encoding="utf-8").read()
want = open(f"examples/{name}.out", encoding="utf-8").read().split("\n")[:-1]
same += run_ll(to_llvm(src)[0]) == want
print(f"উদাহরণ ৮টি: {same}টি হুবহু")
ref = open("random_ref.txt", encoding="utf-8").read().split()
ok = phis = 0
for s in range(len(ref)):
text = to_llvm(gen_program(s))[0]; mine = text[text.index("\ndefine i32 @main"):]
ok += digest(run_ll(text)) == ref[s]; phis += mine.count(" = phi ")
flags += len(re.findall(r" (nsw|nuw) |sdiv|srem", mine))
print(f"এলোমেলো {len(ref)}টি: {ok}টি হুবহু · LLVM phi {phis}টি · Haat-এর function-এ nsw/nuw/sdiv/srem {flags}টি")
print(run_ll(to_llvm("fn f(a: Int) -> Int { return a / (a - a); }\nprint(7);\nprint(f(5));\n")[0]))আসল আউটপুট (ব্রাউজারের Python):
উদাহরণ ৮টি: 8টি হুবহু
এলোমেলো 200টি: 200টি হুবহু · LLVM phi 999টি · Haat-এর function-এ nsw/nuw/sdiv/srem 0টি
['7', '1:32: runtime error: division by zero']
৮টি উদাহরণ আর পর্ব ৬২-এর ২০০টি এলোমেলো program-এর digest সব মিলেছে; ৯৯৯টি phi, ঠিক পর্ব ৬৩-এ গোনা ৯৯৯টি φ: অনুবাদে একটিও হারায়নি বা বাড়েনি। Haat-এর নিজের function-এ কোনো পতাকা বা সরাসরি ভাগ নেই; sdiv/srem আছে শুধু prelude-এর পরীক্ষার পরে। শেষ লাইনে ভাগ চিহ্নের অবস্থান 1:32, আর একই program Clang-এ -O0 আর -O2 দুটিতেই ঠিক এই দুটি লাইন ছেপেছে (লেখকের lab). নিজের program বসিয়ে দেখুন, যেমন % আর ঋণাত্মক সংখ্যা।
শেষে একটি JavaScript ব্লক: LLVM IR-এর একটি ছোট explorer আর verifier. এটি অংশ ৪-এর Haat rounds-এর অনুবাদ (এই অনুবাদকের সত্যিকারের আউটপুট) পড়ে প্রতিটি block-এর predecessor, φ আর terminator দেখায়, আর verifier-এর চারটি শর্ত পরীক্ষা করে: এক নামে এক সংজ্ঞা, প্রতিটি block-এর শেষে terminator, প্রতিটি φ-তে প্রতিটি predecessor-এর জোড়া, আর প্রতিটি ব্যবহৃত নামের সংজ্ঞা।
// LLVM IR-এর ছোট explorer আর verifier (rounds, haat_llvm.py-র আসল আউটপুট); একটি লাইন বদলে বা মুছে আবার চালান
const IR = `define i64 @rounds(i64 %target) {
B0:
br label %B1
B1:
%"n#2" = phi i64 [ 0, %B0 ], [ %"n#3", %B2 ]
%"total#2" = phi i64 [ 0, %B0 ], [ %"total#3", %B2 ]
%t1 = icmp slt i64 %"total#2", %target
br i1 %t1, label %B2, label %B3
B2:
%"total#3" = add i64 %"total#2", 1250
%"n#3" = add i64 %"n#2", 1
br label %B1
B3:
ret i64 %"n#2"
}`;
const NAME = /%("[^"]+"|[\w.$]+)/g, B = {}, defs = {}, bad = []; let cur; IR.split("\n")[0].match(NAME).forEach(p => defs[p] = "param");
for (const line of IR.split("\n").slice(1, -1)) {
if (line[0] !== " ") { cur = line.slice(0, -1); B[cur] = { ins: [], preds: [] }; continue; }
const s = line.trim(), d = s.match(/^(%\S+) = /); B[cur].ins.push(s);
if (d) { if (defs[d[1]]) bad.push(`${d[1]} দুবার সংজ্ঞায়িত`); defs[d[1]] = cur; }
}
for (const [b, { ins }] of Object.entries(B)) {
if (!/^(br|ret|unreachable)\b/.test(ins.at(-1))) bad.push(`${b}: শেষে terminator নেই`);
for (const t of ins.at(-1).match(/label %\w+/g) || []) B[t.slice(7)].preds.push(b);
}
for (const [b, { ins, preds }] of Object.entries(B)) {
const phis = ins.filter(s => / = phi /.test(s)), want = [...preds].sort().join(",");
for (const p of phis) { const from = [...p.matchAll(/, %(\w+) \]/g)].map(m => m[1]).sort().join(",");
if (from !== want) bad.push(`${b}: φ-তে জোড়া {${from}}, predecessor {${want}}`); }
for (const s of ins) for (const u of s.split(" = ").pop().match(NAME) || [])
if (!B[u.slice(1)] && !defs[u]) bad.push(`${b}: ${u}-এর সংজ্ঞা নেই`);
console.log(`${b} ← ${want || "(entry)"} · φ ${phis.length} · নির্দেশ ${ins.length} · শেষে ${ins.at(-1).split(" ")[0]}`);
}
console.log(`nsw/nuw: ${(IR.match(/ (nsw|nuw) /g) || []).length} · সংজ্ঞা: ${Object.keys(defs).length}\n` + (bad.length ? "সমস্যা:\n " + bad.join("\n ") : "যাচাই: ঠিক আছে"));আসল আউটপুট (browser-এর JavaScript):
B0 ← (entry) · φ 0 · নির্দেশ 1 · শেষে br
B1 ← B0,B2 · φ 2 · নির্দেশ 4 · শেষে br
B2 ← B1 · φ 0 · নির্দেশ 3 · শেষে br
B3 ← B1 · φ 0 · নির্দেশ 1 · শেষে ret
nsw/nuw: 0 · সংজ্ঞা: 6
যাচাই: ঠিক আছে
Loop-এর মাথা B1-এ দুটি predecessor (B0 থেকে প্রথমবার, B2 থেকে প্রতিবার ফেরার সময়), তাই দুটি φ, আর B0-তে শুধু br: Haat-এর var total = 0; আর var n = 0; ছিল ধ্রুবকের copy, তাই সরাসরি φ-এর 0-তে ঢুকেছে। “সংজ্ঞা: 6” মানে ৫টি নির্দেশ আর parameter %target. B1-এর প্রথম φ থেকে [ %"n#3", %B2 ] মুছে চালালে আসে B1: φ-তে জোড়া {B0}, predecessor {B0,B2}, অংশের শুরুর Clang-এর তৃতীয় বার্তার মতো একই ভুল; আর B2-তে %"n#2"-কে %"n#4" করলে আসে B2: %"n#4"-এর সংজ্ঞা নেই. একই অনুবাদ Clang-এ rounds(5000)-এ 4 দিয়েছে, দুই স্তরেই।
৮ · Pass, remark আর opt — LLVM-এর tool-গুলো
LLVM-এর পূর্ণ বিতরণে আলাদা আলাদা tool থাকে: opt একটি .ll বা .bc ফাইলে নির্দিষ্ট pass চালায়, llc IR থেকে assembly বানায়, llvm-as আর llvm-dis text আর bitcode-এর মধ্যে বদলায়। ziglang প্যাকেজে শুধু Zig আর তার ভেতরের Clang আছে, এই tool-গুলো নেই। তাই এই পর্বের সব run Clang দিয়ে: .ll ফাইলে -O2 দিলে Clang সেই একই ধরনের ডিফল্ট pipeline চালায়, যা opt -O2-এর কাজ। Clang-এর ভেতর দিয়ে LLVM-এর পতাকা পাঠাতে -mllvm:
| পতাকা | কী করে (এই পর্বে সত্যিকারের run) |
|---|---|
-S -emit-llvm | machine code নয়, LLVM IR-এর text লেখে |
-fno-discard-value-names | C থেকে IR-এ variable-এর নাম রাখে (%total, না হলে %0) |
-fno-sanitize=undefined | zig cc-এর ডিফল্ট UBSan পরীক্ষা বন্ধ, যাতে IR পরিষ্কার থাকে |
-mllvm -print-after=sroa | নির্দিষ্ট pass-এর ঠিক পরের IR ছাপে; -filter-print-funcs= দিয়ে একটি function |
-mllvm -print-pipeline-passes | পুরো pass pipeline-এর তালিকা |
-Rpass=inline | সফল inlining-এর remark; -Rpass-missed= দেয় ব্যর্থগুলোর |
-fwrapv | C-তে signed overflow-কে wrap ধরা, তখন nsw আসে না |
অংশ ৪-এর ret i1 true কোন pass-এ এল? -mllvm -print-after=instcombine -mllvm -filter-print-funcs=bigger দিয়ে দেখা গেল: nsw-ওয়ালা অনুবাদে প্রথম InstCombine pass-এর পরেই ret i1 true, আর ঠিক অনুবাদে সেই একই জায়গায় icmp ne. LLVM-এর পূর্ণ বিতরণ থাকলে একটি pass একা চালানো যায়, যেমন opt -passes=mem2reg -S in.ll -o out.ll; এটি নতুন pass manager-এর লেখার ধরন, কিন্তু এই পর্বে opt চালানো হয়নি (উদাহরণ, চালানো হয়নি)। PyPI-র llvmlite (LLVM-এর Python binding) দিয়েও IR বানিয়ে JIT করা যায়; Clang নিজেই .ll নেওয়ায় এই পর্বে সেটি দরকার হয়নি।
আরও গভীরে: Poison আর undef-এর নিয়ম বহু বছর অস্পষ্ট ছিল, আর কিছু optimization একসঙ্গে অসংগত ছিল; Juneyoung Lee, Nuno Lopes, John Regehr ও সহলেখকদের ২০১৭ সালের PLDI প্রবন্ধ “Taming Undefined Behavior in LLVM” এর একটি সংগত রূপ প্রস্তাব করে, আর তার ফলে LLVM-এ freeze নির্দেশ আসে (মোটামুটি LLVM 10-এ, ২০২০ সালে)। Nuno Lopes, John Regehr ও সহকর্মীদের Alive2 (২০২১ সালের দিকের PLDI প্রবন্ধ) একটি optimization-এর আগের আর পরের IR-কে SMT solver দিয়ে মিলিয়ে দেখে ফলটি সঠিক কি না, অর্থাৎ translation validation; এভাবে LLVM-এ অনেক ভুল ধরা পড়েছে বলে লেখকেরা জানান। আরেকটি ধারা MLIR: একাধিক স্তরের IR একই কাঠামোয়, যার কথা পর্ব ৬৩-এ block argument প্রসঙ্গে এসেছে।
পরীক্ষা ও ইন্টারভিউতে: এই প্রশ্নগুলো প্রায়ই আসে, বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায়। LLVM IR কেন SSA? → প্রতিটি মানের একটি সংজ্ঞা, তাই def-use সরাসরি আর optimization সরল; মিলনে phi. add nsw মানে কী? → signed overflow হবে না, এই প্রতিশ্রুতি; ভাঙলে poison. Clang local variable-কে SSA-তে আনে কীভাবে? → alloca/load/store, পরে SROA বা mem2reg. sdiv কখন UB? → শূন্য দিয়ে ভাগ আর INT_MIN / −১. একটি function-এর LLVM IR লিখুন → type-সহ প্রতিটি operand, প্রতিটি block-এ terminator, মিলনে phi; অংশ ২ আর অনুশীলন ২-এর মতো।
৯ · AI-এর যুগে LLVM IR
AI assistant LLVM IR-এর ছোট উদাহরণ ভালোই লেখে। ভুল আসে তিন জায়গায়: পুরোনো version-এর syntax, পতাকার অর্থ, আর undefined behavior-কে নির্দিষ্ট ফল ধরে নেওয়া। শেষটি সবচেয়ে বিপজ্জনক, কারণ সেটি -O0-এর test পেরিয়ে যায় (অংশ ৪)।
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
পুরোনো typed pointer (i64*, i8*) লেখা; আধুনিক LLVM-এ শুধু ptr | নিজের Clang-এ .ll compile করা; parser সঙ্গে সঙ্গে আপত্তি তোলে |
“wrap চাই” বলার পরেও add nsw লেখা, বা C-এর IR নকল করা | সবচেয়ে বড় Int-এর কিনারায় test, -O2-এ চালিয়ে reference-এর সঙ্গে মেলানো |
শূন্য বা −১-এর পরীক্ষা ছাড়া sdiv/srem | a / 0, INT_MIN / -1, INT_MIN % -1 দিয়ে দুই opt স্তরে চালানো |
φ-এর জোড়া [ %block, মান ] উল্টো, বা একটি predecessor বাদ | Verifier-এর বার্তা পড়া; ছোট CFG-তে predecessor হাতে গোনা |
বানানো pass-এর নাম বা -mllvm পতাকা, অন্য version-এর আউটপুট | -print-pipeline-passes আর -print-after= নিজের version-এ চালিয়ে দেখা |
AI-কে কাজে লাগাতে ভাষার নিয়ম আর যাচাইয়ের পথ নিজেই বলে দিন:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Compiler-এর ইতিহাসে বহু IR এসেছে, কিন্তু LLVM IR কেন এত ভাষার সাধারণ লক্ষ্য হয়ে উঠল? শুধু প্রযুক্তি, নাকি আরও কিছু?
“একটি সাধারণ মাঝের ভাষা” ধারণাটি পুরোনো: ১৯৫০-এর দশকের শেষে UNCOL নামে একটি সর্বজনীন মাঝের ভাষার প্রস্তাব এসেছিল, যা কখনো বাস্তবে দাঁড়ায়নি। GCC বহু বছর ধরে অনেক ভাষা আর অনেক যন্ত্র সমর্থন করেছে, কিন্তু তার ভেতরের IR (GIMPLE, RTL) মূলত GCC-র নিজের ব্যবহারের জন্য, বাইরের প্রকল্পের জন্য একটি স্থির, আলাদা করে ব্যবহারযোগ্য লাইব্রেরি হিসেবে নয়। LLVM শুরু থেকে অন্যভাবে নকশা করা: Chris Lattner আর Vikram Adve University of Illinois-এ মোটামুটি ২০০০ সালে কাজ শুরু করেন, আর লক্ষ্য ছিল একটি IR, যা compile-এর সময়, link-এর সময়, এমনকি চলার সময়ও বিশ্লেষণ করা যায় (২০০৪ সালের CGO প্রবন্ধের শিরোনামে “lifelong program analysis”).
প্রযুক্তিগত কারণ তিনটি। এক, IR-টি পুরোপুরি লেখা যায় আর পড়া যায়: .ll ফাইল একটি স্বাধীন ভাষা, তাই এই পর্বের মতো একটি Python script-ও শুধু text লিখে একটি compiler বানাতে পারে। দুই, type-ওয়ালা SSA, যা optimization-এর জন্য সুবিধাজনক আর verifier দিয়ে যাচাইযোগ্য। তিন, পুরো কাঠামো লাইব্রেরি হিসেবে সাজানো, তাই কেউ শুধু back end নিতে পারে, কেউ শুধু JIT.
প্রযুক্তির বাইরের কারণও বড়। Apple LLVM-এ বড় বিনিয়োগ করে, আর Clang আসে; licence ছিল উদার (মূলত University of Illinois/NCSA ধাঁচের, পরে Apache 2.0-এর সঙ্গে একটি LLVM ব্যতিক্রম), তাই বাণিজ্যিক প্রতিষ্ঠান নিজের পণ্যে নিতে পারে। এরপর ভাষা নির্মাতারা দেখলেন, নিজের back end না লিখেই x86, ARM আর WebAssembly পাওয়া যায়: Rust, Swift, Julia ও আরও অনেকে এই পথে আসে। LLVM ২০১২ সালে ACM Software System Award পায় বলে উল্লেখ আছে। দাম আছে: LLVM-এর optimization সময় নেয়, তাই দ্রুত compile চাওয়া কিছু প্রকল্প (যেমন debug build-এর জন্য) আলাদা, হালকা back end-ও রাখে।
মূল উপলব্ধি: একটি IR সাধারণ মান হয়ে ওঠে যখন সেটি লেখা-পড়া যায়, যাচাই করা যায়, লাইব্রেরি হিসেবে আলাদা নেওয়া যায় আর আইনি দিক থেকে খোলা থাকে; প্রযুক্তি আর পরিবেশ দুটিই লাগে।
প্র ০২LLVM কেন nsw-এর ভাঙা প্রতিশ্রুতিকে সঙ্গে সঙ্গে undefined behavior না বলে “poison” নামে একটি মাঝামাঝি জিনিস রাখে? এতে optimizer কী পায়?
সরাসরি UB বললে একটি সমস্যা হয়: optimizer নির্দেশ সরাতে পারে না। ধরুন একটি if-এর ভেতরে add nsw আছে, আর optimizer সেটি if-এর আগে তুলতে চায় (speculation, পর্ব ৬৬-এর loop-invariant code motion-এর আত্মীয়)। যদি overflow মানেই সঙ্গে সঙ্গে UB হতো, তবে if-এর শর্ত মিথ্যা হলেও তোলা যোগটি চলত আর পুরো program-কে UB বানাত, অথচ মূল program-এ সেটি কখনো চলতই না। Poison সেই সমস্যা মেটায়: overflow হলে শুধু একটি “বিষাক্ত মান” তৈরি হয়, যা ব্যবহার না হলে কোনো ক্ষতি করে না। তাই নির্দেশটি নিরাপদে আগে তোলা যায়, আর আসল UB হয় শুধু তখন, যখন poison কোনো পার্শ্বপ্রতিক্রিয়ায় পৌঁছায়: একটি br-এর শর্ত, একটি memory ঠিকানা, ইত্যাদি।
অন্যদিকে sdiv-এর শূন্য সরাসরি UB, কারণ অনেক যন্ত্রে ভাগ নিজেই trap করে (x86-এ অংশ ৫-এর মতো), তাই সেটিকে “শুধু একটি মান” বলা যায় না; এজন্য optimizer ভাজক শূন্য নয় প্রমাণ না করে sdiv আগে তুলতে পারে না।
ইতিহাসটা জটিল। পুরোনো LLVM-এ undef আর poison দুটি ছিল, আর তাদের নিয়ম মিলে কিছু optimization একসঙ্গে ভুল প্রমাণিত হয়েছিল। Juneyoung Lee, Nuno Lopes, John Regehr ও সহলেখকেরা ২০১৭ সালের PLDI-তে দেখান কোন জোড়া optimization একসঙ্গে অসংগত, আর প্রস্তাব করেন poison-কেন্দ্রিক একটি নিয়ম, সঙ্গে freeze নির্দেশ, যা poison-কে একটি নির্দিষ্ট কিন্তু অজানা মানে “জমিয়ে” দেয়। freeze পরে LLVM-এ আসে (মোটামুটি LLVM 10-এ)। C-এর signed overflow-কে UB রাখার পুরোনো একটি যুক্তিও এখানে মেলে: ৬৪-বিট যন্ত্রে ৩২-বিট int i দিয়ে array-র ঘর গুনলে, overflow নেই ধরে নিলে compiler i-কে আগেই ৬৪ বিটে বাড়িয়ে loop-এ রাখতে পারে।
মূল উপলব্ধি: Poison হলো “ভুল হলে পরে দেখা যাবে” ধরনের একটি নরম UB, যা নির্দেশ সরানোর স্বাধীনতা দেয়; আর এর নিয়ম ঠিক করতে LLVM-এর মতো পরিণত প্রকল্পেও বহু বছর আর আনুষ্ঠানিক যুক্তি লেগেছে।
প্র ০৩Haat wrap চায় আর ভাগে পরীক্ষা চায়; C overflow-কে UB বলে। বাস্তব ভাষাগুলো এই দুইয়ের মাঝে কোথায় দাঁড়ায়, আর তার দাম কে দেয়?
প্রতিটি ভাষার সিদ্ধান্ত আলাদা, আর প্রতিটি অনুবাদে আলাদা LLVM IR আসে। C আর C++ (C17, C++20) signed overflow-কে UB রাখে: compiler nsw দেয়, আর অংশ ৪-এর rounds-এর মতো loop সূত্রে নামে। Java (Java 21-সহ) int আর long-কে wrap করায়, আর পূর্ণসংখ্যায় শূন্য দিয়ে ভাগে ArithmeticException ছোড়ে; Haat-এর নিয়ম প্রায় হুবহু Java-র মতো, পার্থক্য শুধু ভাষার ব্যতিক্রম বনাম program থামানো। Rust-এ ডিফল্ট debug build-এ overflow-এ panic, release build-এ wrap (দুটিই নির্দিষ্ট আচরণ, UB নয়), আর ভাগে শূন্য আর overflow-এর পরীক্ষা সবসময়। Swift-এর সাধারণ + overflow-এ program থামায়; wrap চাইলে আলাদা &+ অপারেটর। Python-এর int-এর কোনো সীমাই নেই (পর্ব ২০)।
দাম দুই রকম। প্রথমটি সরাসরি: পরীক্ষার নির্দেশ। কিন্তু অংশ ৫-এ দেখেছেন, ভাজক জানা বা শর্তে সীমিত হলে -O2 পরীক্ষাগুলো নিজেই মুছে দেয়। দ্বিতীয়টি পরোক্ষ আর বেশি সূক্ষ্ম: হারানো optimization. Haat-এর rounds loop রইল, C-এর loop সূত্র হলো; কারণ wrap-এর জগতে সেই সূত্র সত্যিই ভুল। সময় কতটা বদলায়, তা এই পর্বে মাপা হয়নি; একটি loop-এর ক্ষেত্রে পার্থক্য বিরাট হতে পারে, আবার বেশির ভাগ বাস্তব কোডে নগণ্যও হতে পারে, আর তা জানতে প্রতিটি ক্ষেত্রে মাপতে হয়।
অন্যদিকে UB-র দাম দেয় ব্যবহারকারী: অংশ ৫-এর সরাসরি sdiv -O0-এ program ভেঙেছে, -O2-এ চুপচাপ অর্থহীন সংখ্যা ছেপেছে। নিরাপত্তার জগতে এমন চুপচাপ ভুলই সবচেয়ে বিপজ্জনক (Cybersecurity কোর্সের memory-safety আলোচনা)। তাই অনেক নতুন ভাষা নির্দিষ্ট আচরণ বেছে নেয়, আর দ্রুত পথ চাইলে আলাদা, স্পষ্ট নামের অপারেটর বা function দেয়।
মূল উপলব্ধি: ভাষার semantics ঠিক করে IR-এ কোন প্রতিশ্রুতি দেওয়া যায়; প্রতিশ্রুতি বেশি মানে optimization বেশি, কিন্তু ভুল program-এর আচরণ অনির্দিষ্ট। Haat, Java আর Rust নির্দিষ্টতার পক্ষে, C গতির পক্ষে।
প্র ০৪LLVM IR কি সত্যিই যন্ত্র-নিরপেক্ষ? একটি .ll ফাইল লিখে কি সব যন্ত্রে চালানো যায়?
পুরোপুরি নয়। LLVM IR “প্রায় যন্ত্র-নিরপেক্ষ”: নির্দেশগুলো (add, br, phi) সব যন্ত্রে এক, কিন্তু একটি বাস্তব module-এ যন্ত্রের তথ্য ঢুকে পড়ে। প্রথমত, target triple আর target datalayout: কোন যন্ত্র, কোন operating system, pointer কত বিট, কোন type-এর alignment কত। দ্বিতীয়ত, C থেকে আসা IR-এ type-গুলোই যন্ত্রভেদে আলাদা: Linux-এর x86-64-এ C-এর long ৬৪ বিট, কিন্তু Windows-এ ৩২ বিট (LLP64 মডেল)। এই পর্বের lab-এই এটি চোখে পড়েছে: long দিয়ে লেখা C ফাইল IR দেখানোর জন্য --target=x86_64-linux-gnu দিয়ে compile করা হয়েছে, আর Windows-এ চালানোর জন্য long long লাগল। তৃতীয়ত, calling convention আর struct পাঠানোর নিয়ম (পর্ব ৩০, বিস্তার পর্ব ৭১-এ): Clang C-এর একটি struct argument-কে যন্ত্রভেদে আলাদা IR-এ নামায়, কারণ ABI আলাদা।
আমাদের Haat-এর অনুবাদ এই দিক থেকে ভাগ্যবান: আমরা কোথাও C-এর long ব্যবহার করি না, সব i64; কোনো struct যন্ত্রের নিয়মে পাঠাই না; আর triple লিখিনি, তাই Clang নিজের যন্ত্রের triple বসায়। একই .ll অন্য যন্ত্রের জন্য compile করা সম্ভব হওয়া উচিত, কিন্তু এই পর্বে শুধু x86-64 Windows-এ চালানো হয়েছে, তাই অন্য যন্ত্রের দাবি যাচাই করা হয়নি।
যন্ত্র-নিরপেক্ষ bitcode-এর চেষ্টা হয়েছে। Google-এর PNaCl (Portable Native Client) LLVM bitcode-এর একটি স্থির উপসেট ব্রাউজারে পাঠাত, পরে প্রকল্পটি বন্ধ হয়, আর তার জায়গা নেয় WebAssembly (২০১৭), যা শুরু থেকেই একটি নির্দিষ্ট, স্থির, যন্ত্র-নিরপেক্ষ নির্দেশমালা হিসেবে নকশা করা। LLVM IR-এর নিজের পরিবর্তনও দ্রুত: typed pointer থেকে opaque ptr-এ যাওয়া কয়েক version ধরে হয়েছে (মোটামুটি LLVM 15 থেকে 17), তাই পুরোনো .ll নতুন LLVM-এ না-ও চলতে পারে।
মূল উপলব্ধি: LLVM IR একটি compiler-এর ভেতরের ভাষা, বিতরণের ভাষা নয়; যন্ত্র-নিরপেক্ষ বিতরণের জন্য WebAssembly বা JVM bytecode-এর মতো স্থির নির্দেশমালা লাগে (পর্ব ৭৩)।
প্র ০৫এই পর্বে ৩,০০০টি program দুই opt স্তরে মিলেছে। এতে কি প্রমাণ হলো অনুবাদক ঠিক? Compiler-এর সঠিকতা আর কোন কোন পথে যাচাই হয়?
না, প্রমাণ হয়নি; আত্মবিশ্বাস বেড়েছে। Test শুধু সেই program-গুলোর কথা বলে, যা চালানো হয়েছে। এই পর্বেই এর উদাহরণ আছে: ৩,০০০টি এলোমেলো program-এর কোনোটি ১,০০০-call সীমা ছোঁয় না, তাই অনুবাদকের সেই ফাঁক ধরা পড়েনি; আর haat_gen.py Str বা closure বানায় না। অনুশীলন ২-এর add nsw-ওয়ালা অনুবাদ সবচেয়ে বড় Int-এর কিনারায়ও একবার ঠিক উত্তর দিয়েছে। Edsger Dijkstra-র বহুল উদ্ধৃত কথা: test ভুলের উপস্থিতি দেখাতে পারে, অনুপস্থিতি নয়।
বাস্তব compiler-এর জগতে কয়েকটি পথ পাশাপাশি চলে। এক, এলোমেলো program দিয়ে differential testing: Xuejun Yang, John Regehr ও সহকর্মীদের Csmith (PLDI ২০১১) এলোমেলো, UB-মুক্ত C program বানিয়ে GCC আর Clang-এ শত শত ভুল খুঁজে পেয়েছিল বলে প্রবন্ধে জানানো হয়। এর কঠিন অংশ ঠিক আমাদের haat_gen.py-এর মতো: program যেন বৈধ হয়, নইলে দুই compiler-এর ভিন্ন ফল কিছুই প্রমাণ করে না; C-তে এর মানে UB এড়ানো। দুই, translation validation: প্রতিবার অনুবাদের পরে আগের আর পরের রূপ সমতুল্য কি না যাচাই, যেমন LLVM-এর জন্য Alive2. তিন, পুরো compiler-এর গাণিতিক প্রমাণ: Xavier Leroy-র CompCert, যার C থেকে assembly পর্যন্ত অনুবাদের সঠিকতা Coq-এ প্রমাণিত (পর্ব ৪৪)।
আমাদের ক্ষেত্রে কোন যুক্তি বাকি? প্রতিটি নির্দেশের অনুবাদ ছোট, আর অনুশীলন ৪-এর মতো প্রতিটির জন্য হাতে একটি প্রমাণ লেখা যায়: add মানে modulo-যোগ, @haat.div মানে c_div. বাকি থাকে বিন্যাস: φ-এর জোড়া, নাম, type অনুমান; সেগুলো verifier আর differential test মিলে ভালোভাবে ধরে।
মূল উপলব্ধি: Compiler-এর আস্থা আসে কয়েক স্তর থেকে: ছোট টুকরোর প্রমাণ, গঠনের যাচাই (verifier), আর বৈধ program দিয়ে বিশাল differential test; একটি দিয়ে অন্যটির কাজ হয় না।
অনুশীলন
প্রথমে নিজে হিসাব করুন বা লিখুন, তারপর উত্তর খুলুন। প্রতিটি উত্তর সত্যিকারের run দিয়ে যাচাই করা।
-
নকশা ও বাস্তবায়ন — ১,০০০-call সীমা: Reference ১,০০০টির বেশি গভীর call-এ থামে:
<line>:<col>: runtime error: stack overflow, অবস্থান callee-র শুরুতে (সিদ্ধান্ত ২৪, ২৬)। এই পর্বের অনুবাদকে এটি নেই। নিচের program-এ reference ছাপে999, তারপর3:16: runtime error: stack overflow; এই পর্বের অনুবাদ কী ছাপে? তারপর অনুবাদকে সীমাটি যোগ করুন,ins_llvmনা ভেঙে।fn down(n: Int) -> Int { if n == 0 { return 0; } return 1 + down(n - 1); } print(down(999)); print(down(1000));এখনকার অনুবাদ (সত্যিকারের Clang run,
-O0আর-O2):999আর1000; সীমা নেই, আর native stack ১,০০০ গভীরতায় ভরে না। সমাধান: একটি global গণক, আর প্রতিটিcall-এর আগে-পরে দুটি সহায়ক function. Reference-এ গণনা শুরু<main>-এর frame দিয়ে (১), আর নতুন frame বসানোর আগে পরীক্ষাlen(stack) > 1000:@haat.depth = internal global i64 1 define internal void @haat.enter(i64 %line, i64 %col) { entry: %d = load i64, ptr @haat.depth %over = icmp sgt i64 %d, 1000 ; reference: len(stack) > MAX_CALL_DEPTH br i1 %over, label %fail, label %ok fail: call i32 (ptr, ...) @printf(ptr @.so, i64 %line, i64 %col) call void @exit(i32 1) unreachable ok: %d1 = add i64 %d, 1 store i64 %d1, ptr @haat.depth ret void } ; @haat.leave: depth থেকে ১ বাদ; @.so = "%lld:%lld: runtime error: stack overflow\n" old_ins = ins_llvm # Python: পুরোনো অনুবাদ মুড়ে নেওয়া def ins_llvm(i, v, T, sig, main): out = old_ins(i, v, T, sig, main) if i.kind != "call": return out pos = f"i64 {i.pos[0]}, i64 {i.pos[1]}" return [f"call void @haat.enter({pos})"] + out + ["call void @haat.leave()"]down-এর B2 তখন হয়call void @haat.enter(i64 3, i64 16),%t7 = call i64 @down(i64 %t6),call void @haat.leave(). লেখকের lab-এ সত্যিকারের run:-O0আর-O2দুটিতেই999আর3:16: runtime error: stack overflow, reference-এর হুবহু;recursion,mutualআরbazarউদাহরণও আগের মতো মিলেছে।-O2recursion-কে যেভাবেই বদলাক, গণকেরload/storeদেখা যায় এমন পার্শ্বপ্রতিক্রিয়া, তাই সীমা টিকে থাকে। -
ভুল খুঁজুন: একজন সহকর্মী নিচের Haat function-এর LLVM IR হাতে লিখেছেন। তিনটি সন্দেহজনক জায়গা খুঁজুন: কোনটি সত্যিই ভুল, কোনটি verifier ধরবে, আর কোনটি আসলে নিরাপদ?
fn avg(sum: Int, n: Int) -> Int { var r = 0; if n > 0 { r = sum / n; } return r + 1; } define i64 @avg(i64 %sum, i64 %n) { B0: %t2 = icmp sgt i64 %n, 0 br i1 %t2, label %B1, label %B2 B1: %"r#2" = sdiv i64 %sum, %n br label %B2 B2: %"r#3" = phi i64 [ %"r#2", %B1 ] %t4 = add nsw i64 %"r#3", 1 ret i64 %t4 }১. φ-তে B0-এর জোড়া নেই (ভুল, verifier ধরে)। B2-এর দুই predecessor, B0 আর B1; B0 থেকে এলে
r= ০. ঠিক:phi i64 [ 0, %B0 ], [ %"r#2", %B1 ]. Clang 22.1.8-এর সত্যিকারের বার্তা:PHINode should have one entry for each predecessor of its parent basic block!২.
add nsw(ভুল, verifier চুপ)।avg(9223372036854775807, 1)-এ r + ১ overflow করে; Haat চায় wrap. লেখকের lab-এ φ ঠিক করে এই অনুবাদ চালানো হলো: এই বিশেষ input-এ-O2-এও ফল ঠিক এল (-9223372036854775808), কারণ এখানে optimizer প্রতিশ্রুতিটি কাজে লাগানোর সুযোগ পায়নি। ভুলটি তবু ভুল: অংশ ৪-এরbigger-এ একই পতাকা ভুল উত্তর দিয়েছে। UB মানে “কখনো ভুল”, “সবসময় ভুল” নয়; তাই একটি test পাস করা যথেষ্ট নয়।৩. পরীক্ষা ছাড়া
sdiv(এখানে নিরাপদ)। ভাগটি শুধুn > 0হলে চলে, তাই ভাজক শূন্যও নয়, −১-ও নয়। আমাদের অনুবাদক এই বিশ্লেষণ করে না, সবসময়@haat.divডাকে; কিন্তু Clang-O2-এ inline করার পরে নিজেই একই সিদ্ধান্তে আসে (সত্যিকারের আউটপুট):%q.i = sdiv i64 %sum, %n, কোনো পরীক্ষা ছাড়া, আর φ হয়[ 1, %B0 ], [ %0, %B1 ]. আমাদের অনুবাদ তিনটি input-এই (avg(10, 3),avg(10, 0), সবচেয়ে বড় Int) দুই স্তরে reference-এর মতো4,1,-9223372036854775808দিয়েছে। -
হিসাব ও অনুমান — wrap-এর loop: অংশ ৪-এর
roundsনিন। (ক) Haat-এrounds(5000)কত? (খ) Haat-এrounds(9223372036854775807)কী করবে? যুক্তি দিন। (গ) একই loop-এর C রূপ (long long) Clang-O2-এ ওই সবচেয়ে বড় মানে কী ছাপে, অংশ ৪-এর সূত্র থেকে হিসাব করুন। কোনটি “ঠিক”?(ক) total ০ → ১২৫০ → ২৫০০ → ৩৭৫০ → ৫০০০: চারবার যোগ, তাই
4. Haat-এর অনুবাদ আর C দুটিই সত্যিকারের run-এ4দিয়েছে।(খ) কখনো শেষ হয় না। Loop থামে শুধু total ≥ 9223372036854775807 হলে, অর্থাৎ total = 9223372036854775807 হলে (এর বড় কোনো Int নেই)। Wrap-এর জগতে total সবসময় ১২৫০ × k-কে 264-এর modulo-তে নেওয়া মান। ১২৫০ জোড়, 264-ও জোড়, তাই এমন যেকোনো মান জোড়; কিন্তু 9223372036854775807 বিজোড়। তাই শর্ত কখনো মিথ্যা হয় না: অসীম loop. (এটি যুক্তি দিয়ে পাওয়া; program-টি চালানো হয়নি, কারণ থামত না।)
(গ) সূত্র: (9223372036854775807 − 1) / 1250 + 1 = 7378697629483820 + 1 =
7378697629483821. লেখকের lab-এ সত্যিকারের run (Clang 22.1.8,-O2, Windows): ঠিক এই সংখ্যা, সঙ্গে সঙ্গে। কোনটি ঠিক? C-এ loop চলতে চলতে signed overflow হতো, যা UB, তাই C-এর মানদণ্ড কোনো ফল দাবি করে না; compiler যেকোনো কিছু করতে পারত, আর এটি একটি সূত্রের উত্তর বেছে নিয়েছে। Haat-এর semantics-এ অসীম loop-ই একমাত্র সঠিক আচরণ, আর আমাদের অনুবাদ-O2-এও loop রাখে, তাই সেটি মানে। -
প্রমাণ — অনুবাদ অর্থ রাখে: ধরুন a, b ৬৪-বিট signed পূর্ণসংখ্যা, আর wrap(x) = x-কে [−263, 263)-এ আনা 264-এর modulo-মান। প্রমাণ করুন: (ক) পতাকাহীন
add i64-এর ফল wrap(a + b); (খ) b ≠ 0 হলে@haat.div-এর ফল reference-এরc_div-এর সমান; (গ) b = 0 হলে দুটিই একই error দেয়।- (ক) LangRef অনুযায়ী পতাকাহীন
add-এর ফল দুই operand-এর যোগফল 264-এর modulo-তে, আরi64-এর বিট-রূপকে two's complement-এ পড়লে মানটি [−263, 263)-এর সেই একমাত্র সংখ্যা, যা a + b-এর সঙ্গে 264-এর modulo-তে সমান।wrap-এর সংজ্ঞাও ঠিক এটি।sub,mulআরsub i64 0, a(একক minus)-এর যুক্তি একই। - (খ), b = −১:
@haat.divনেয়negপথ, ফল wrap(0 − a) = wrap(−a).c_div: q = |a| ÷ 1 = |a|; চিহ্ন আলাদা হলে −q, নইলে q; a > 0 হলে চিহ্ন আলাদা, ফল −a; a < 0 হলে চিহ্ন এক, ফল |a| = −a; a = 0 হলে ০. তিন ক্ষেত্রেই wrap(−a). a = INT_MIN হলে wrap(263) = INT_MIN, সিদ্ধান্ত ১৩-এর মতো। - (খ), b ∉ {0, −1}: পথ
div,sdiv. এর overflow হয় শুধু INT_MIN / −১-এ, যা বাদ; তাই ফল সংজ্ঞায়িত, আর LangRef অনুযায়ী শূন্যের দিকে কাটা ভাগফল। গাণিতিক ভাগফল a / b-এর পরম মান ≤ |a| ≤ 263, আর 263 সম্ভব শুধু a = INT_MIN, |b| = ১ হলে; b = ১-এ ফল INT_MIN নিজেই, যাi64-এ ধরে।c_div-ও শূন্যের দিকে কাটে: |a| ÷ |b|-এর পূর্ণ অংশ, চিহ্ন মিলিয়ে। একই সংখ্যা, আর wrap সেখানে কিছু বদলায় না। - (গ) b = 0 হলে
@haat.divfail-এ যায়, কোনো ভাগ হয় না, আর লেখেline:col: runtime error: division by zero; reference-এরc_divএকই অবস্থানে একই বার্তারHaatErrorতোলে। আগের ছাপা লাইন দুই দিকেই থাকে (exitC library-র buffer লিখে দেয়)।@haat.rem-এর যুক্তি একই, b = −১-এ ফল ০ (c_mod: a − (−১)(−a) = ০)। ∎
প্রমাণের পাশে পরীক্ষাও: লেখকের lab-এ ৩,০০০টি এলোমেলো program-এ
@haat.div/@haat.rem-এর ২৭,৩৫৫টি call, আর অংশ ৫-এরshare, দুই opt স্তরেই reference-এর হুবহু। - (ক) LangRef অনুযায়ী পতাকাহীন
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি Haat program-কে LLVM দিয়ে চালানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Lexer আর parser দিয়ে AST, আর type checker-এর যাচাই
- Haat IR-এ lowering আর basic block দিয়ে CFG
- Dominator, φ বসানো আর নাম বদলে SSA রূপ
- Type অনুমান আর LLVM IR text লেখা (
.ll) - Clang: verifier, তারপর
-O2-এর pass pipeline - Machine code, link, চালানো আর reference-এর আউটপুটের সঙ্গে মেলানো
LLVM IR-এ %y = add nsw i64 %x, 1, আর চলার সময় %x = 9223372036854775807. %y কী?
- −9223372036854775808
- 9223372036854775808
- একটি poison value
- Program সঙ্গে সঙ্গে exception দিয়ে থামে
Haat-এর a / b-কে সরাসরি sdiv i64 %a, %b-এ অনুবাদ করলে কোন অবস্থায় Haat-এর অর্থ ভাঙে?
- শুধু b = 0 হলে
- b = 0 হলে, আর a = INT_MIN ও b = −1 হলে
- a বা b ঋণাত্মক হলে
- কখনো না, sdiv আর Haat-এর / একই
SSA-র নাম n#2-কে LLVM IR-এ %"n#2" লেখা হয় কেন, %n.2 নয়?
- উদ্ধৃতি ছাড়া নাম ৪ অক্ষরের বেশি হতে পারে না
- LLVM-এ নামে বিন্দু চলে না
- উদ্ধৃতি দিলে optimizer নামটি বদলাতে পারে না
- # উদ্ধৃতি ছাড়া অবৈধ, আর n.2 shadowing-এর একটি আলাদা Haat নাম হতে পারে
Block B2-এর শুরুতে %r = phi i64 [ 0, %B0 ], [ %q, %B1 ]. চলার সময় B1 থেকে B2-তে আসা হলো, আর তখন %q = 7. %r কত?
- 7
- 0
- 7 + 0 = 7, কারণ phi দুটি মান যোগ করে
- অনির্দিষ্ট
Clang -O0-এ C-এর local variable-কে কীভাবে রাখে, আর পরে কোন pass সেগুলোকে SSA নামে তোলে?
- শুরু থেকেই phi দিয়ে; কোনো pass লাগে না
- Register-এ রাখে; register allocator SSA বানায়
- alloca, load আর store দিয়ে; পরে SROA বা mem2reg
- Global variable হিসেবে; linker SSA বানায়
C-তে int bigger(long x) { return x + 1 > x; }. Clang -O2 এটিকে ret i32 1 বানায়, কিন্তু -fwrapv দিলে icmp ne i64 %x, 9223372036854775807. কেন?
- দুটি একই অর্থ, শুধু লেখা আলাদা
- ছাড়া হলে overflow UB, তাই nsw; -fwrapv-এ wrap, তাই সবচেয়ে বড় x-এ মিথ্যা
- -fwrapv সব optimization বন্ধ করে
- এটি Clang-এর একটি bug
নিচের কোন ভুল LLVM-এর verifier (বা parser) compile-এর সময় ধরে?
- Haat-এর অনুবাদে add-এর জায়গায় add nsw
- শূন্যের পরীক্ষা ছাড়া sdiv
- Error বার্তায় ভুল line:col
- একটি phi-তে একটি predecessor-এর জোড়া নেই
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- গঠন: module → global, declare, define → basic block → নির্দেশ; প্রতিটি block-এর শেষে terminator, প্রতিটি operand-এর type, প্রতিটি
%নামএকবার। - অনুবাদ: SSA রূপের Haat IR থেকে লাইন ধরে; type অনুমান,
constআর copy-র জায়গায় সরাসরি মান,%"x#1", আর দরকারে আলাদা entry block. - পতাকা:
nsw/nuwপ্রতিশ্রুতি, ভাঙলে poison; Haat wrap করে, তাই সাধারণadd; ভুল পতাকা শুধু-O2-এ ধরা পড়তে পারে। - ভাগ:
sdiv/sremশূন্য আর INT_MIN / −১-এ UB; অনুবাদ পরীক্ষা বসায়, আর ভাজক জানা হলে-O2সেই পরীক্ষা নিজেই মুছে দেয়। - যাচাই: verifier গঠন দেখে, অর্থ নয়; Clang 22-এ ৮টি উদাহরণ আর ৩,০০০টি program দুই opt স্তরে হুবহু, আর যা test ছোঁয় না (১,০০০-call সীমা) তা আলাদা করে।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৬৯ · Instruction selection — tree pattern matching আর tilingপরবর্তী পর্বIR থেকে যন্ত্রের নির্দেশ: code generation-এর প্রথম ধাপ।
- পর্ব ৬৩ · SSA formএই মডিউলেএই পর্বের অনুবাদকের input: φ, dominator আর নাম বদল।
- পর্ব ৬২ · Intermediate representationএই মডিউলেHaat IR, CFG, IR interpreter আর Clang-এর প্রথম LLVM IR.
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- C toolchain — preprocess, compile, assemble, linkপাশের ট্র্যাকC-এর দিক থেকে Clang আর GCC-র পুরো পথ।
- C থেকে assemblyপাশের ট্র্যাকIR-এর পরের ধাপ: যন্ত্রের নির্দেশ আর register.