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

Instruction selection — tree pattern matching আর tiling

Instruction Selection — Tree Pattern Matching and Tiling

Taught in Bangla, this lesson turns Haat IR into expression trees and covers them with RISC-V instruction tiles, including 12-bit immediates and li for larger constants. It implements maximal munch and dynamic-programming optimal tiling, compares their costs, and inserts explicit zero-divisor checks because RISC-V division does not trap. Selections are assembled with real Clang and run in the Unicorn emulator for differential testing, and it relates the approach to LLVM's SelectionDAG and GlobalISel.

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

  • Haat IR-এর basic block থেকে নিরাপদে expression tree বানানো, আর কোন temp গাছে ঢোকে না
  • RISC-V (RV64IM)-এর নির্দেশকে tile হিসেবে দেখা: pattern, শর্ত, খরচ, আর ১২ বিটের immediate বনাম li
  • Maximal munch আর dynamic programming দিয়ে tiling, optimality-র প্রমাণের রূপরেখা, আর কোথায় munch হারে
  • Haat-এর wrap আর C-ধাঁচের ভাগ RISC-V-তে কীভাবে মেলে, আর শূন্য দিয়ে ভাগের পরীক্ষা কেন back end-এর দায়িত্ব
  • সত্যিকারের assembler আর emulator-এ differential test, আর Clang-এর SelectionDAG ও GlobalISel-এর আসল আউটপুটের সঙ্গে তুলনা

১ · Instruction selection — IR থেকে যন্ত্রের নির্দেশ

বাজারের ফর্দ হাতে মুদি দোকানে গেছেন: চাল ৫ কেজি, ডাল ১ কেজি, তেল ১ লিটার। দোকানে আলগা জিনিসও আছে, আবার কিছু “প্যাক”-ও আছে: চাল-ডালের একটি কম্বো, তেলের একটি বোতল। পুরো ফর্দটি কয়েকটি প্যাক আর আলগা জিনিস দিয়ে এমনভাবে মেটাতে হবে যাতে প্রতিটি জিনিস ঠিক একবার আসে, আর মোট দাম সবচেয়ে কম হয়। Compiler-এর instruction selection ঠিক এই কাজ: ফর্দ হলো IR-এর হিসাব, প্যাক হলো যন্ত্রের একেকটি নির্দেশ, আর দাম হলো নির্দেশের খরচ।

পর্ব ০৫-এ compiler-এর তিন অংশ দেখেছেন। মডিউল ১১-এর Haat IR ছিল middle end-এর ভাষা; এই মডিউল back end: IR থেকে সত্যিকারের যন্ত্রের কোড। Back end-এর কাজ সাধারণত তিন ধাপে ভাগ হয়, আর এই মডিউলের পর্বগুলোও সেভাবে সাজানো:

  1. Instruction selection (এই পর্ব): কোন হিসাব কোন নির্দেশে। এখানে ধরে নেওয়া হয় register অসীম, বা অন্তত প্রতিটি নামের জন্য একটি register কেউ ঠিক করে দেবে।
  2. Register allocation (পর্ব ৭০): অসীম নামকে যন্ত্রের সীমিত register-এ বসানো, না ধরলে memory-তে রাখা।
  3. Frame আর calling convention (পর্ব ৭১), তারপর সম্পূর্ণ back end (পর্ব ৭২): function-এর শুরু-শেষ, argument কোথায়, call কীভাবে।

লক্ষ্য-যন্ত্র RISC-V-এর ৬৪-বিটের মূল অংশ RV64I আর গুণ-ভাগের M extension, একসঙ্গে RV64IM. RISC-V-এর নির্দেশ, তাদের encoding আর addressing mode-এর বিস্তারিত Computer Architecture কোর্সে আছে (পর্ব ২৬, পর্ব ২৭, পর্ব ২৮); C থেকে assembly কেমন হয়, তা সেখানের পর্ব ৩১-এ। এখানে প্রশ্ন অন্য: compiler নিজে কীভাবে বাছাই করে, আর বাছাইটি যে ঠিক আর সস্তা, তা কীভাবে জানা যায়।

প্রশ্নটি সহজ মনে হতে পারে: + মানে add, ব্যস। কিন্তু p + 1000-এর জন্য একটি নির্দেশই যথেষ্ট (addi), p + 2048-এর জন্য তিনটি লাগে; p * 8 একটি shift; p / 10 একটি div, অথবা গুণ আর shift-এর পাঁচটি নির্দেশ, যা অনেক যন্ত্রে বেশি দ্রুত; আর if p >= 1000-এর তুলনা আর লাফ মিলে একটি blt. কোনটি “সেরা”, তা নির্ভর করে খরচ কীভাবে মাপছেন তার ওপর। চলমান উদাহরণ bazar.haat-এর price:

fn price(qty: Int, unit: Int) -> Int {
    let p = qty * unit;
    if p >= 1000 { return p - p / 10; }
    return p;
}

২ · Haat IR থেকে expression tree

Haat IR-এ প্রতিটি নির্দেশ একটি ছোট হিসাব, আর মাঝের ফল যায় temp-এ। পর্ব ৬২-এর haat_ir.py দিয়ে price-এর CFG (এই পাতার Python ব্লকগুলো সেই ফাইল হুবহু, অপরিবর্তিত ব্যবহার করে):

fn price(qty, unit):
B0:
  p = qty * unit
  t1 = const 1000
  t2 = p >= t1
  branch t2 B1 B2
B1:
  t3 = const 10
  t4 = p / t3
  t5 = p - t4
  return t5
B2:
  return p

Tile বসানোর জন্য দরকার একটি expression tree: t5 = p - t4 আর t4 = p / t3 আর t3 = const 10 মিলে একটি গাছ (- p (/ p 10)). কারণ একটি নির্দেশ প্রায়ই কয়েকটি IR নির্দেশের কাজ একসঙ্গে করে: addi একটি যোগ আর একটি ধ্রুবক দুটোই খায়। তাই প্রথম কাজ temp-গুলোকে তাদের ব্যবহারের জায়গায় “ভাঁজ করে” ঢোকানো। কিন্তু সব temp ঢোকানো নিরাপদ নয়। এই পর্বের block_trees একটি temp-কে গাছে ঢোকায় শুধু চারটি শর্তে:

নিয়ম ৬৯.১ — কোন temp গাছে ঢোকে

(১) temp-টি const, copy, binary বা unary নির্দেশে তৈরি (call নয়); (২) পুরো function-এ একবারই লেখা হয়; (৩) একবারই পড়া হয়; (৪) পড়া হয় একই basic block-এ। আর পুরো দলটি ভাঁজ হয় তখনই, যখন গাছের post-order ক্রম আর IR-এর ক্রম হুবহু এক; না মিললে কিছুই ভাঁজ হয় না, প্রতিটি নির্দেশ আলাদা থাকে।

প্রতিটি শর্তের কারণ আছে। দুবার পড়া temp গাছে ঢোকালে হিসাবটি দুবার হতো; তখন কাঠামোটি আসলে একটি DAG, আর সেই temp নিজেই একটি নামওয়ালা মূল হয়। দুবার লেখা temp হলো &&/||-এর ফল (পর্ব ৬২)। Call ভাঁজ হয় না, কারণ তার ভেতরের print সরালে আউটপুটের ক্রম বদলায়। আর ক্রমের শর্তটি এজন্য যে Haat-এ শূন্য দিয়ে ভাগ line:col-সহ একটি runtime error (সিদ্ধান্ত ২৬), আর হিসাব বাঁ থেকে ডানে (সিদ্ধান্ত ১২): দুটি ভাগের ক্রম উল্টালে ভুল অবস্থানের error ছাপা হতে পারত। Haat-এর lowering post-order-এ লেখে, তাই বাস্তবে প্রায় সবকিছুই ভাঁজ হয়।

price-এর ফল চারটি statement, প্রতিটিতে একটি গাছ:

B0: set    p (* qty unit)
B0: branch (>= p 1000) B1 B2
B1: return (- p (/ p 10))
B2: return p

নিয়মটি ঠিক কি না, তা চালিয়ে দেখা হয়েছে: লেখকের ল্যাবে পর্ব ৬২-এর haat_gen.py-র ৩,০০০টি এলোমেলো program-এর প্রতিটি block গাছে ভেঙে আবার post-order-এ Haat IR-এ ফেরানো হয়েছে, আর পর্ব ৬২-এর run_ir দিয়ে চালানো হয়েছে: ৩,০০০টির ৩,০০০টিতেই আউটপুট আসলের সঙ্গে হুবহু এক (প্রথম ২০০টি reference-এর digest-এর সঙ্গেও মিলিয়ে)। এতে ৬৭,৩৮৮টি set, ২৪,৩৩৯টি branch আর ১৬,৮২২টি call statement ছিল।

৩ · RISC-V-এর tile — pattern, শর্ত আর খরচ

একটি tile তিনটি জিনিস: গাছের একটি নকশা (pattern), একটি শর্ত, আর যে নির্দেশগুলো লেখা হবে। Pattern-এ a আর b মানে “যেকোনো উপ-গাছ, যার মান আগে কোনো register-এ আনা হবে”, আর # মানে “একটি ধ্রুবক k”, যা নির্দেশের ভেতরেই বসবে। গাছে নকশা খুঁজে বসানোকে বলে tree pattern matching. haat_isel.py-র tile-তালিকার একটি অংশ:

