Instruction Selection ও Scheduling — IR থেকে আসল instruction

আগের লেসনের TACInstr convention-ই চলছে; selector output structured tuple + pretty string — scheduler tuple নিয়ে কাজ করে:

from dataclasses import dataclass

@dataclass
class X86:
    mnem: str            # 'mov', 'lea', 'add', 'imul', 'load'
    dest: str | None
    uses: list
    text: str

LAT = {'mov': 1, 'lea': 1, 'add': 1, 'imul': 3, 'load': 4}

def select(tac, regs):
    """TACInstr list → X86 list; regs = var→physical reg map"""
    out, pending_mul = [], {}            # var → (idx of imul-to-fold)
    for ins in tac:
        if ins.op == '*' and ins.b in ('#2', '#4', '#8'):
            rd, rs = regs[ins.dest], regs[ins.a]
            s = {'#2': 1, '#4': 2, '#8': 3}[ins.b]
            out.append(X86('lea', ins.dest, [ins.a],
                           f'lea {rd}, [{rs}*{2**s}]'))   # strength-reduce
            pending_mul[ins.dest] = len(out) - 1
            continue
        if ins.op == 'load_arr':         # arr[i]: scale fold!
            rb, ri = regs.get(ins.a, ins.a), regs[ins.b]
            out.append(X86('load', ins.dest, [ins.a, ins.b],
                           f'mov {regs[ins.dest]}, DWORD PTR '
                           f'[{rb} + {ri}*4]'))
            continue
        if ins.op == '+':
            rd, ra, rb_ = regs[ins.dest], regs[ins.a], regs[ins.b]
            out.append(X86('add', ins.dest, [ins.a, ins.b],
                           f'add {rd}, {ra}, {rb_}'))
            continue
        if ins.op == '*':
            rd = regs[ins.dest]
            rs1, rs2 = regs.get(ins.a, ins.a), regs.get(ins.b, '#1')
            out.append(X86('imul', ins.dest, [ins.a, ins.b],
                           f'imul {rd}, {rs1}, {rs2}'))
            continue
        if ins.op == '-':
            rd = regs[ins.dest]
            rs1, rs2 = regs[ins.a], regs[ins.b]
            out.append(X86('add', ins.dest, [ins.a, ins.b],
                           f'sub {rd}, {rs1}, {rs2}'))
            continue
        if ins.op == 'return':
            out.append(X86('mov', None, [ins.a],
                           f'ret   ; uses {regs[ins.a]}'))
            continue
        raise ValueError(ins.op)
    return out

def build_dag(code):
    deps = [[] for _ in code]            # deps[j] = producers j must wait
    last_write = {}
    last_reads = {}
    for j, ins in enumerate(code):
        for v in ins.uses:               # RAW
            if v in last_write:
                deps[j].append(last_write[v])
            last_reads.setdefault(v, []).append(j)
        if ins.dest:                     # WAR + WAW (fixed phys regs)
            for r in last_reads.get(ins.dest, []):
                deps[j].append(r)
            if ins.dest in last_write:
                deps[j].append(last_write[ins.dest])
            last_write[ins.dest] = j
            last_reads[ins.dest] = []
    return deps

def heights(code, deps):                 # priority = critical-path height
    memo = {}
    def h(i):
        if i not in memo:
            cons = [j for j in range(len(code)) if i in deps[j]]
            memo[i] = LAT[code[i].mnem] + max((h(j) for j in cons), default=0)
        return memo[i]
    return [h(i) for i in range(len(code))]

def list_schedule(code):
    deps, hgt = build_dag(code), heights(code, build_dag(code))
    done_at, order, cycle = {}, [], 1
    remaining = set(range(len(code)))
    while remaining:
        ready = [i for i in remaining
                 if all(d in done_at and done_at[d] <= cycle for d in deps[i])]
        if not ready:
            cycle += 1
            continue
        pick = max(ready, key=lambda i: (hgt[i], -i))
        done_at[pick] = cycle + LAT[code[pick].mnem] - 1
        order.append(pick)
        remaining.discard(pick)
        cycle += 1
    return order

REGS = {'i': 'rsi', 'q': 'rdi', 'r': 'r8', 't': 'rcx',
        'k': 'eax', 'm': 'edx', 'w': 'ebx'}

tac = [
    TACInstr('*',        't', 'i', '#8'),
    TACInstr('+',        'k', 't', 'q'),
    TACInstr('load_arr', 'x', 'arr', 'i'),
    TACInstr('-',        'm', 'k', 'r'),
    TACInstr('+',        'y', 'x', 'm'),
]

code = select(tac, REGS)
print('=== selected (program order) ===')
for i, ins in enumerate(code):
    print(f'  {i}: [{LAT[ins.mnem]:>2}cy] {ins.text}')

order = list_schedule(code)
print('=== scheduled ===')
for step, i in enumerate(order, 1):
    print(f'  issue@{step}: {code[i].text}')

প্রত্যাশিত আউটপুট-এর মূল পাঠ: t ← i*8 lea-tile হয়ে ১cy; load_arr scale-4 folded; আর scheduler dependency-free, দীর্ঘ-latency instruction- কে সামনে টেনে critical path ছোট করে — before/after issue cycle তুলনা করলেই লাভ দেখা যায়।

নিজে বাড়ান: (১) multi-issue (2-wide) resource model — scheduler কীভাবে বদলায়; (২) flags-dependency edge (cmp→jcc) যোগ করে দেখান flag-clobber মাঝে ঢুকলে cmp re-issue হয়; (৩) superoptimizer spirit-এ brute-force 4-instruction windows-এর best sequence খোঁজা (Massalin-এর 1987 paper-এর toy version)।