Register Allocation — অসীম temporary, সসীম register

আগের লেসনের কোডের সাথে জোড়া দিন — নিচে শুধু allocation layer:

class InterferenceGraph:
    def __init__(self):
        self.adj = {}

    def add(self, u, v):
        if u != v:
            self.adj.setdefault(u, set()).add(v)
            self.adj.setdefault(v, set()).add(u)

    def nodes(self):
        return set(self.adj)

    def neighbors(self, v):
        return self.adj.get(v, set())

    def edges(self):
        return sorted({tuple(sorted((u, w)))
                       for u in self.adj for w in self.adj[u]})

    def without(self, v):                 # v + edges বাদ দেওয়া shallow copy
        g2 = InterferenceGraph()
        g2.adj = {u: ns - {v} for u, ns in self.adj.items() if u != v}
        return g2


def build_interference(cfg, params):
    ig = InterferenceGraph()
    for p in params:                      # parameter clique: entry-তে
        for q in params:                  # parallel definition
            ig.add(p, q)
    for b in cfg.blocks:                  # lesson 9-এর live_out ব্যবহার
        live = set(live_out[b.bid])
        for ins in reversed(b.instrs):
            if ins.dest:
                for v in live:
                    ig.add(ins.dest, v)   # def interferes with live-out
                live.discard(ins.dest)
            live.update(ins.uses())
    return ig


def simplify_select(ig, k):
    work = InterferenceGraph()
    work.adj = {v: set(ns) for v, ns in ig.adj.items()}
    stack = []
    while work.adj:
        simple = sorted(v for v in work.adj if len(work.adj[v]) < k)
        if simple:                           # SIMPLIFY
            v = ('+', simple[0])             # deterministic: alphabetical
        else:                                # POTENTIAL SPILL (optimistic)
            v = ('*', min(work.adj,          # highest degree, alpha tie-break
                          key=lambda n: (-len(work.adj[n]), n)))
        stack.append(v)
        work = work.without(v[1])
    color, spilled = {}, []
    for mark, v in reversed(stack):          # SELECT: উল্টো ক্রমে
        taken = {color[n] for n in ig.neighbors(v) if n in color}
        free = [c for c in range(k) if c not in taken]
        if free:
            color[v] = free[0]
        else:
            spilled.append(v)                # optimistic attempt failed
    return color, spilled


params = ['a', 'b']
program = [
    TACInstr('+',     'c', 'a', '#1'),
    TACInstr('*',     'd', 'b', '#2'),
    TACInstr('if_<',  None, 'c', 'd', 'L_then'),
    TACInstr('copy',  'e', '#0'),
    TACInstr('goto',  None, None, None, 'L_end'),
    TACInstr('label', None, None, None, 'L_then'),
    TACInstr('+',     'e', 'c', 'd'),
    TACInstr('label', None, None, None, 'L_end'),
    TACInstr('+',     't', 'a', 'c'),
    TACInstr('+',     'u', 't', 'e'),
    TACInstr('return', None, 'u'),
]

cfg = build_cfg(program)
live_in, live_out = solve_liveness(cfg)
ig = build_interference(cfg, params)
print('edges:', ', '.join(f'{u}-{w}' for u, w in ig.edges()))

for k in (3, 2):
    color, spilled = simplify_select(ig, k)
    tag = ', '.join(f'{v}=r{color[v]}' for v in sorted(color))
    print(f'k={k}: {tag}' + (f'  SPILL: {sorted(spilled)}' if spilled else '  (no spill)'))

প্রত্যাশিত output (t, u = return a+c+e chain-এর দুই temporary; তাদের ছোট range সহজেই color হয়):

edges: a-b, a-c, a-d, a-e, b-c, c-d, c-e, e-t
k=3: a=r2, b=r1, c=r0, d=r1, e=r1, t=r0, u=r0  (no spill)
k=2: b=r0, c=r1, d=r0, e=r0, t=r0, u=r0  SPILL: ['a']

example section-এর টেবিলের হাতে-trace-এর সাথে মিলিয়ে নিন — একই graph, একই ফয়সালা।

নিজে বাড়ান: (১) spill rewrite pass — spilled var-এর use-এ reload TAC বসান, rebuild করে দেখান retry-তে সব color হয়; (২) spill-cost weight (loop depth × 10^depth) দিয়ে potential-pick বদলান; (৩) conservative coalescing: move-এর দুই node merge করে দেখান degree-check কেন দরকার।