নামPatternশর্তনির্দেশ
add(+ a b)—add d, a, b
addi(+ a #)k ১২ বিটে ধরেaddi d, a, k
subi(- a #)−k ১২ বিটে ধরেaddi d, a, -k
slli(* a #)k = 2jslli d, a, j
div(/ a b)—beqz b, err; div d, a, b
divk(/ a #)k ≠ 0li x, k; div d, a, x
divm(/ a #)k ≥ 3, 2-এর ঘাত নয়“magic” গুণ: li, mulh, srai, srli, add
sgt(> a b)—slt d, b, a
sgti(> a #)k + 1 ১২ বিটে ধরেslti d, a, k+1; xori d, d, 1
sle(<= a b)—slt d, b, a; xori d, d, 1
seq(== a b)—xor d, a, b; seqz d, d
notle(! (<= a b))—slt d, b, a
branch(>= a b) শাখায়—bge a, b, L (তুলনা আর লাফ এক নির্দেশে)

তালিকাটি পড়ার মতো কয়েকটি জিনিস। RISC-V-এ sgt, sle, sge নামের কোনো নির্দেশ নেই, আছে শুধু slt (set if less than) আর slti; বাকিগুলো operand উল্টে বা ফল উল্টে (xori d, d, 1) বানাতে হয়। ফল উল্টানো চলে কারণ Haat-এর Bool যন্ত্রে সবসময় 0 বা 1. seqz, snez, neg, mv, li আসলে pseudo-instruction: assembler এদের এক বা একাধিক আসল নির্দেশে বদলায়, যেমন neg d, a আসলে sub d, zero, a. আর zero (x0) একটি zero register: ধ্রুবক 0 লাগলে কোনো নির্দেশই লাগে না।

খরচ। প্রতিটি tile-এর খরচ তার নির্দেশগুলো থেকে হিসাব হয়, একটি cost model অনুযায়ী। এই পর্বে দুটি: INSN, প্রতিটি আসল নির্দেশের খরচ 1; আর LATENCY, LLVM-এর সোর্সের SiFive7 scheduling model থেকে (RISCVSchedSiFive7.td, main শাখা, এই পর্ব লেখার সময় পড়া): সাধারণ নির্দেশ ৩ cycle, ৬৪-বিট গুণ ৩, ভাগ বা ভাগশেষ ৬৬. এগুলো একটি CPU পরিবারের জন্য LLVM-এর অনুমান, মাপা সময় নয়; আর latency যোগ করা সময়ের মোটা হিসাব মাত্র।

১২ বিটের immediate আর li

RISC-V-এর I-type নির্দেশে ধ্রুবকের জন্য ১২টি বিট, sign-সহ: −2048 থেকে 2047 (encoding: Computer Architecture পর্ব ২৭)। এর বাইরের ধ্রুবক আগে একটি register-এ আনতে হয়, li (load immediate) দিয়ে। li একটি pseudo-instruction; assembler সংখ্যা দেখে lui, addi, slli ইত্যাদির একটি ক্রম বানায়। লেখকের ল্যাবে Clang 22.1.8-এর assembler দিয়ে বানিয়ে Capstone disassembler-এ পড়া (সত্যিকারের run):

li a0, 10                   -> addi a0, zero, 0xa
li a0, 2048                 -> addi a0, zero, 1; slli a0, a0, 0xb
li a0, -2049                -> lui a0, 0xfffff; addi a0, a0, 0x7ff
li a0, 9223372036854775807  -> addi a0, zero, -1; srli a0, a0, 1
li a0, 7378697629483820647  -> lui a0, 0x3333; addi a0, a0, 0x333; slli a0, a0, 0xc;
                               addi a0, a0, 0x333; slli a0, a0, 0xc;
                               addi a0, a0, 0x333; slli a0, a0, 0xd; addi a0, a0, 0x667

খরচ হিসাবের জন্য haat_isel.py-র li_seq(k) এই সংখ্যাটি অনুমান করে, LLVM-এর RISCVMatInt-এর মূল ধারণা নিয়ে। সত্যিকারের assembler-এর সঙ্গে ৪,২২৬টি ধ্রুবকে মিলিয়ে দেখা হয়েছে: ৩,৫১৪টিতে হুবহু এক, বাকি ৭১২টিতে li_seq একটি নির্দেশ বেশি বলে, কম কখনো নয়; আর চালিয়ে দেখা প্রতিটি li-এর মান ঠিক। খরচের হিসাব তাই কখনো কখনো একটু রক্ষণশীল, কিন্তু কোড ভুল হয় না, কারণ li-এর আসল বিস্তার assembler নিজেই করে।

1p + 10002p + 20473p + 20484p - 20485p + 92233720368547758076if p >= 1000 …
বাছাই (munch, p = a2)
tile
assembly
আসল নির্দেশ
  1. ছোট ধ্রুবক। 1000 ১২ বিটের সীমার ভেতরে, তাই addi tile যোগ আর ধ্রুবক দুটোই একসঙ্গে ঢাকে: একটি নির্দেশ।
  2. সীমার শেষ। 2047 = 211 − 1, ১২ বিটের সবচেয়ে বড় ধনাত্মক সংখ্যা। এখনো একটি নির্দেশ।
  3. এক বেশি হলেই। 2048 ধরে না, তাই addi-এর শর্ত মিথ্যা; বাকি থাকে সাধারণ add, আর ধ্রুবকটি আলাদা li-তে, যা assembler-এ দুটি নির্দেশ (addi আর slli). মোট তিন। Clang -O2 এখানে addi 2047 আর addi 1 লেখে, দুটি নির্দেশ; সেটি tiling নয়, গাছটিকেই বদলে লেখা।
  4. অসমতা। p - 2048-কে subi tile লেখে addi a0, a2, -2048, কারণ −2048 ১২ বিটে ধরে। যোগে 2048 ধরে না, বিয়োগে ধরে: two's complement-এর সীমা একদিকে একটি বেশি।
  5. খুব বড় ধ্রুবক। Int-এর সর্বোচ্চ মান: li দুটি নির্দেশে বানায়, সব বিট ১ করে একবার ডানে সরিয়ে। এলোমেলো ৬৪-বিট ধ্রুবকে li আটটি পর্যন্ত নির্দেশ নিতে পারে।
  6. শাখায় তুলনা। RISC-V-এর branch দুটি register তুলনা করে; ধ্রুবকের জায়গা নেই। তাই p >= 1000-এ আগে li t0, 1000, তারপর একটি তুলনা-লাফ। শর্ত মিথ্যা হলে B2-তে যেতে হয়, আর সত্য হলে ঠিক পরের block B1-এ গড়িয়ে পড়ে, তাই bge-এর উল্টো blt লেখা হয়। ধ্রুবকটি 0 হলে zero register-ই যথেষ্ট, li লাগত না।

৪ · Haat-এর অর্থ রক্ষা — wrap, ভাগ আর শূন্যের পরীক্ষা

একটি tile সস্তা হলেই চলবে না, তাকে Haat-এর অর্থ হুবহু রাখতে হবে। প্রতিটি tile-এর জন্য প্রশ্ন: সব ৬৪-বিট মানে কি নির্দেশটির ফল Haat-এর ফলের সমান?

  • যোগ, বিয়োগ, গুণ। RISC-V-এর add, sub, mul ফলের নিচের ৬৪ বিট রাখে, অর্থাৎ 264 দিয়ে ভাগশেষ: ঠিক Haat-এর wrapping arithmetic (সিদ্ধান্ত ১৩)। তাই x * 8-এর জায়গায় slli নিরাপদ: wrap-সহও x · 23 আর x-কে তিন ঘর বাঁয়ে সরানো একই বিট দেয়। C-তে signed integer overflow undefined behavior, কিন্তু সেটি ভাষার নিয়ম; যন্ত্রের নির্দেশ wrap-ই করে।
  • তুলনা। slt signed তুলনা, Haat-এর <-এর সমান। Unsigned-এর জন্য আলাদা sltu; ভুল করে সেটি নিলে ঋণাত্মক সংখ্যায় ফল উল্টে যাবে।
  • ভাগ আর ভাগশেষ। এখানেই আসল সাবধানতা, নিচে।

RISC-V-এর নিয়ম The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA (version 20240411)-এর “M” Extension, Version 2.0 অধ্যায় থেকে: div শূন্যের দিকে কাটে, আর ভাগশেষের চিহ্ন ভাজ্যের মতো, ঠিক C আর Haat-এর মতো। কিন্তু দুটি কিনারার নিয়ম আলাদা: শূন্য দিয়ে ভাগে ভাগফলের সব বিট ১ (অর্থাৎ −1) আর ভাগশেষ ভাজ্যের সমান; আর signed overflow (সবচেয়ে ছোট সংখ্যা ÷ −1)-এ ভাগফল ভাজ্যের সমান, ভাগশেষ 0. কোনো exception বা trap হয় না। অধ্যায়টি নিজেই বলে, শূন্য-ভাগে trap বিবেচনা করা হয়েছিল, কিন্তু তাহলে সেটি standard ISA-র একমাত্র arithmetic trap হতো। লেখকের ল্যাবে Clang-এ assemble করে Unicorn emulator-এ চালানো (সত্যিকারের run):

div/rem 7 0 -> -1 7
div/rem -7 0 -> -1 -7
div/rem -9223372036854775808 -1 -> -9223372036854775808 0
div/rem -7 2 -> -3 -1
div/rem 7 -2 -> -3 1

এবার Haat-এর সঙ্গে মেলান। Reference-এর runtime.py-র c_div আর c_mod শূন্য ভাজকে runtime error দেয় division by zero, / বা % চিহ্নের অবস্থানে (সিদ্ধান্ত ২৪ আর ২৬); আর INT_MIN / -1 = INT_MIN, INT_MIN % -1 = 0 (সিদ্ধান্ত ১৩)। ফল দাঁড়ায়:

ক্ষেত্রRISC-V div/remHaatBack end-কে কী করতে হয়
সাধারণশূন্যের দিকে কাটাএকইকিছু না
MIN ÷ −1MIN, ভাগশেষ 0একই (wrap)কিছু না
÷ 0−1, ভাগশেষ = ভাজ্য; trap নেইruntime error, line:col-সহআগে নিজে পরীক্ষা: beqz b, err

তাই div tile দুটি নির্দেশ লেখে: beqz b, .Lprice_dz1, তারপর div. শাখাটি যায় function-এর শেষে একটি ছোট “stub”-এ, যা error-এর অবস্থান argument হিসেবে দিয়ে runtime-এর একটি function ডাকে: li a0, LINE; li a1, COL; call haat_div_zero. সেই function বার্তা ছাপে আর program থামায়; সেটি লেখা আর যুক্ত করা পর্ব ৭২-এর কাজ। ভাজক একটি অশূন্য ধ্রুবক হলে (p / 10) পরীক্ষাটি লাগেই না, তাই divk আর divm tile-এ beqz নেই। ভাজক ধ্রুবক 0 হলে সাধারণ div tile beqz zero, … লেখে, যা সবসময় লাফ দেয়: আলাদা নিয়ম ছাড়াই ঠিক। পরীক্ষাটি বাঁ আর ডান দুই operand-এর হিসাবের পরে বসে, কারণ Haat-এ আগে দুই দিক হিসাব হয়; বাঁ দিকেও আরেকটি শূন্য-ভাগ থাকলে সেটির error আগে আসবে।

অন্য লক্ষ্যে অন্য নিয়ম: RISC-V-এর জন্য যা ঠিক, তা অন্য যন্ত্রে নাও হতে পারে। WebAssembly-র i64.div_s শূন্যে আর MIN ÷ −1-এ, দুই ক্ষেত্রেই trap করে; তাই পর্ব ৭৩-এর Wasm back end-কে দুটোই নিজে সামলাতে হবে। C-তে দুটোই undefined behavior, তাই Clang কোনো পরীক্ষাই বসায় না: long divv(long a, long b) { return a / b; }-এর -O2 কোড শুধু div a0, a0, a1 আর ret (সত্যিকারের run). ভাষার অর্থ ঠিক করে back end কী যোগ করবে; যন্ত্র নয়।

৫ · Maximal munch — ওপর থেকে সবচেয়ে বড় টুকরো

সবচেয়ে সরল কৌশলটির নাম maximal munch (নামটি Andrew Appel-এর compiler-এর পাঠ্যবইয়ের মাধ্যমে বিশেষ পরিচিত)। মুদি দোকানের উদাহরণে: ফর্দের মাথা থেকে শুরু করে প্রতিবার সবচেয়ে বড় যে প্যাক মেলে সেটি তুলে নিন, তারপর বাকি অংশের জন্য একই কাজ। Lexer-এর longest match-এর (পর্ব ৪৬) সঙ্গে নামের মিল আছে, ধারণাতেও: “যতটা পারা যায় একবারে খাও”।

অ্যালগরিদম ৬৯.১ — maximal munch

Munch(n): n-এ বসে এমন সব tile-এর মধ্যে সবচেয়ে বেশি node ঢাকে এমনটি নিন (সমান হলে কম নির্দেশেরটি); সেই tile-এর প্রতিটি operand-উপগাছ m-এর জন্য বাঁ থেকে ডানে Munch(m); তারপর tile-এর নির্দেশগুলো লিখুন। সিদ্ধান্ত ওপর থেকে নিচে, কিন্তু নির্দেশ লেখা হয় post-order-এ, কারণ operand-এর মান আগে লাগে।

ছবি ৬৯.১ — qty * unit - p / 10-এর গাছ আর তিনটি tile

qty, unit, p আগে থেকেই register-এ; 10 একটি tile-এর ভেতরে

Maximal munch tiling of (- (* qty unit) (/ p 10)): sub at the root, mul for the product, and one divk tile covering the division together with the constant 10 - * / qtya0 unita1 pa2 10 sub a0, t0, t1 mul t0, a0, a1 li t2, 10 div t1, a2, t2 লেখার ক্রম: ① mul → ② li, div → ③ sub ধূসর পাতা = আগে থেকেই register-এ, কোনো tile নয়
ছবি ৬৯.১ — তিনটি tile পুরো গাছ ঢাকে, প্রতিটি node ঠিক একবার: নীল sub মূলটি, সবুজ mul গুণটি, আর কমলা divk ভাগ আর ধ্রুবক 10 দুটোকে একসঙ্গে। ভাজক অশূন্য ধ্রুবক, তাই শূন্যের পরীক্ষা নেই। মোট চারটি নির্দেশ।
1(-                 ← মূল2   (* qty unit)3   (/ p 10))
munch-এর খাতা
যে tile মেলে
বাছাই
খালি scratch
  1. মূলে বিয়োগ। sub মেলে। subi মেলে না, কারণ ডান সন্তান ধ্রুবক নয়। বাছাই sub; তার দুই operand-উপগাছ এখন munch হবে।
  2. বাঁয়ে গুণ। unit ধ্রুবক নয়, তাই slli বসে না; বাছাই mul. তার দুই পাতা আগে থেকেই register-এ (a0, a1), তাই আর কিছু করার নেই।
  3. ডানে ভাগ। তিনটি tile মেলে: div শুধু ভাগ-node ঢাকে; divk আর divm ভাগ আর 10 দুটোই। Munch বড়টি নেয়; দুটি বড়টির মধ্যে কম নির্দেশেরটি divk (২টি; divm-এ ১২টি, কারণ magic সংখ্যার li-ই ৮টি)।
  4. লেখা শুরু, post-order. সবচেয়ে বাঁয়ের tile আগে: mul t0, a0, a1. ফলের জন্য scratch register-এর তালিকা থেকে প্রথম খালিটি, t0.
  5. ভাগ। ফলের জন্য t1, ধ্রুবকের জন্য বাড়তি একটি t2. 10 অশূন্য, তাই beqz নেই।
  6. মূল। পুরো গাছের ফল যাবে a0-তে (ফেরত মানের register), তাই sub সরাসরি a0-তে লেখে, আর t0, t1, t2 আবার খালি। মোট ৪টি নির্দেশ।

Register-এর সৎ সীমা: মাঝের মানের জন্য selector t0–t6 সাতটি scratch register নেয় আর ফেরত দেয়। Haat-এর নামগুলো কোথায় থাকবে, তা বাইরে থেকে একটি loc dict বলে দেয়; memory হলে ("-24(s0)") আগে একটি ld বসে। সাতটির বেশি scratch লাগলে selector স্পষ্ট বার্তায় থামে; আসল বণ্টন পর্ব ৭০-এর কাজ। haat_isel.py থেকে হুবহু, লেখার অংশ:

    def ev(self, n, want=None):                  # n-এর মান কোনো register-এ; সেই register ফেরত
        if n.op == "name":
            r = self.loc[n.val]
            if "(" in r: d = want or self.new(); self.emit(f"ld {d}, {r}"); return d
            if want and want != r: self.emit(f"mv {want}, {r}"); return want
            return r
        if n.op == "const":
            if n.val == 0 and not want: return "zero"
            d = want or self.new(); self.emit(f"li {d}, {int(n.val)}"); return d
        t, b, _, _ = self.choose(n)
        regs = [self.ev(m) for m in b["ops"]]
        d = want or next((r for r in regs if r in SCRATCH), None) or self.new(regs)
        x = self.new(regs + [d]) if "{x}" in str(t[3]) or t[3] == "magic" else "x"
        e = "e"
        if "{e}" in str(t[3]):
            e = f".L{self.prefix}_dz{len(self.stubs) + 1}"; self.stubs.append((e, n.pos))
        for s in self.lines(t, b, d, regs, x, e): self.emit(s)
        for r in regs + [x]:
            if r != d: self.release(r)
        return d
সহায়ক module haat_isel.py পুরোটা দেখুন (এই পর্বের selector, পর্ব ৭২ এটি ব্যবহার করবে)
# haat_isel.py — পর্ব ৬৯: Haat IR থেকে expression tree, আর RISC-V (RV64IM)-এর instruction selection.
# পর্ব ৬২-এর haat_ir.py-র ওপর লেখা, সেটি অপরিবর্তিত। Tile বাছাই দুইভাবে: maximal munch (ওপর থেকে) আর DP (নিচ থেকে)।
# Assembly: GNU as-এর লেখা (Clang-এর assembler নেয়); register-এর ABI নাম; ভাগে শূন্যের পরীক্ষা নিজে বসানো।
from haat_ir import *

@dataclass(eq=False)
class Node:                                      # tree-র node: "const", "name", বা operator (+ - * / % == != < <= > >= neg !)
    op: str
    kids: list = field(default_factory=list)
    val: object = None                           # const: Int বা Bool (যন্ত্রে true = 1, false = 0); name: IR নাম
    pos: tuple = None                            # / আর %: শূন্য দিয়ে ভাগের error কোন (line, col)-এ

def sexpr(n):
    if n.op in ("const", "name"): return lit(n.val) if n.op == "const" else n.val
    return "(" + " ".join([n.op] + [sexpr(k) for k in n.kids]) + ")"

def block_trees(fn, b):                          # একটি block -> statement-এর তালিকা, প্রতিটিতে গাছ
    nuse, ndef = {}, {}
    for body in fn.blocks.values():
        for i in body:
            for x in i.args: nuse[x] = nuse.get(x, 0) + 1
            if i.dst: ndef[i.dst] = ndef.get(i.dst, 0) + 1
    here = {x for i in fn.blocks[b] for x in i.args}
    def foldable(i):                             # একবার লেখা, একবার পড়া, এই block-এই পড়া temp
        return i.kind in ("const", "copy", "bin", "un") and is_temp(i.dst) and ndef[i.dst] == 1 \
            and nuse.get(i.dst, 0) == 1 and i.dst in here
    out, run = [], []
    def build(i, deep, pend, used):              # নির্দেশ i-এর গাছ; deep হলে অপেক্ষমাণ temp ভেতরে ঢোকে
        def leaf(x):
            if deep and x in pend:
                j = pend.pop(x); n = build(j, True, pend, used); used.append(j); return n
            return Node("name", val=x)
        if i.kind == "const":
            if isinstance(i.sym, str): raise Unsupported("Str values are not selected here")
            return Node("const", val=0 if i.sym is None else i.sym)   # Unit () -> 0 (মানটি কেউ পড়ে না)
        if i.kind == "copy": return Node("name", val=i.args[0], pos=i.pos) if i.args[0][0] == "@" else leaf(i.args[0])
        if i.kind == "un": return Node("neg" if i.sym == "-" else "!", [leaf(i.args[0])])
        if i.kind == "bin": l = leaf(i.args[0]); return Node(i.sym, [l, leaf(i.args[1])], pos=i.pos)
        return [leaf(x) for x in i.args]         # call, print, return, branch: শুধু operand-এর গাছ
    def stmt(i, kids):
        k = i.kind
        if k == "call": return ("call", i.dst, i.sym, kids)
        if k in ("print", "return"): return (k, kids[0])
        if k == "branch": return ("branch", kids[0], *i.targets)
        if k == "jump": return ("jump", i.targets[0])
        return ("set", i.dst, kids, i.pos)       # const/copy/bin/un, যা গাছে ঢোকেনি; pos: @x-এ লেখার পরীক্ষা
    for i in fn.blocks[b]:
        if foldable(i): run.append(i); continue
        pend, used = {j.dst: j for j in run}, []
        kids = build(i, True, pend, used)
        if pend or used != run:                  # ক্রম না মিললে ভাঁজ নয়: আগের মতো একে একে (error-এর ক্রম রক্ষা)
            out += [("set", j.dst, build(j, False, {}, []), j.pos) for j in run]
            kids = build(i, False, {}, [])
        out.append(stmt(i, kids)); run = []
    return out

# ---------- RV64IM: ধ্রুবক, tile আর খরচ ----------
def fits12(k): return -2048 <= k <= 2047        # I-type immediate: ১২ বিট, sign-সহ
def sext(v, bits): v &= (1 << bits) - 1; return v - (1 << bits) if v >> (bits - 1) else v

def li_seq(v):                                   # `li rd, v` কয়টি আসল নির্দেশ হয় (LLVM-এর RISCVMatInt-এর মূল ধারণা)
    if -2**31 <= v < 2**31:
        hi, lo = ((v + 0x800) >> 12) & 0xFFFFF, sext(v, 12)
        return (1 if hi else 0) + (1 if lo or not hi else 0)          # lui, তারপর addi(w)
    lo, hi = sext(v, 12), ((v + 0x800) % 2**64) >> 12
    sh = 12 + ((hi & -hi).bit_length() - 1)
    best = li_seq(sext(hi >> (sh - 12), 64 - sh)) + 1 + (1 if lo else 0)   # ... তারপর slli, addi
    lz = 64 - (v % 2**64).bit_length()
    if v > 0 and lz:                             # বিকল্প: বাঁয়ে সরিয়ে ১ ভরে, শেষে srli
        best = min(best, li_seq(sext(((v << lz) | ((1 << lz) - 1)) % 2**64, 64)) + 1)
    return best

def pow2(k): return 1 < k < 2**62 and k & (k - 1) == 0
def magic(d):                                    # d >= 3: q = mulh(n, M) >> s, তারপর ঋণাত্মক হলে +1 (Hacker's Delight ১০-১)
    two, anc = 2**63, 2**63 - 1 - (2**63 % d)
    p, q1, r1, q2, r2 = 63, two // anc, two % anc, two // d, two % d
    while True:
        p += 1; q1, r1, q2, r2 = 2 * q1, 2 * r1, 2 * q2, 2 * r2
        if r1 >= anc: q1, r1 = q1 + 1, r1 - anc
        if r2 >= d: q2, r2 = q2 + 1, r2 - d
        if not (q1 < d - r2 or (q1 == d - r2 and r1 == 0)): return sext(q2 + 1, 64), p - 64

# Tile: (নাম, pattern, শর্ত, নির্দেশ)। pattern-এ "a" "b" = যেকোনো উপ-গাছ (register-এ আসে), "#" = ধ্রুবক k.
# নির্দেশের লেখায় {d} = ফলের register, {a} {b} = operand, {k} = ধ্রুবক, {x} = বাড়তি scratch, {e} = error label.
TILES = [
    ("add",   ("+", "a", "b"),  None,                ["add {d}, {a}, {b}"]),
    ("addi",  ("+", "a", "#"),  lambda k: fits12(k), ["addi {d}, {a}, {k}"]),
    ("addi'", ("+", "#", "a"),  lambda k: fits12(k), ["addi {d}, {a}, {k}"]),
    ("sub",   ("-", "a", "b"),  None,                ["sub {d}, {a}, {b}"]),
    ("subi",  ("-", "a", "#"),  lambda k: fits12(-k), ["addi {d}, {a}, {-k}"]),
    ("mul",   ("*", "a", "b"),  None,                ["mul {d}, {a}, {b}"]),
    ("slli",  ("*", "a", "#"),  pow2,                ["slli {d}, {a}, {lg}"]),
    ("slli'", ("*", "#", "a"),  pow2,                ["slli {d}, {a}, {lg}"]),
    ("div",   ("/", "a", "b"),  None,                ["beqz {b}, {e}", "div {d}, {a}, {b}"]),
    ("divk",  ("/", "a", "#"),  lambda k: k != 0,    ["li {x}, {k}", "div {d}, {a}, {x}"]),
    ("divp2", ("/", "a", "#"),  pow2,                ["srai {x}, {a}, 63", "srli {x}, {x}, {64-lg}",
                                                      "add {x}, {a}, {x}", "srai {d}, {x}, {lg}"]),
    ("divm",  ("/", "a", "#"),  lambda k: k >= 3 and not pow2(k), "magic"),
    ("rem",   ("%", "a", "b"),  None,                ["beqz {b}, {e}", "rem {d}, {a}, {b}"]),
    ("remk",  ("%", "a", "#"),  lambda k: k != 0,    ["li {x}, {k}", "rem {d}, {a}, {x}"]),
    ("slt",   ("<", "a", "b"),  None,                ["slt {d}, {a}, {b}"]),
    ("slti",  ("<", "a", "#"),  lambda k: fits12(k), ["slti {d}, {a}, {k}"]),
    ("sgt",   (">", "a", "b"),  None,                ["slt {d}, {b}, {a}"]),
    ("sgti",  (">", "a", "#"),  lambda k: fits12(k + 1), ["slti {d}, {a}, {k+1}", "xori {d}, {d}, 1"]),
    ("sle",   ("<=", "a", "b"), None,                ["slt {d}, {b}, {a}", "xori {d}, {d}, 1"]),
    ("slei",  ("<=", "a", "#"), lambda k: fits12(k + 1), ["slti {d}, {a}, {k+1}"]),
    ("sge",   (">=", "a", "b"), None,                ["slt {d}, {a}, {b}", "xori {d}, {d}, 1"]),
    ("sgei",  (">=", "a", "#"), lambda k: fits12(k), ["slti {d}, {a}, {k}", "xori {d}, {d}, 1"]),
    ("seq",   ("==", "a", "b"), None,                ["xor {d}, {a}, {b}", "seqz {d}, {d}"]),
    ("seqi",  ("==", "a", "#"), lambda k: fits12(-k), ["addi {d}, {a}, {-k}", "seqz {d}, {d}"]),
    ("sne",   ("!=", "a", "b"), None,                ["xor {d}, {a}, {b}", "snez {d}, {d}"]),
    ("snei",  ("!=", "a", "#"), lambda k: fits12(-k), ["addi {d}, {a}, {-k}", "snez {d}, {d}"]),
    ("neg",   ("neg", "a"),     None,                ["neg {d}, {a}"]),
    ("not",   ("!", "a"),       None,                ["xori {d}, {a}, 1"]),
    ("notle", ("!", ("<=", "a", "b")), None,         ["slt {d}, {b}, {a}"]),
    ("notge", ("!", (">=", "a", "b")), None,         ["slt {d}, {a}, {b}"]),
]
BRANCH = {"<": "blt {a}, {b}", ">=": "bge {a}, {b}", ">": "blt {b}, {a}", "<=": "bge {b}, {a}",
          "==": "beq {a}, {b}", "!=": "bne {a}, {b}"}     # তুলনা আর লাফ এক নির্দেশে
INV = {"<": ">=", ">=": "<", ">": "<=", "<=": ">", "==": "!=", "!=": "=="}
INSN = {}                                        # খরচ = আসল নির্দেশের সংখ্যা (li-এর বিস্তারসহ)
LATENCY = {"mul": 3, "mulh": 3, "div": 66, "rem": 66, "*": 3}   # LLVM-এর SiFive7 model-এর latency; বাকি সব ৩
SCRATCH = ["t0", "t1", "t2", "t3", "t4", "t5", "t6"]

def line_cost(s, model):                         # একটি assembly লাইনের খরচ
    op, *rest = s.split(None, 1)
    w = model.get(op, model.get("*", 1))
    return w * li_seq(int(rest[0].split(",")[1])) if op == "li" else w

def match(p, n, b):                              # pattern p কি node n-এ বসে? b-তে operand আর k জমে
    if p in ("a", "b"): b["ops"].append(n); return True
    if p == "#":
        if n.op != "const": return False
        b["k"] = int(n.val); return True
    return n.op == p[0] and len(p) - 1 == len(n.kids) and all(match(q, m, b) for q, m in zip(p[1:], n.kids))

def size(p): return 0 if p in ("a", "b") else 1 if p == "#" else 1 + sum(size(q) for q in p[1:])

class Selector:
    def __init__(self, loc, how="munch", model=INSN, prefix="f", stub="call"):
        self.loc, self.how, self.model, self.prefix, self.stub = loc, how, model, prefix, stub
        self.out, self.stubs, self.free, self.memo = [], [], list(SCRATCH), {}
    def tiles(self, n):                          # n-এ বসে এমন সব tile: (tile, binds, নিজের নির্দেশ)
        res = []
        for t in TILES:
            b = {"ops": [], "k": None}
            if match(t[1], n, b) and (t[2] is None or t[2](b["k"])): res.append((t, b, self.lines(t, b)))
        return res
    def lines(self, t, b, d="d", regs=("a", "b"), x="x", e="e"):
        k = b["k"]
        if t[3] == "magic":
            M, s = magic(k)
            L = [f"li {x}, {M}", f"mulh {x}, {regs[0]}, {x}"] + ([f"add {x}, {x}, {regs[0]}"] if M < 0 else [])
            return L + ([f"srai {x}, {x}, {s}"] if s else []) + [f"srli {d}, {x}, 63", f"add {d}, {x}, {d}"]
        lg = k.bit_length() - 1 if k else 0
        f = dict(d=d, a=regs[0], b=regs[1] if len(regs) > 1 else "", x=x, e=e, k=k)
        return [s.replace("{-k}", str(-k if k is not None else 0)).replace("{k+1}", str((k or 0) + 1))
                 .replace("{64-lg}", str(64 - lg)).replace("{lg}", str(lg)).format(**f) for s in t[3]]
    def leaf_cost(self, n):
        if n.op == "name": return 0 if "(" not in self.loc[n.val] else line_cost("ld x, 0(sp)", self.model)
        if n.op == "const": return 0 if n.val == 0 else line_cost(f"li x, {int(n.val)}", self.model)
        return self.choose(n)[3]
    def choose(self, n):                         # (tile, binds, নির্দেশ, গাছের মোট খরচ) — munch না DP
        if id(n) in self.memo and self.memo[id(n)][0] is n: return self.memo[id(n)][1]
        opts = []
        for t, b, L in self.tiles(n):
            own = sum(line_cost(s, self.model) for s in L)
            total = own + sum(self.leaf_cost(m) for m in b["ops"])
            key = (-size(t[1]), sum(line_cost(s, INSN) for s in L)) if self.how == "munch" else (total,)
            opts.append((key, t, b, L, total))
        if not opts: raise Unsupported(f"no tile for {sexpr(n)}")
        best = min(opts, key=lambda o: o[0])
        self.memo[id(n)] = (n, best[1:]); return best[1:]   # n-ও রাখা: id আবার ব্যবহার হলে ভুল না হয়
    # ---------- নির্দেশ লেখা: post-order, বাঁ আগে (সিদ্ধান্ত ১২) ----------
    def emit(self, s): self.out.append("  " + s)
    def new(self, avoid=()):
        r = next((r for r in self.free if r not in avoid), None)
        if r is None: raise Unsupported("out of scratch registers (register allocation: পর্ব ৭০)")
        self.free.remove(r); return r
    def release(self, r):
        if r in SCRATCH and r not in self.free: self.free.append(r); self.free.sort(key=SCRATCH.index)
    def ev(self, n, want=None):                  # n-এর মান কোনো register-এ; সেই register ফেরত
        if n.op == "name":
            r = self.loc[n.val]
            if "(" in r: d = want or self.new(); self.emit(f"ld {d}, {r}"); return d
            if want and want != r: self.emit(f"mv {want}, {r}"); return want
            return r
        if n.op == "const":
            if n.val == 0 and not want: return "zero"
            d = want or self.new(); self.emit(f"li {d}, {int(n.val)}"); return d
        t, b, _, _ = self.choose(n)
        regs = [self.ev(m) for m in b["ops"]]
        d = want or next((r for r in regs if r in SCRATCH), None) or self.new(regs)
        x = self.new(regs + [d]) if "{x}" in str(t[3]) or t[3] == "magic" else "x"
        e = "e"
        if "{e}" in str(t[3]):
            e = f".L{self.prefix}_dz{len(self.stubs) + 1}"; self.stubs.append((e, n.pos))
        for s in self.lines(t, b, d, regs, x, e): self.emit(s)
        for r in regs + [x]:
            if r != d: self.release(r)
        return d
    def value(self, n, dest):                    # dest: register ("a0") বা memory ("-24(s0)")
        if "(" in dest:
            r = self.ev(n); self.emit(f"sd {r}, {dest}"); self.release(r)
        else: self.release(self.ev(n, dest))
    def branch(self, n, T, F, fall=None):        # n সত্য হলে T-তে, না হলে F-এ; fall = ঠিক পরের label
        if n.op == "!": return self.branch(n.kids[0], F, T, fall)
        if n.op in BRANCH:
            op = n.op
            if T == fall: T, F, op = F, T, INV[op]          # উল্টো শর্তে লাফ, বাকিটা নিচে গড়িয়ে
            a = self.ev(n.kids[0]); b = self.ev(n.kids[1])
            self.emit(BRANCH[op].format(a=a, b=b) + f", {T}"); self.release(a); self.release(b)
        else:
            r = self.ev(n)
            if T == fall: self.emit(f"beqz {r}, {F}"); T, F = F, T
            else: self.emit(f"bnez {r}, {T}")
            self.release(r)
        if F != fall: self.emit(f"j {F}")
    def stub_lines(self):                        # শূন্য দিয়ে ভাগ: Haat-এর error, line আর col সহ
        out = []
        for e, (line, col) in self.stubs:
            out += [f"{e}:", f"  li a0, {line}", f"  li a1, {col}", f"  {self.stub} haat_div_zero"]
        return out
    def cost(self): return sum(line_cost(s.strip(), self.model) for s in self.out if not s.endswith(":"))

def select_function(fn, loc, how="munch", model=INSN, stub="call"):   # leaf function: call/print ছাড়া
    S = Selector(loc, how, model, fn.name, stub)
    names = list(fn.blocks)
    S.out.append(f"{fn.name}:")
    for i, b in enumerate(names):
        fall = f".L{fn.name}_{names[i + 1]}" if i + 1 < len(names) else None
        if i: S.out.append(f".L{fn.name}_{b}:")
        for st in block_trees(fn, b):
            if st[0] == "set": S.value(st[2], loc[st[1]])
            elif st[0] == "return": S.value(st[1], "a0"); S.emit("ret")
            elif st[0] == "branch": S.branch(st[1], f".L{fn.name}_{st[2]}", f".L{fn.name}_{st[3]}", fall)
            elif st[0] == "jump":
                if f".L{fn.name}_{st[1]}" != fall: S.emit(f"j .L{fn.name}_{st[1]}")
            else: raise Unsupported(f"{st[0]} is selected in পর্ব ৭২ (needs the calling convention)")
    return S.out + S.stub_lines(), S

choose(n) ঠিক করে কোন tile; munch আর DP-র পার্থক্য শুধু সেখানে, পরের অংশে। ফলের register d হয় চাওয়া জায়গা (want), নয়তো operand-এর একটি scratch, যা এখন আর লাগবে না। Tile-এর নির্দেশে একটি বাড়তি register ({x}) লাগলে সেটি operand আর d থেকে আলাদা নেওয়া হয়, কারণ কিছু tile ফল লেখার পরেও operand পড়ে; এই নিয়ম না থাকলে p / 8-এর shift-ক্রমে p-এর মান মাঝপথে মুছে যেত। এবার চালিয়ে দেখুন:

# ধাপ ১: Haat IR -> expression tree -> maximal munch-এ RISC-V (price আর delivery)
from haat_isel import *                          # পর্ব ৬২-এর haat_ir.py-র ওপর: Node, block_trees, Selector …
mod = compile_ir(open("examples/bazar.haat", encoding="utf-8").read())
fn = mod.funcs["price"]
print(show_ir(fn))
print("-- গাছ:")
for b in fn.blocks:
    for st in block_trees(fn, b):
        parts = [sexpr(x) if isinstance(x, Node) else x for x in st[1:4] if isinstance(x, (str, Node))]
        print(f"{b}: {st[0]:6}", *parts)
loc = {"qty": "a0", "unit": "a1", "p": "a2", "total": "a0"}   # কোন নাম কোন register-এ (পর্ব ৭০-এর কাজ)
for name in ("price", "delivery"):
    lines, S = select_function(mod.funcs[name], loc, "munch")
    print(f"-- {name}: {S.cost()}টি নির্দেশ"); print("\n".join(lines))

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

fn price(qty, unit):
B0:
  p = qty * unit
  t1 = const 1000
  t2 = p >= t1
  branch t2 B1 B2
B1:
  t3 = const 10
  t4 = p / t3
  t5 = p - t4
  return t5
B2:
  return p
-- গাছ:
B0: set    p (* qty unit)
B0: branch (>= p 1000) B1 B2
B1: return (- p (/ p 10))
B2: return p
-- price: 9টি নির্দেশ
price:
  mul a2, a0, a1
  li t0, 1000
  blt a2, t0, .Lprice_B2
.Lprice_B1:
  li t1, 10
  div t0, a2, t1
  sub a0, a2, t0
  ret
.Lprice_B2:
  mv a0, a2
  ret
-- delivery: 6টি নির্দেশ
delivery:
  li t0, 1000
  blt a0, t0, .Ldelivery_B2
.Ldelivery_B1:
  li a0, 0
  ret
.Ldelivery_B2:
  li a0, 60
  ret

price-এর নয়টি নির্দেশ: B0-তে গুণ আর তুলনা-লাফ, B1-এ ভাগ-বিয়োগ, B2-তে শুধু mv. .Lprice_B1 label-টিতে কেউ লাফ দেয় না, B0 সেখানে গড়িয়ে পড়ে; সেটি থাকলে কোনো ক্ষতি নেই। delivery-তে ফেরত মান সরাসরি a0-তে li দিয়ে। লেখকের ল্যাবে এই price Clang-এ assemble করে Unicorn-এ চালানো হয়েছে: price(2, 520) = 936, price(3, 100) = 300, price(1, 1000) = 900, price(-5, 300) = −1500, আর price(240, 230) = 0 (গুণফল 270 wrap হয়ে 0); reference-এর haat.py run একই পাঁচটি সংখ্যা ছাপে।

৬ · Optimal tiling — dynamic programming

Munch শুধু tile-টি দেখে, tile-এর পরে বাকি যা থাকে তার দাম দেখে না। p > 0-এ দুটি tile মেলে: sgti, যা > আর 0 দুটোই ঢাকে (slti d, p, 1; xori d, d, 1, দুটি নির্দেশ), আর sgt, যা শুধু > ঢাকে (slt d, b, a, একটি)। Munch বড়টি নেয়। কিন্তু sgt-এর পরে বাকি থাকা 0-এর জন্য কোনো নির্দেশ লাগে না, কারণ zero register আছে: slt a0, zero, a2. মোট এক। বড় প্যাকটি সবসময় সস্তা নয়।

সমাধান dynamic programming: নিচ থেকে ওপরে, প্রতিটি node-এর জন্য “এই উপ-গাছ ঢাকার সবচেয়ে কম খরচ” একবার হিসাব করে রাখা।

নিয়ম ৬৯.২ — optimal tiling-এর recurrence

best(n) = minT [ cost(T) + Σm ∈ ops(T, n) best(m) ], যেখানে T এমন সব tile যা n-এ বসে আর শর্ত পূরণ করে, আর ops(T, n) হলো T-এর a/b জায়গায় পড়া উপ-গাছ। পাতার জন্য: register-এ থাকা নাম 0, memory-তে থাকা নাম একটি ld-এর খরচ, ধ্রুবক 0 হলে 0, অন্য ধ্রুবক li-এর খরচ।

অ্যালগরিদম: গাছটি post-order-এ ঘুরে প্রতিটি node-এ সব tile চেষ্টা করুন, প্রতিটির খরচ = নিজের খরচ + তার operand-উপগাছগুলোর (আগেই হিসাব করা) best; সবচেয়ে কমটি রাখুন, কোন tile দিয়ে তাও। তারপর মূল থেকে সেই বাছাই অনুসরণ করে নির্দেশ লিখুন, munch-এর মতোই post-order-এ। n node আর t tile হলে কাজ O(n · t), কারণ প্রতিটি tile-এর pattern ছোট আর স্থির।

প্রমাণের রূপরেখা — DP-র tiling optimal. দাবি: যেকোনো node n-এর জন্য best(n) হলো n-এর উপ-গাছের প্রতিটি বৈধ tiling-এর খরচের সর্বনিম্ন। গাছের উচ্চতার ওপর induction.

  1. ভিত্তি: পাতার একটিই “tiling”, তার খরচ সংজ্ঞা অনুযায়ী best.
  2. গঠন: n-এর যেকোনো বৈধ tiling-এ ঠিক একটি tile T n-কে ঢাকে। বাকি tile-গুলো ops(T, n)-এর উপ-গাছগুলোকে আলাদা আলাদা ঢাকে, কারণ tile-গুলো একে অপরের ওপর পড়ে না। খরচ যোগফলে ভাঙে: cost(T) + প্রতিটি উপ-গাছের tiling-এর খরচ।
  3. Induction: প্রতিটি উপ-গাছ m-এর tiling-এর খরচ ≥ best(m), আর best(m) অর্জনযোগ্য। তাই T স্থির থাকলে সর্বনিম্ন cost(T) + Σ best(m); সব T-এর ওপর সর্বনিম্ন নিলে ঠিক recurrence-টি। ∎

প্রমাণের দুটি অনুমান খেয়াল করুন: খরচ যোগ করা যায় (এক tile-এর খরচ অন্যটির ওপর নির্ভর করে না), আর register অসীম। আসল যন্ত্রে দুটোই পুরো সত্য নয়: register ফুরালে spill লাগে, আর CPU নির্দেশ একসঙ্গে চালায়। তাই “optimal” মানে “এই cost model-এ optimal”.

1(> p 0)2(- p3   (/ p 10))
DP-র টেবিল
node
প্রার্থী: খরচ
best
  1. পাতা। p আছে a2-তে: খরচ 0. ধ্রুবক 0-এর জন্য zero register: খরচ 0.
  2. >-এ দুই প্রার্থী। sgt: নিজের ১ + দুই পাতার 0 = 1. sgti 0-কে নিজের ভেতরে নেয়: নিজের ২ = 2. DP নেয় 1; munch নিত 2, কারণ sgti বেশি node ঢাকে।
  3. দ্বিতীয় গাছের পাতা। p: 0. 10 operand হলে একটি li লাগবে: 1. কিন্তু কোনো tile 10-কে নিজের ভেতরে নিলে সেই 1 লাগবে না; সেটি ওপরের node-এ ঠিক হবে।
  4. ভাগ, নির্দেশ গুনে (INSN). div: beqz আর div 2, সঙ্গে 10-এর li 1 = 3. divk: 2 (li ভেতরেই, আর শূন্যের পরীক্ষা নেই)। divm: magic সংখ্যার li 8 + আরও 4 = 12. best = 2.
  5. মূল। শুধু sub মেলে: 1 + 0 + 2 = 3. এখানে DP আর munch একই কোড দেয়: li, div, sub.
  6. একই গাছ, অন্য cost model. LATENCY-তে div 66, বাকি নির্দেশ 3. divk: 3 + 66 = 69. divm: li-এর 8 × 3 = 24, তারপর mulh, srai, srli, add 4 × 3 = 12; মোট 36. DP নেয় divm, মূলে 3 + 36 = 39: ছয়টি নির্দেশ, কোনো div নেই (M = 7378697629483820647). Cost model বদলালে সেরা tiling বদলায়।

DP আর munch-এর পার্থক্য কোডে মাত্র একটি লাইন, choose-এর বাছাইয়ের চাবি: munch-এ (−tile-এর আকার, tile-এর নিজের নির্দেশ), DP-তে উপ-গাছসহ মোট খরচ। তিনটি উপায় পাশাপাশি:

# ধাপ ২: একই গাছ, তিনভাবে — munch, DP (নির্দেশ গুনে), DP (latency গুনে)
from haat_isel import *
def tree(expr):                                  # একটি Haat expression -> Haat IR -> গাছ
    src = f"fn f(p: Int, unit: Int) -> Int {{ return {expr}; }}"
    return block_trees(compile_ir(src).funcs["f"], "B0")[-1][1]
ways = [("munch", INSN), ("dp", INSN), ("dp", LATENCY)]
for expr in ["p > 0", "1250 + 0", "p - p / 10", "p / 8"]:
    t = tree(expr); print(f"== {expr}   {sexpr(t)}")
    for how, model in ways:
        S = Selector({"p": "a2", "unit": "a1"}, how, model); S.value(t, "a0")
        m = "latency" if model is LATENCY else "নির্দেশ"
        print(f"  {how:5} {m:7} খরচ {S.cost():3}:", "; ".join(s.strip() for s in S.out))
S = Selector({"p": "a2"}, "dp", LATENCY)         # DP-র নিজের হিসাব: (/ p 10)-এ কোন tile কত খরচে
for t, b, L in S.tiles(tree("p / 10")):
    print(f"  tile {t[0]:5} নিজের খরচ {sum(line_cost(s, LATENCY) for s in L):3}  নির্দেশ {len(L)}")

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

== p > 0   (> p 0)
  munch নির্দেশ খরচ   2: slti a0, a2, 1; xori a0, a0, 1
  dp    নির্দেশ খরচ   1: slt a0, zero, a2
  dp    latency খরচ   3: slt a0, zero, a2
== 1250 + 0   (+ 1250 0)
  munch নির্দেশ খরচ   2: li t0, 1250; addi a0, t0, 0
  dp    নির্দেশ খরচ   1: addi a0, zero, 1250
  dp    latency খরচ   3: addi a0, zero, 1250
== p - p / 10   (- p (/ p 10))
  munch নির্দেশ খরচ   3: li t1, 10; div t0, a2, t1; sub a0, a2, t0
  dp    নির্দেশ খরচ   3: li t1, 10; div t0, a2, t1; sub a0, a2, t0
  dp    latency খরচ  39: li t1, 7378697629483820647; mulh t1, a2, t1; srai t1, t1, 2; srli t0, t1, 63; add t0, t1, t0; sub a0, a2, t0
== p / 8   (/ p 8)
  munch নির্দেশ খরচ   2: li t0, 8; div a0, a2, t0
  dp    নির্দেশ খরচ   2: li t0, 8; div a0, a2, t0
  dp    latency খরচ  12: srai t0, a2, 63; srli t0, t0, 61; add t0, a2, t0; srai a0, t0, 3
  tile div   নিজের খরচ  69  নির্দেশ 2
  tile divk  নিজের খরচ  69  নির্দেশ 2
  tile divm  নিজের খরচ  36  নির্দেশ 5

চারটি শিক্ষা। p > 0: munch-এর বড় tile দুই নির্দেশ, DP এক। 1250 + 0 (ধরুন constant propagation 1250 + total-এর total-কে 0 বানিয়েছে): munch সমান আকারের দুটি addi-রূপের প্রথমটি নেয়, যা 0-কে খায় আর 1250-এর জন্য আলাদা li রেখে যায়; DP অন্যটি নেয়, যা 1250-কে খায় আর 0-এর জন্য zero পায়। p - p / 10 আর p / 8: নির্দেশ গুনলে div-ই সস্তা; latency গুনলে 10-এর জন্য magic গুণ আর 8-এর জন্য shift-এর চারটি নির্দেশ। শেষের তিন লাইন DP-র ভেতরের হিসাব। লেখকের ল্যাবে ৩,০০০টি এলোমেলো program আর bazar.haat-এর IR থেকে পাওয়া ৭০,৫৪০টি গাছে মোট খরচ: নির্দেশ গুনে munch ২,২৪,৫১৪ আর DP ২,২৪,৪২০; munch বেশি দামি মাত্র ৯৪টি গাছে। Latency গুনলে munch বেশি দামি ৬৩৯টি গাছে। RISC-V-এর মতো সরল, নিয়মিত ISA-তে munch প্রায় সবসময় optimal-এর কাছে থাকে; পার্থক্য বাড়ে যখন tile-এর খরচ খুব অসমান।

Tree pattern matching আর DP মিলিয়ে code generator বানানোর পদ্ধতি Aho, Ganapathi আর Tjiang ১৯৮৯ সালে প্রকাশ করেন; পরে BURG (১৯৯২) আর iburg DP-র হিসাব আগেভাগে একটি automaton-এ ভরে রাখে (ইতিহাস: প্রশ্ন ০১)। আর গাছের জায়গায় DAG covering, অর্থাৎ ভাগ করা উপ-রাশি একবার ঢাকা, সাধারণভাবে NP-complete বলে প্রমাণিত; তাই বাস্তব compiler DAG-কে গাছে কাটে, যেমন block_trees একাধিকবার পড়া temp-এ কাটে (প্রশ্ন ০২)।

৭ · চালিয়ে যাচাই — সত্যিকারের assembler, emulator আর differential test

Selector-এর ভুল চুপচাপ: বেশির ভাগ input-এ ফল ঠিক, ভুল শুধু কোনো কিনারায় (2048, MIN, একটি register দুবার ব্যবহার)। তাই লেখকের ল্যাবে তিন স্তরে যাচাই (সত্যিকারের run):

  1. সত্যিকারের assembler: PyPI-র ziglang 0.17.1-এর ভেতরের Clang 22.1.8, -target riscv64-linux-musl -mcpu=generic_rv64+m -mno-relax -c: প্রতিটি লাইন বৈধ RISC-V assembly আর শুধু RV64IM-এর নির্দেশ। pyelftools 0.33 দিয়ে .text পড়া, কোনো relocation বাকি নেই।
  2. সত্যিকারের emulator: সেই machine code Unicorn 2.1.4-এ (QEMU-ভিত্তিক) চালানো। পরীক্ষার stub tail haat_div_zero লেখে, আর পরীক্ষার haat_div_zero একটি register-এ চিহ্ন দিয়ে ফেরে, যাতে a0-a1-এর line:col পড়া যায়।
  3. প্রত্যাশিত ফল: গাছের জন্য Haat-এর অর্থ (wrap, c_div, c_mod); পুরো function-এর জন্য পর্ব ৬২-এর run_ir.
পরীক্ষাআকারফল
এলোমেলো গাছ (Int আর Bool, গভীরতা ৪–৫, পাঁচ ভাগের এক ভাগে operand memory থেকে ld), munch, DP-INSN, DP-LATENCYপ্রতিটিতে ১০,০০০টি গাছ, ৬০,০০০ run; মোট ১,৮০,০০০সব মিলেছে; প্রতিটিতে ৯,০৯৮টি শূন্য-ভাগের error, অবস্থানসহ
এলোমেলো পুরো function (var, if/else, &&, !, return), তিন selection৩,০০০টি function × ৩ = ৯,০০০; ২৭,০০০ runসব run_ir-এর সমান; ৬,৮৩২টি error-সহ
পাতার ছোট interpreter rv_text.py বনাম Unicorn৬৩,০০০ runসব হুবহু এক

এই পরীক্ষাগুলো একটি সত্যিকারের ভুল ধরেছে। choose প্রথমে প্রতিটি node-এর বাছাই মনে রাখত id(n) দিয়ে। এক গাছে কাজ শেষ হলে Python পুরোনো node মুছে ফেলে, আর একই id নতুন গাছের অন্য node পেতে পারে; তখন selector পুরোনো বাছাই ফেরত দিত। এলোমেলো-গাছের পরীক্ষা এটি ধরেনি, কারণ সেখানে প্রতিটি গাছ নতুন Selector পায়; পুরো function-এর পরীক্ষায় একটি Selector অনেক গাছ দেখে, আর নিচের ব্লকের প্রথম সংস্করণে ৭২০টি run-এর ৮৬টি ভুল এল। সমাধান: node-টিকেও memo-তে রাখা। শিক্ষা: কোড যেভাবে ব্যবহার হবে, সেভাবেই পরীক্ষা করুন।

পাতার ভেতরে Clang আর Unicorn চলে না, তাই নিচের ব্লক assembly-র text সরাসরি চালায় একটি ছোট interpreter দিয়ে (rv_text.py, এই পর্বের সহায়ক ফাইল): এটি সত্যিকারের CPU নয়, encoding ছাড়া শুধু এই পর্বের নির্দেশগুলো বোঝে, আর ল্যাবে ৬৩,০০০ run-এ Unicorn-এর সঙ্গে মিলিয়ে পরীক্ষিত। এর div RISC-V-এর নিয়ম মানে: শূন্যে −1. প্রত্যাশিত ফল আসে পর্ব ৬২-এর run_ir থেকে:

সহায়ক ফাইল rv_text.py পুরোটা দেখুন (assembly-র text চালানোর ছোট interpreter)
# rv_text.py — পর্ব ৬৯: haat_isel.py যে assembly লেখে, তার text সরাসরি চালানোর ছোট RV64IM interpreter.
# সত্যিকারের CPU নয়: শুধু এই পর্বের নির্দেশগুলো, encoding ছাড়া। লেখকের ল্যাবে Unicorn-এর সঙ্গে মিলিয়ে পরীক্ষিত।
M = 2**64
def s64(v): v %= M; return v - M if v >= 2**63 else v
def q(a, b):                                     # RISC-V div: শূন্যে -1, MIN / -1 = MIN, শূন্যের দিকে কাটা
    if b == 0: return -1
    r = abs(a) // abs(b); return s64(r if (a < 0) == (b < 0) else -r)
ALU = {"add": lambda a, b: a + b, "sub": lambda a, b: a - b, "mul": lambda a, b: a * b,
       "mulh": lambda a, b: (a * b) >> 64, "div": q, "rem": lambda a, b: a if b == 0 else a - b * q(a, b),
       "slt": lambda a, b: int(a < b), "xor": lambda a, b: a ^ b, "sll": lambda a, b: a << b,
       "srl": lambda a, b: (a % M) >> b, "sra": lambda a, b: a >> b}
BR = {"blt": lambda a, b: a < b, "bge": lambda a, b: a >= b, "beq": lambda a, b: a == b, "bne": lambda a, b: a != b}

def run_asm(lines, entry, regs, limit=10000):    # ফেরত: register-এর dict, আর কোন label-এ থামল ("ret" বা runtime-এর নাম)
    code = [l.strip() for l in lines if l.strip()]
    at = {l[:-1]: i for i, l in enumerate(code) if l.endswith(":")}
    R = dict(regs, zero=0); pc = at[entry]
    def v(x): return 0 if x == "zero" else R.get(x, 0)
    for _ in range(limit):
        pc += 1; s = code[pc]
        if s.endswith(":"): continue
        op, *a = s.replace(",", " ").split()
        if op == "ret": return R, "ret"
        if op in ("call", "tail"): return R, a[0]               # runtime function: এখানে থামি
        if op == "j": pc = at[a[0]]; continue
        if op in ("beqz", "bnez"):
            if (v(a[0]) == 0) == (op == "beqz"): pc = at[a[1]]
            continue
        if op in BR:
            if BR[op](v(a[0]), v(a[1])): pc = at[a[2]]
            continue
        d = a[0]
        if op == "li": R[d] = s64(int(a[1]))
        elif op == "mv": R[d] = v(a[1])
        elif op == "neg": R[d] = s64(-v(a[1]))
        elif op in ("seqz", "snez"): R[d] = int((v(a[1]) == 0) == (op == "seqz"))
        elif op[-1] == "i" and op[:-1] in ALU: R[d] = s64(ALU[op[:-1]](v(a[1]), int(a[2])))   # addi slti xori slli srli srai
        else: R[d] = s64(ALU[op](v(a[1]), v(a[2])))
        if d == "zero": R[d] = 0
    raise RuntimeError("too many steps")
# ধাপ ৩: এলোমেলো Haat function -> selection -> assembly চালানো; ফল কি run_ir (পর্ব ৬২)-এর সমান?
import random
from haat_isel import *
from rv_text import run_asm                      # এই পর্বের assembly-র ছোট interpreter (সহায়ক ফাইল)
R = random.Random(69)
def ex(d):                                       # এলোমেলো Int expression
    if d == 0 or R.random() < 0.25:
        return R.choice(["x", "y", "z", "0", "1", "7", "10", "2047", "2048", "9223372036854775807"])
    if R.random() < 0.1: return f"-{ex(d - 1)}"
    return f"({ex(d - 1)} {R.choice('+-*/%+-*')} {ex(d - 1)})"
same = total = errors = 0
for i in range(120):
    cond = f"{ex(2)} {R.choice(['<', '<=', '>', '>=', '==', '!='])} {ex(2)}"
    src = f"fn f(x: Int, y: Int, z: Int) -> Int {{ if {cond} {{ return {ex(3)}; }} return {ex(3)}; }}\n"
    fn = compile_ir(src).funcs["f"]
    for how, model in [("munch", INSN), ("dp", LATENCY)]:
        lines, S = select_function(fn, {"x": "a0", "y": "a1", "z": "a2"}, how, model)
        for args in [(1, 2, 3), (R.randint(-99, 99), 0, R.choice([-1, 2**63 - 1])), (-2**63, -1, 10)]:
            call = ", ".join("-9223372036854775807 - 1" if a == -2**63 else str(a) for a in args)
            want = run_lines(compile_ir(src + f"print(f({call}));"))[-1]
            regs, stop = run_asm(lines, "f", dict(zip(["a0", "a1", "a2"], args)))
            got = str(regs["a0"]) if stop == "ret" else f"{regs['a0']}:{regs['a1']}: runtime error: division by zero"
            total += 1; same += got == want; errors += "error" in want
print(f"{total}টি run, মিলেছে {same}টি; এর মধ্যে শূন্য দিয়ে ভাগের error {errors}টি (অবস্থানসহ)")
print("শেষ function-এর DP/latency assembly:"); print("\n".join(lines))

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

720টি run, মিলেছে 720টি; এর মধ্যে শূন্য দিয়ে ভাগের error 179টি (অবস্থানসহ)
শেষ function-এর DP/latency assembly:
f:
  li t0, 9223372036854775807
  li t1, 9223372036854775807
  sub t0, t0, t1
  sub t0, t0, a0
  li t1, 9223372036854775807
  addi t1, t1, 10
  neg t1, t1
  bge t0, t1, .Lf_B2
.Lf_B1:
  li a0, 10
  ret
.Lf_B2:
  sub t0, a1, a2
  li t1, 9223372036854775807
  mul t1, zero, t1
  sub t0, t0, t1
  addi a0, t0, -1
  ret

৭২০টি run-এর সবগুলো মিলেছে, এর ১৭৯টি শূন্য দিয়ে ভাগের error, যার line:col-ও run_ir-এর সঙ্গে এক। শেষ function-এর কোডটি দেখুন: 9223372036854775807 - 9223372036854775807-এর জন্য দুটি li আর একটি sub, আর 0 * …-এর জন্য mul t1, zero, t1. Instruction selection ধ্রুবক ভাঁজ করে না; সেটি constant folding-এর কাজ (পর্ব ৬৫), যা selection-এর আগে চলার কথা। ধাপগুলো আলাদা রাখলে প্রতিটি সহজ থাকে আর আলাদাভাবে যাচাই করা যায়।

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

  • Instruction selection, register allocation আর scheduling-এর পার্থক্য? প্রথমটি কোন নির্দেশ, দ্বিতীয়টি কোন register, তৃতীয়টি কোন ক্রমে।
  • Maximal munch কি optimal? না; প্রতিটি node-এ সবচেয়ে বড় tile নেয়, কিন্তু বাকি অংশের খরচ দেখে না (p > 0-এর উদাহরণ)। DP একটি cost model-এ optimal.
  • একটি গাছ দিয়ে tiling আঁকুন আর খরচ বলুন। প্রতিটি node ঠিক একবার ঢাকা চাই; খরচ = tile-গুলোর খরচের যোগফল।
  • RISC-V-এ শূন্য দিয়ে ভাগ করলে কী হয়? Trap নেই: ভাগফল −1, ভাগশেষ ভাজ্য। ভাষা error চাইলে compiler নিজে পরীক্ষা বসায়।
  • বড় ধ্রুবক কীভাবে register-এ আসে? li pseudo-instruction, যা lui/addi/slli-এর একটি ক্রম; ১২ বিটে ধরলে একটি addi.

৮ · বাস্তব compiler — Clang-এর আউটপুট, SelectionDAG আর GlobalISel

আমাদের selector কেমন, তা বুঝতে একই price C-তে লিখে সত্যিকারের Clang-কে দেওয়া হলো। Haat-এর wrap-এর সঙ্গে মেলাতে -fwrapv (এখানে সেটি ছাড়াও আউটপুট হুবহু এক এসেছে); zig নিজে frame pointer রাখে, তাই -fomit-frame-pointer. সত্যিকারের run, Clang 22.1.8 (ziglang 0.17.1), directive-এর লাইন বাদ:

$ zig cc -target riscv64-linux-musl -O2 -g0 -fomit-frame-pointer -fwrapv -S price.c
price:
        mul     a0, a1, a0
        li      a1, 1000
        blt     a0, a1, .LBB0_2
        lui     a1, 838861
        addi    a1, a1, -819
        slli    a2, a1, 32
        add     a1, a1, a2
        mulhu   a1, a0, a1
        srli    a1, a1, 3
        sub     a0, a0, a1
.LBB0_2:
        ret

পাশাপাশি পড়ুন। গুণ, li 1000 আর উল্টো blt আমাদের munch-এর মতোই। পার্থক্য তিনটি। এক, Clang p-কে a0-তেই রাখে, তাই mv লাগে না আর দুটি পথ একটি ret ভাগ করে; এটি register allocation আর block সাজানোর ফল (পর্ব ৭০)। দুই, div-এর বদলে magic সংখ্যা দিয়ে গুণ। তিন, সবচেয়ে মজার: mulh নয়, mulhu (unsigned), আর ঋণাত্মক ফলের সংশোধন নেই। কারণ এই পথে Clang জানে p >= 1000, অর্থাৎ p ধনাত্মক, আর তখন unsigned ভাগই যথেষ্ট ও সস্তা। এই জ্ঞান শাখার শর্ত থেকে আসে, গাছের বাইরে থেকে; আমাদের selector তা দেখে না। Magic সংখ্যাটি Clang চারটি নির্দেশে বানিয়েছে, যেখানে assembler-এর li আটটি নিত। লেখকের ল্যাবে এই কোড Unicorn-এ চালানো হয়েছে: wrap-এর একটি ক্ষেত্রসহ ছয়টি input-এ ফল reference-এর সমান।

আরও কয়েকটি ছোট function, একই Clang -O2-এর সত্যিকারের আউটপুট থেকে: p / 8 → srai, srli, add, srai, ঠিক আমাদের divp2 tile; p + 2048 → addi a0, a0, 2047 আর addi a0, a0, 1; p * 9223372036854775807 → slli a1, a0, 63 আর sub a0, a1, a0. শেষ দুটি গাছের আকারই বদলায়, যা tiling-এর আগের একটি “combine” ধাপের কাজ। আকার ছোট রাখার -Os আর -Oz-তেও এই version p / 10-এ magic গুণ রেখেছে।

LLVM আর GCC-র ভেতরে

LLVM-এর প্রধান পথ SelectionDAG: প্রতিটি basic block-এর LLVM IR থেকে একটি DAG, তারপর “legalize” (যন্ত্র যা পারে না, যেমন ১২৮-বিট যোগ, তা ভেঙে ফেলা), DAG combine (উপরের p + 2048-এর মতো বদল), তারপর pattern matching: প্রতিটি যন্ত্রের নির্দেশের pattern TableGen নামের একটি বর্ণনা-ভাষায় লেখা, যা থেকে একটি matcher-টেবিল তৈরি হয়। -O0-তে দ্রুততার জন্য FastISel নামের সরল পথও আছে, যা না পারলে SelectionDAG-এ ফেরে। নতুন কাঠামো GlobalISel পুরো function-এ কাজ করে, আলাদা DAG না বানিয়ে; কিছু লক্ষ্যে (যেমন AArch64-এ -O0) এটি ডিফল্ট বলে LLVM-এর নথিতে বলা আছে, তবে লক্ষ্য আর version অনুযায়ী অবস্থা বদলায়। একই Clang 22.1.8-এ RISC-V-এর জন্য -mllvm -global-isel দিয়ে চালানো হলো (-global-isel-abort=1 দিয়েও একই আউটপুট, অর্থাৎ SelectionDAG-এ ফেরেনি; সত্যিকারের run):

price:
        li      a2, 999
        mul     a0, a1, a0
        bge     a2, a0, .LBB0_2
        lui     a1, 1035469
        addi    a1, a1, -819
        slli    a1, a1, 12
        addi    a1, a1, -819
        slli    a1, a1, 12
        addi    a1, a1, -819
        slli    a1, a1, 12
        addi    a1, a1, -819
        mulhu   a1, a0, a1
        srli    a1, a1, 3
        sub     a0, a0, a1
.LBB0_2:
        ret

ফল একই (Unicorn-এ একই ছয়টি input-এ মিলেছে), কিন্তু ১১টির জায়গায় ১৫টি লাইন: তুলনাটি p > 999 রূপে, আর magic সংখ্যাটি বানাতে আটটি নির্দেশ। GCC-র পথ আলাদা: GIMPLE থেকে RTL-এ নামার সময় (“expand”) যন্ত্রের বর্ণনা-ফাইলের (.md) নামওয়ালা pattern ব্যবহার হয়, আর পরে combine pass পাশাপাশি কয়েকটি RTL নির্দেশ মিলিয়ে একটি বড় pattern খোঁজে; অর্থাৎ selection এক জায়গায় নয়, কয়েকটি ধাপে ছড়ানো। এখানে GCC চালানো হয়নি, তাই তার আউটপুট দেখানো হলো না।

শেষে একটি ছোট দৃশ্য-টুল: কোন tile গাছের কোন অংশ ঢাকে। এটি JavaScript-এ ছোট একটি tile-তালিকায় maximal munch; src বদলে, যেমন "(+ (* p 8) (/ p unit))" বা "(< (- x 1) 2048)" লিখে আবার চালিয়ে দেখুন:

// গাছের কোন অংশ কোন tile ঢাকে — ছোট একটি tile-তালিকায় maximal munch; src বদলে আবার চালান
const src = "(- (* qty unit) (/ p 10))";
const toks = src.match(/[()]|[^\s()]+/g); let i = 0;
const read = () => { const x = toks[i++]; if (x !== "(") return x;
  const n = [toks[i++]]; while (toks[i] !== ")") n.push(read()); i++; return n; };
const isK = x => typeof x === "string" && /^-?\d+$/.test(x);
const fits = k => k >= -2048 && k <= 2047, pow2 = k => k > 1 && (k & (k - 1)) === 0;
const TILES = [  // [নাম, operator, ডানে ধ্রুবক লাগে কি না, ধ্রুবকের শর্ত, নির্দেশের সংখ্যা]
  ["addi", "+", true, fits, 1], ["add", "+", false, null, 1], ["sub", "-", false, null, 1],
  ["slli", "*", true, pow2, 1], ["mul", "*", false, null, 1],
  ["li+div", "/", true, k => k !== 0, 2], ["beqz+div", "/", false, null, 2],
  ["slti", "<", true, fits, 1], ["slt", "<", false, null, 1]];
let total = 0; const out = [];
function munch(t, depth) {                       // বড় tile আগে: ধ্রুবক-সহ রূপ তালিকায় আগে
  const pad = "  ".repeat(depth);
  if (!Array.isArray(t)) {
    if (isK(t)) { out.push(`${pad}li       ঢাকে: ধ্রুবক ${t}`); total += 1; }
    else out.push(`${pad}(register ${t})`);
    return;
  }
  const [op, a, b] = t;
  const tile = TILES.find(([, top, wantK, ok]) => top === op && (!wantK || (isK(b) && ok(+b))));
  if (!tile) throw new Error("কোনো tile নেই: " + op);
  const [name, , wantK, , cost] = tile; total += cost;
  out.push(`${pad}${name.padEnd(8)} ঢাকে: ${op}${wantK ? " আর " + b : ""}  (${cost}টি নির্দেশ)`);
  munch(a, depth + 1); if (!wantK) munch(b, depth + 1);
}
munch(read(), 0);
console.log("গাছ: " + src); out.forEach(l => console.log(l));
console.log(`মোট ${total}টি নির্দেশ (ছোট ধ্রুবকের li একটি নির্দেশ ধরে)`);

আসল আউটপুট:

গাছ: (- (* qty unit) (/ p 10))
sub      ঢাকে: -  (1টি নির্দেশ)
  mul      ঢাকে: *  (1টি নির্দেশ)
    (register qty)
    (register unit)
  li+div   ঢাকে: / আর 10  (2টি নির্দেশ)
    (register p)
মোট 4টি নির্দেশ (ছোট ধ্রুবকের li একটি নির্দেশ ধরে)

ইন্ডেন্ট দেখায় কোন tile কার ভেতরে। li+div ভাগ আর 10 দুটোই ঢাকে, তাই 10-এর জন্য আলাদা লাইন নেই; তিনটি পাতা register-এ। এটি ছবি ৬৯.১-এর মতো একই tiling, আর মোট সংখ্যাও এক: চারটি নির্দেশ। তালিকায় ধ্রুবক-সহ রূপগুলো (addi, slli, li+div, slti) আগে রাখা, কারণ সেগুলো বড়; munch-এর পুরো বুদ্ধি এই ক্রমেই।

আরও গভীরে: x86-64-এর মতো CISC যন্ত্রে tile অনেক বড় হতে পারে: lea rax, [rdi + rsi*4 + 8] একটি নির্দেশে যোগ, ২-এর ঘাতে গুণ আর ধ্রুবক যোগ করে, আর memory operand-ওয়ালা add load আর যোগ একসঙ্গে করে। সেখানে tile-এর খরচ খুব অসমান, তাই DP-র লাভ বেশি। বাস্তবে instruction selection-কে register allocation আর scheduling-এর সঙ্গে একসঙ্গে optimal করা (যেমন integer linear programming বা constraint programming দিয়ে) নিয়ে গবেষণা আছে, যা ছোট function-এ optimal কোড দেয় কিন্তু সাধারণ compiler-এ এখনো খুব ধীর বলে বিবেচিত। এই পর্বের selector-এর API (Selector, value, branch, stub_lines, select_function) পর্ব ৭২-এর সম্পূর্ণ RISC-V back end সরলভাবে ব্যবহার করবে।

৯ · AI-এর যুগে instruction selection

AI assistant RISC-V assembly লিখতে পারে, আর একটি ছোট selector-ও। কিন্তু assembly-র ভুল খুব বিশ্বাসযোগ্য দেখায়: সঠিক নামের নির্দেশ, সঠিক বিন্যাস, শুধু একটি কিনারায় ভুল ফল। এই বিষয়ে সাধারণ ভুলগুলো:

AI-এর ভুলকীভাবে ধরবেন
অস্তিত্বহীন নির্দেশ (sgt, subi, immediate-ওয়ালা branch) বা x86-এর অভ্যাস RISC-V-তেClang দিয়ে সত্যিই assemble করুন; বৈধ না হলে assembler থামবে
১২ বিটের বাইরের ধ্রুবক addi-তে, বা 2048-কে বৈধ ধরা−2048, 2047, 2048 আর বড় ধ্রুবক দিয়ে test
“RISC-V শূন্য দিয়ে ভাগে trap করে” বা উল্টো, সব ISA-কে এক ধরাISA manual-এর সেই অধ্যায় আর version পড়ুন; emulator-এ চালিয়ে দেখুন
Wrap-এর সঙ্গে ভুল সরলীকরণ, যেমন (x - y) < 0 → blt x, yMIN, MAX, −1 দিয়ে differential test
Signed আর unsigned গুলিয়ে ফেলা (sltu, mulhu, srli বনাম srai)ঋণাত্মক input রেখে test
Clang-এর আউটপুট “মনে থেকে” বলা, বা বানানো LLVM flagনিজের যন্ত্রে সেই version-এ -S চালিয়ে --version লিখে রাখা

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

আমি Python 3.14-এ একটি শিক্ষামূলক ভাষার (Haat) জন্য RV64IM-এর instruction selector লিখছি। Int ৬৪-বিট, wrap করে; / আর % C-এর মতো শূন্যের দিকে কাটে; শূন্য দিয়ে ভাগ হলে runtime error দিতে হবে line:col-সহ; INT_MIN / -1 = INT_MIN. ১. (/ a b) আর (% a b)-এর tile লেখো, শূন্যের পরীক্ষাসহ; RISC-V-এর div/rem শূন্যে আর overflow-এ কী দেয়, তা ISA manual-এর কোন version-এর কোন অধ্যায় থেকে বলছ, উল্লেখ করো। ২. শুধু RV64IM-এর আসল নির্দেশ আর GNU as-এর মানক pseudo-instruction ব্যবহার করো; immediate যেন −2048…2047-এর ভেতরে থাকে। ৩. প্রতিটি tile-এর জন্য একটি করে test দাও, যেখানে MIN, MAX, −1, 0, 2047, 2048 আছে। ৪. কোনো বাস্তব compiler-এর আউটপুট বললে version বলো; নিশ্চিত না হলে অনুমান করবে না।

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

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

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

প্র ০১Instruction selection একসময় হাতে লেখা হতো, পরে “বর্ণনা থেকে তৈরি” হলো। এই পরিবর্তন কেন এল, আর কী লাভ হলো?

প্রথম দিকের compiler-এ code generator ছিল হাতে লেখা একটি বড় switch: প্রতিটি IR-কাজের জন্য কোন নির্দেশ, কোন কিনারায় কোন বিকল্প। নতুন যন্ত্র মানে প্রায় নতুন code generator, আর ভুলও হতো বিস্তর। ১৯৭০-এর দশকের শেষে একটি ধারণা দানা বাঁধে: যন্ত্রটিকে একটি বর্ণনা হিসেবে লিখুন (কোন নির্দেশ কোন গাছের নকশা ঢাকে, কত খরচে), আর একটি generator সেই বর্ণনা থেকে selector বানাক। Glanville আর Graham (১৯৭৮) নির্দেশের নকশাকে একটি grammar হিসেবে লিখে LR parser দিয়ে বাছাই করার পদ্ধতি দেন; কিন্তু grammar-এর ambiguity আর খরচের প্রশ্নে সমস্যা ছিল।

Aho, Ganapathi আর Tjiang-এর ১৯৮৯ সালের কাজ tree pattern matching আর dynamic programming মিলিয়ে দেখায় যে একটি বর্ণনা থেকে optimal tiling পাওয়া যায়, আর twig নামের tool এর উদাহরণ। তারপর BURG (১৯৯২) আর iburg: DP-র হিসাব আগেভাগে একটি automaton-এ ভরে রাখা, যাতে compile-এর সময় প্রতিটি node-এ শুধু টেবিল দেখা। শিক্ষামূলক lcc compiler তার বিভিন্ন লক্ষ্যের জন্য iburg-ধাঁচের একটি tool (lburg) আর এমন বর্ণনা ব্যবহার করত বলে তার লেখকদের বইয়ে উল্লেখ আছে।

আজকের LLVM-এ একই নীতি: প্রতিটি লক্ষ্যের নির্দেশ TableGen-এ বর্ণনা করা, আর সেখান থেকে matcher, assembler, disassembler, encoding সব তৈরি হয়। লাভ তিনটি। এক, নতুন যন্ত্র যোগ করা মানে মূলত বর্ণনা লেখা। দুই, একই বর্ণনা থেকে অনেক tool, তাই তারা পরস্পরের সঙ্গে মেলে। তিন, বর্ণনা যাচাই করা যায়, যেমন প্রতিটি pattern-এর অর্থ আর নির্দেশের অর্থ এক কি না। এই পর্বের TILES তালিকাও ছোট আকারে একটি বর্ণনা: নতুন tile যোগ করতে শুধু একটি লাইন।

মূল উপলব্ধি: যন্ত্রকে কোডে নয়, ডেটায় বর্ণনা করলে selector বানানো, বদলানো আর যাচাই করা সহজ হয়; DP সেই বর্ণনা থেকে optimal বাছাইয়ের গাণিতিক ভিত্তি দেয়।

প্র ০২গাছ আর DAG: একই উপ-রাশি দুবার লাগলে কী হয়, আর optimal DAG covering কঠিন কেন?

let p = qty * unit;-এর p তিনবার ব্যবহার হয়। p যদি একটি temp হতো, তাহলে IR-টি গাছ নয়, একটি DAG: একটি node-এর একাধিক পিতা। গাছের tiling-এর DP চলে কারণ প্রতিটি উপ-গাছ স্বাধীন: একটির বাছাই অন্যটির ওপর প্রভাব ফেলে না। DAG-এ সেটি ভাঙে। একটি ভাগ করা node-কে একবার হিসাব করে register-এ রাখবেন, নাকি প্রতিটি পিতার বড় tile-এর ভেতরে আবার হিসাব করবেন (যা কখনো সস্তা)? এই সিদ্ধান্তগুলো একে অপরের ওপর নির্ভরশীল, আর সাধারণভাবে optimal সমাধান খোঁজা NP-complete বলে প্রমাণিত; এর একটি রূপ ১৯৭০-এর দশকেই register machine-এর কোড তৈরির প্রসঙ্গে দেখানো হয়েছিল বলে উল্লেখ পাওয়া যায়।

বাস্তব compiler তাই সহজ পথ নেয়। প্রথম পথ: DAG-কে ভাগ করা node-এ কেটে কয়েকটি গাছ বানানো, আর প্রতিটি গাছে optimal DP. এই পর্বের block_trees ঠিক তাই করে: যে temp একবারের বেশি পড়া হয়, সেটি নিজে একটি নামওয়ালা মূল, আর তার ব্যবহারকারীরা তাকে register-এর পাতা হিসেবে দেখে। দ্বিতীয় পথ: DAG-এর ওপর সরাসরি greedy matching, যা LLVM-এর SelectionDAG করে; প্রতিটি block-এ একটি DAG, আর বড় pattern আগে মেলানো হয়। গবেষণায় DAG-এর জন্য প্রায়-optimal পদ্ধতিও আছে (যেমন ২০০৮ সালের দিকে Koes আর Goldstein-এর কাজ, যা গাছের DP-কে DAG-এ বাড়িয়ে ভাগ করা node-এর জন্য বাড়তি নিয়ম দেয়)।

আরেকটি সূক্ষ্মতা Haat-এর নিজের: DAG কাটার সময় হিসাবের ক্রমও রক্ষা করতে হয়, কারণ শূন্য-ভাগের error-এর অবস্থান ক্রমের ওপর নির্ভর করে। block_trees-এর post-order মিলিয়ে দেখার শর্তটি এজন্যই, আর ৩,০০০টি এলোমেলো program-এ সেটি পরীক্ষিত।

মূল উপলব্ধি: গাছে optimal সহজ, DAG-এ কঠিন; তাই compiler DAG-কে গাছে কাটে বা greedy পথে যায়, আর কাটার জায়গাগুলো হয় সেই মানগুলো, যা একাধিকবার লাগে।

প্র ০৩শূন্য দিয়ে ভাগে RISC-V trap করে না, x86 করে, WebAssembly করে। ISA-র এই পছন্দ ভাষা আর compiler-এর ওপর কী দায় চাপায়?

RISC-V-এর M extension-এর অধ্যায়ে যুক্তিটি লেখা আছে: শূন্য-ভাগে trap রাখলে সেটি standard ISA-র একমাত্র arithmetic trap হতো, আর সেই trap-এর জন্য hardware-এ বাড়তি জটিলতা লাগত। বদলে ফলটি নির্দিষ্ট করে দেওয়া হলো (ভাগফল সব বিট ১, ভাগশেষ ভাজ্য), যাতে যে ভাষা পরীক্ষা চায়, সে ভাগের ঠিক আগে একটি শাখা বসিয়ে নেয়। x86-64-এর idiv অন্যদিকে শূন্য-ভাগ আর overflow দুটিতেই একটি exception দেয়, যা operating system একটি signal হিসেবে program-এ পাঠায় (Linux-এ সাধারণত SIGFPE). WebAssembly-র i64.div_s দুটিতেই trap করে, কারণ তার নকশার লক্ষ্য প্রতিটি নির্দেশের অর্থ সব যন্ত্রে এক রাখা (পর্ব ৭৩)।

ভাষার দিক থেকে দেখুন। C-তে দুটোই undefined behavior, তাই C compiler কিছুই বসায় না, আর ফল যন্ত্রভেদে আলাদা: RISC-V-তে চুপচাপ −1, x86-এ program শেষ। Java-তে শূন্য-ভাগ একটি ArithmeticException, আর Integer.MIN_VALUE / -1 = MIN_VALUE; তাই JVM-কে RISC-V-তে পরীক্ষা বসাতে হয়, আর x86-এ উল্টো দিকে MIN ÷ −1-এর জন্য বাড়তি কাজ করতে হয় যাতে hardware-এর exception না আসে। Haat-এর নিয়ম Java-র মতো: শূন্যে error, MIN ÷ −1 = MIN. ফলে RISC-V-তে শুধু শূন্যের পরীক্ষা, Wasm-এ দুটি পরীক্ষা।

পরীক্ষার খরচ কত? একটি beqz, যা প্রায় সবসময় একই দিকে যায়, তাই আধুনিক CPU-র branch predictor সাধারণত তা ভালোভাবে অনুমান করে; আর ভাজক অশূন্য ধ্রুবক হলে পরীক্ষাই লাগে না। তবু এটি একটি নির্দেশ আর একটি শাখা, আর optimizer যদি প্রমাণ করতে পারে ভাজক অশূন্য (যেমন if d != 0-এর ভেতরে), তাহলে সেটি সরাতে পারে।

মূল উপলব্ধি: ভাষার অর্থ স্থির, ISA-র আচরণ আলাদা; back end-এর কাজ ফাঁকটুকু ভরানো, আর সেই ফাঁক প্রতিটি লক্ষ্য-যন্ত্রে আলাদা।

প্র ০৪“সবচেয়ে ভালো কোড” মানে কী: কম নির্দেশ, কম সময়, না ছোট আকার? Cost model বেছে নেওয়ার দ্বিধা।

এই পর্বে একই গাছ p - p / 10 দুই cost model-এ দুই রকম কোড দিয়েছে: নির্দেশ গুনলে li, div, sub (তিনটি নির্দেশ), latency গুনলে magic গুণের ছয়টি নির্দেশ। কোনটি ভালো? যন্ত্রের ওপর নির্ভর করে। যে ছোট embedded core-এ ভাগের hardware ধীর বা নেই, সেখানে গুণের পথ অনেক এগিয়ে; যে core-এ ভাগ দ্রুত, সেখানে পার্থক্য কম, আর কোডের আকার ছোট রাখা বেশি জরুরি হতে পারে। LLVM-এর SiFive7 model-এর ৬৬ cycle-এর ভাগ একটি নির্দিষ্ট পরিবারের অনুমান; অন্য core-এর model অন্য সংখ্যা দেবে।

বাস্তব compiler তাই একাধিক মাপকাঠি রাখে। -O2 সাধারণত গতি দেখে, -Os আর -Oz আকার। কিন্তু এই পর্বের সত্যিকারের run দেখিয়েছে, Clang 22.1.8 RISC-V-এর জন্য -Oz-তেও p / 10-এ magic গুণ রেখেছে; অর্থাৎ “আকার ছোট” মোডেও সব সিদ্ধান্ত আকার দিয়ে হয় না, বা ভাগকে ভিন্নভাবে দাম দেওয়া হয়। এর কারণ খুঁজতে হলে compiler-এর সেই version-এর সোর্স পড়তে হবে; অনুমান করে বলা ঠিক নয়।

আরেকটি স্তর: latency যোগ করা নিজেই একটি সরলীকরণ। আধুনিক out-of-order CPU একাধিক নির্দেশ একসঙ্গে চালায় (Computer Architecture-এর pipeline-এর পর্বগুলো), তাই পরস্পর-নির্ভরতাহীন দুটি নির্দেশের সময় যোগ হয় না। তাই compiler instruction selection-এ মোটা হিসাব করে, আর পরে scheduling ধাপে নির্ভরতার শিকল দেখে নির্দেশ সাজায়। শেষ বিচার সবসময় মাপা: নির্দিষ্ট যন্ত্রে নির্দিষ্ট কাজে সময় মেপে দেখা, আর মাপটি এক যন্ত্রের বলে চিহ্নিত করা।

মূল উপলব্ধি: “optimal” সবসময় একটি cost model-এর সাপেক্ষে; model যন্ত্র আর লক্ষ্য (গতি, আকার) অনুযায়ী বদলায়, আর DP-র শক্তি হলো model বদলালে বাছাইও ঠিকঠাক বদলায়।

প্র ০৫LLVM কেন SelectionDAG থেকে GlobalISel-এর দিকে যাচ্ছে, আর একটি নতুন selector-কে কীভাবে বিশ্বাস করা যায়?

SelectionDAG বহু বছর ধরে LLVM-এর মূল selector, আর এর pattern-গুলো অনেক পরিণত। কিন্তু এর কিছু কাঠামোগত সীমা LLVM-এর আলোচনায় বারবার উঠে এসেছে: এটি একবারে একটি basic block দেখে, তাই block পেরোনো সুযোগ হারায়; LLVM IR থেকে আলাদা একটি DAG বানানো আর ভাঙা সময়সাপেক্ষ; আর -O0-র দ্রুত পথ FastISel আলাদা কোড, যা দুটি selector-এর মধ্যে আচরণের পার্থক্য তৈরি করে। GlobalISel-এর লক্ষ্য একটি কাঠামোয় পুরো function দেখা, LLVM-এর machine-স্তরের নির্দেশের ওপর সরাসরি কাজ করা, আর দ্রুত ও অপ্টিমাইজ করা দুই মোডেই একই পথ রাখা। কোন লক্ষ্যে এটি কতটা এগিয়েছে, তা version অনুযায়ী বদলায়।

এই পর্বের সত্যিকারের run একটি ছোট ছবি দেয়: Clang 22.1.8-এ RISC-V-এর জন্য GlobalISel price সফলভাবে compile করেছে, ফল ঠিক, কিন্তু চারটি নির্দেশ বেশি, কারণ বড় ধ্রুবক বানানোর কৌশলটি সেখানে আসেনি। একটি function থেকে এর বেশি সিদ্ধান্ত টানা ঠিক নয়।

বিশ্বাসের প্রশ্নে উত্তর এই পর্বের পদ্ধতিই, বড় আকারে। LLVM-এর নিজের test-suite-এ হাজার হাজার ছোট test থাকে, যেখানে একটি IR-এর জন্য প্রত্যাশিত assembly লেখা থাকে। Csmith-এর মতো এলোমেলো C program-এর generator দুটি compiler বা দুটি optimization স্তরের ফল মিলিয়ে বহু ভুল খুঁজে পেয়েছে বলে প্রকাশিত। Alive2-এর মতো tool LLVM-এর রূপান্তরের সঠিকতা গাণিতিকভাবে পরীক্ষা করে। আর CompCert-এর মতো যাচাই-করা compiler (পর্ব ৪৪) instruction selection-সহ পুরো পথের সঠিকতা proof assistant-এ প্রমাণ করে।

মূল উপলব্ধি: selector-এর কাঠামো বদলায়, কিন্তু বিশ্বাসের ভিত্তি একই থাকে: স্পষ্ট অর্থ, সত্যিকারের যন্ত্রে বা emulator-এ চালানো, আর বড় আকারের differential test, যেখানে সম্ভব সেখানে proof.

অনুশীলন

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

  1. নকশা ও বাস্তবায়ন — নতুন tile: x * 9 = (x << 3) + x. haat_isel.py-র TILES-এ একটি tile যোগ করুন, যা k = 2j + 1 (k > 2) ধ্রুবক দিয়ে গুণকে slli আর add-এ লেখে। (ক) wrap-সহ এটি কেন ঠিক? (খ) INSN আর LATENCY model-এ DP কি কখনো এটি বেছে নেবে? (গ) কীভাবে যাচাই করবেন?
    ("muladd", ("*", "a", "#"), lambda k: k > 2 and pow2(k - 1),
               ["slli {x}, {a}, {lg}", "add {d}, {x}, {a}"]),    # lg = log2(k - 1)

    (ক) x · (2j + 1) = x · 2j + x গণিতে সত্য, আর 264 দিয়ে ভাগশেষ নিলেও যোগ আর গুণ একই থাকে; slli আর add দুটোই নিচের ৬৪ বিট রাখে, তাই wrap-সহ ফল mul-এর সমান। একটি সাবধানতা: {x} একটি আলাদা scratch, কারণ add ফল লেখার সময় আবার a পড়ে; ফল d যদি a-র register হতো আর মাঝের মান d-তে রাখা হতো, a মুছে যেত। (খ) এই কোডে {lg} k-এর log নেয়, তাই tile-এর জন্য k − 1 দিয়ে lines ডাকতে হয় (লেখকের ল্যাবে একটি ছোট wrapper). সত্যিকারের run: x * 9-এ INSN-এ খরচ 2 (li আর mul) বনাম 2, LATENCY-তে 6 বনাম 6, দুই ক্ষেত্রেই সমান, তাই DP পুরোনো tile-ই রাখে। শুধু যে model-এ গুণ বেশি দামি (যেমন গুণ 10, বাকি 1), সেখানে DP slli t0, a0, 3; add a0, t0, a0 নেয়। (গ) সেই model-এ এলোমেলো গাছের পরীক্ষা, ধ্রুবকের তালিকায় 3, 5, 9, 17, 232 + 1, 261 + 1 যোগ করে: ৬,০০০টি গাছে ৩৬,০০০ run, Clang-এ assemble করে Unicorn-এ, সব Haat-এর অর্থের সমান (৪,২৪০টি শূন্য-ভাগের error-সহ), আর নতুন tile ৮১১ বার ব্যবহার হয়েছে।

  2. ভুল খুঁজুন: একজন সহকর্মী (বা একটি AI assistant) শাখার জন্য একটি “চতুর” tile প্রস্তাব করলেন: গাছ (< (- a b) 0) দেখলে sub বাদ দিয়ে সরাসরি blt a, b, L (মান হিসেবে হলে slt d, a, b), কারণ “a − b < 0 মানে a < b”. Haat-এ এটি কি ঠিক? একটি পাল্টা উদাহরণ দিন।

    ভুল, কারণ Haat-এর বিয়োগ wrap করে। a = −9223372036854775807 − 1 (MIN), b = 1: a − b wrap হয়ে MAX, যা ধনাত্মক, তাই a - b < 0 মিথ্যা; কিন্তু a < b সত্য। উল্টো দিকেও: a = MAX, b = −1: a − b wrap হয়ে MIN, ঋণাত্মক, তাই সত্য; কিন্তু a < b মিথ্যা। সত্যিকারের run: Unicorn-এ sub t0, a0, a1; slt a0, t0, zero দেয় 0 আর 1; “চতুর” slt a0, a0, a1 দেয় 1 আর 0; আর reference-এর haat.py run return x - y < 0;-এর জন্য ছাপে false আর true, অর্থাৎ প্রথমটির সঙ্গে মেলে। ছোট সংখ্যায় (3, 5 বা 5, 3) দুটিই একই ফল দেয়, তাই হাতে দুই-একটি উদাহরণে ভুলটি ধরা পড়ে না। রূপান্তরটি ঠিক শুধু সেই ভাষায়, যেখানে signed overflow ঘটে না বলে ধরে নেওয়া যায়: C-তে signed overflow undefined behavior, তাই C compiler এমন রূপান্তর করতে পারে, Haat-এর compiler পারে না।

  3. হিসাব ও trace: নিচের function-এর জন্য (ক) block_trees-এর গাছ, (খ) maximal munch-এর RISC-V কোড, x = a0, y = a1, ফল a0-তে, আর নির্দেশের সংখ্যা, (গ) f(5, 4), f(-2, 4), f(2, -1) আর f(2305843009213693952, 6)-এর ফল লিখুন।
    fn f(x: Int, y: Int) -> Int {
        return (x * 8 - 3) % (y + 1);
    }
    return (% (- (* x 8) 3) (+ y 1))
    
    f:
      slli t0, a0, 3
      addi t0, t0, -3
      addi t1, a1, 1
      beqz t1, .Lf_dz1
      rem a0, t0, t1
      ret
    .Lf_dz1:
      li a0, 2
      li a1, 24
      call haat_div_zero

    (ক) সাতটি IR নির্দেশের সব temp একবার লেখা আর একবার পড়া, তাই পুরোটা একটি গাছ। (খ) * 8 → slli; - 3 → subi, যা addi … -3 লেখে; + 1 → addi; ভাজক ধ্রুবক নয়, তাই rem tile beqz-সহ। মূল অংশে ৬টি নির্দেশ (ret-সহ), আর stub-এ ৩টি; DP-ও একই কোড দেয়। Stub-এর 2 আর 24 হলো %-এর line আর column. (গ) f(5, 4): 37 % 5 = 2. f(−2, 4): −19 % 5 = −4 (ভাজ্যের চিহ্ন)। f(2, −1): ভাজক 0, তাই 2:24: runtime error: division by zero. f(261, 6): 261 · 8 = 264 wrap হয়ে 0, তারপর 0 − 3 = −3, আর −3 % 7 = −3. লেখকের ল্যাবে কোডটি Clang-এ assemble করে Unicorn-এ চালানো হয়েছে (stub-এ পরীক্ষার জন্য tail): চারটি ফলই reference-এর run-এর সঙ্গে এক।

  4. প্রমাণ — munch optimal নয়, DP optimal: (ক) একটি গাছ আর একটি tile-তালিকা দিন যেখানে maximal munch-এর খরচ optimal-এর চেয়ে বেশি। (খ) নিয়ম ৬৯.২-এর DP যে optimal, তার প্রমাণ কোন দুটি অনুমানের ওপর দাঁড়ায়, আর কোনটি ভাঙলে প্রমাণ ভাঙে?

    (ক) গাছ (> p 0), p একটি register-এ, ধ্রুবক 0-এর জন্য zero register (খরচ 0). Tile sgti = (> a #), খরচ 2 (slti, xori), দুটি node ঢাকে; tile sgt = (> a b), খরচ 1, একটি node. Munch বড়টি নেয়: খরচ 2. অন্য বৈধ tiling: sgt আর পাতা 0, খরচ 1 + 0 = 1. তাই munch-এর খরচ optimal-এর দ্বিগুণ। সত্যিকারের run: slti a0, a2, 1; xori a0, a0, 1 বনাম slt a0, zero, a2.

    (খ) প্রমাণের রূপরেখা অংশ ৬-এ। দুটি অনুমান: (১) tile-গুলো পরস্পর না ছুঁয়ে গাছ ঢাকে আর খরচ যোগ করা যায়, অর্থাৎ একটি উপ-গাছের খরচ তার পিতা কোন tile বেছেছে তার ওপর নির্ভর করে না; (২) প্রতিটি উপ-গাছ স্বাধীন, অর্থাৎ গঠনটি গাছ, DAG নয়। (১) ভাঙে যদি খরচ register-এর চাপের ওপর নির্ভর করে (register ফুরালে spill); (২) ভাঙে যদি একটি node-এর দুই পিতা থাকে, কারণ তখন সেই node-এর একবারের হিসাব দুই পিতার বাছাইকে জোড়া লাগায়। দুটি ক্ষেত্রেই recurrence আর সত্যিকারের সর্বনিম্ন মেলে না, আর সমস্যাটি সাধারণভাবে অনেক কঠিন (প্রশ্ন ০২)।

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

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

ক্রমHaat IR থেকে যাচাই-করা RISC-V কোড পর্যন্ত ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. একবার লেখা, একবার পড়া temp ভাঁজ করে প্রতিটি block-এ expression tree
  2. প্রতিটি node-এ যে tile-গুলো বসে, তা খোঁজা (pattern আর শর্ত)
  3. Munch বা DP দিয়ে প্রতিটি node-এর tile বাছাই
  4. Post-order-এ নির্দেশ লেখা, scratch register দিয়ে
  5. শূন্য-ভাগের stub function-এর শেষে যোগ
  6. সত্যিকারের assembler আর emulator-এ চালিয়ে ভাষার অর্থের সঙ্গে মেলানো

RV64I-এর addi-এর immediate ১২ বিটের, sign-সহ। কোন Haat expression এক নির্দেশে (addi) হয়, যেখানে p একটি register-এ?

  • p + 2048
  • p - 2048
  • p + 4096
  • p * 1000

RISC-V-এর M extension (v2.0) অনুযায়ী div নির্দেশে ভাজক 0 হলে কী হয়?

  • একটি exception (trap)
  • ভাগফল 0
  • ভাগফল −1, কোনো trap নেই
  • ফল অনির্দিষ্ট (undefined)

গাছ (> p 0), p একটি register-এ, ধ্রুবক 0-এর জন্য zero register. Tile: sgt = (> a b) খরচ 1; sgti = (> a #) খরচ 2. Maximal munch আর DP-র খরচ কত?

  • দুটিই 1
  • দুটিই 2
  • Munch 1, DP 2
  • Munch 2, DP 1

Haat IR-এর একটি block-এ t3 = a / b, তারপর t4 = call g(x), তারপর y = t3 + t4. t3 একবার পড়া হয়। Expression tree বানাতে t3-কে y-এর গাছে ভাঁজ করা কি নিরাপদ?

  • না: ভাগ call-এর পরে সরে যাবে, তাই error আর print-এর ক্রম বদলাতে পারে
  • হ্যাঁ, কারণ t3 একবারই পড়া হয়
  • হ্যাঁ, কারণ ভাগের কোনো side effect নেই
  • না, কারণ call কখনো গাছে থাকতে পারে না, তাই y-এর গাছই হয় না

Clang -O2 একটি C function-এ p / 10-এর জন্য div-এর বদলে একটি বড় ধ্রুবক দিয়ে mulh আর কয়েকটি shift লিখল। কোন ব্যাখ্যাটি ঠিক?

  • এটি ভাগের একটি আনুমানিক রূপ, বড় সংখ্যায় ভুল হতে পারে
  • ধ্রুবক দিয়ে ভাগকে গুণ আর shift-এ হুবহু লেখা যায়, আর div সাধারণত অনেক ধীর
  • RISC-V-এ div নির্দেশ নেই
  • শূন্য দিয়ে ভাগ এড়াতে

Haat-এর INT_MIN / -1 = INT_MIN আর INT_MIN % -1 = 0. RISC-V back end-কে এর জন্য কী করতে হয়?

  • div-এর আগে আলাদা শাখা দিয়ে এই ক্ষেত্র ধরা
  • trap এড়াতে ভাজ্যকে আগে বদলে নেওয়া
  • কিছুই না: RISC-V-এর ফল Haat-এর সঙ্গে মেলে
  • একটি runtime error দেওয়া

শব্দকোষ

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

মনে রাখুন

  1. Instruction selection = tiling: IR-কে expression tree-তে সাজিয়ে প্রতিটি node ঠিক একবার কোনো যন্ত্র-নির্দেশের নকশা (tile) দিয়ে ঢাকা; খরচ = tile-গুলোর খরচের যোগফল।
  2. নিরাপদ গাছ: শুধু একবার লেখা, একবার পড়া, একই block-এর temp ভাঁজ হয়, আর হিসাবের ক্রম বদলায় না; call আর বারবার পড়া মান নামওয়ালা মূল।
  3. RISC-V-এর tile: ১২ বিটের immediate (−2048…2047), বড় ধ্রুবকে li, slt/xori দিয়ে সব তুলনা, তুলনা-লাফ এক নির্দেশে, ধ্রুবক 0-এর জন্য zero.
  4. Munch বনাম DP: munch ওপর থেকে সবচেয়ে বড় tile, সহজ আর প্রায় সবসময় ভালো; DP নিচ থেকে, একটি cost model-এ optimal; model বদলালে বাছাই বদলায়।
  5. অর্থ আগে: wrap আর MIN ÷ −1 RISC-V-তে মেলে, শূন্য-ভাগ মেলে না, তাই beqz-এর পরীক্ষা; প্রতিটি tile সত্যিকারের assembler আর emulator-এ differential test দিয়ে যাচাই।

পরের পর্বে: পর্ব ৭০ (Register allocation — graph coloring আর linear scan). এই পর্বে নামগুলো বাইরে থেকে register পেয়েছিল; এবার পর্ব ৬৪-এর liveness থেকে interference graph বানিয়ে সীমিত register-এ সেগুলো বসানো, না ধরলে spill.

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

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