কোড জেনারেশন বেসিকস

# L51-এর (a+b)*(c-d) থেকে জেনারেট হওয়া থ্রি-অ্যাড্রেস কোড (3AC)
code = [
    {"result": "t1", "op": "+", "arg1": "a",  "arg2": "b"},
    {"result": "t2", "op": "-", "arg1": "c",  "arg2": "d"},
    {"result": "t3", "op": "*", "arg1": "t1", "arg2": "t2"},
]

def compute_live_points(code, temp_names):
    """প্রতিটি temp-এর জীবনকাল বের করে -- def_point = instruction i-তে অপারেন্ড পড়ার
    *পরে* (i + 0.5); use_point = instruction i-তে অপারেন্ড পড়ার মুহূর্তে (i)। এই আধা-ধাপ
    টাইমিং একই instruction-এর ভেতরে "আগে পুরনো অপারেন্ড ব্যবহার শেষ, পরে নতুন ফলাফলের জন্ম"
    এই সঠিক ক্রম ধরে রাখে -- নইলে একই instruction-index হওয়ায় ভুলভাবে কনফ্লিক্ট মনে হবে।"""
    def_point = {}
    last_use_point = {}
    for i, instr in enumerate(code):
        for arg in (instr["arg1"], instr["arg2"]):
            if arg in temp_names:
                last_use_point[arg] = i
        if instr["result"] in temp_names:
            def_point[instr["result"]] = i + 0.5
    for t in temp_names:
        if t not in last_use_point:
            last_use_point[t] = def_point[t]
    return def_point, last_use_point

def allocate_registers(code, num_available_registers):
    """অর্ডার-অফ-ফার্স্ট-ডেফিনিশন রেজিস্টার অ্যালোকেশন -- প্রতিটি temp সংজ্ঞায়িত হওয়ার সময়
    একটি ফ্রি রেজিস্টার পায়; একটি temp-এর শেষ ব্যবহার শেষ হলে তার রেজিস্টার মুক্ত হয়ে পরের
    temp রিইউজ করতে পারে।"""
    temp_names = {instr["result"] for instr in code if instr["result"].startswith("t")}
    def_point, last_use_point = compute_live_points(code, temp_names)

    free_regs = list(range(1, num_available_registers + 1))
    active = {}
    allocation = {}
    trace = []

    for i, instr in enumerate(code):
        for arg in (instr["arg1"], instr["arg2"]):
            if arg in temp_names and arg in active and last_use_point[arg] == i:
                freed = active.pop(arg)
                free_regs.append(freed)
                free_regs.sort()
                trace.append(f"  instr{i+1}: {arg}-এর শেষ ব্যবহার শেষ -> R{freed} মুক্ত হলো")

        result = instr["result"]
        if result in temp_names and result not in active:
            if not free_regs:
                raise RuntimeError(f"রেজিস্টার বাজেট শেষ! {result}-এর জন্য spill প্রয়োজন")
            reg = free_regs.pop(0)
            active[result] = reg
            allocation[result] = reg
            trace.append(f"  instr{i+1}: {result} সংজ্ঞায়িত -> R{reg} বরাদ্দ")

    return allocation, def_point, last_use_point, trace

print("3AC:")
for instr in code:
    print(f"  {instr['result']} = {instr['arg1']} {instr['op']} {instr['arg2']}")

NUM_REGISTERS = 2   # ইচ্ছাকৃতভাবে ছোট বাজেট -- মাত্র ২টি রেজিস্টার, ৩টি temp-এর জন্য
allocation, def_point, last_use_point, trace = allocate_registers(code, NUM_REGISTERS)

print(f"\nরেজিস্টার বাজেট: {NUM_REGISTERS}")
print("অ্যালোকেশন ট্রেস:")
for line in trace:
    print(line)

print("\nচূড়ান্ত বরাদ্দ:")
for t, r in allocation.items():
    print(f"  {t} -> R{r}  (জন্ম {def_point[t]}, শেষ ব্যবহার {last_use_point[t]})")

# সঠিকতা যাচাই: কোনো দুটো একসাথে-জীবিত (simultaneously live) temp কি একই রেজিস্টার শেয়ার করছে?
temps = list(allocation.keys())
conflict_found = False
for i in range(len(temps)):
    for j in range(i + 1, len(temps)):
        t1, t2 = temps[i], temps[j]
        s1, e1 = def_point[t1], last_use_point[t1]
        s2, e2 = def_point[t2], last_use_point[t2]
        overlap = max(s1, s2) <= min(e1, e2)
        if overlap and allocation[t1] == allocation[t2]:
            conflict_found = True
            print(f"  ✗ কনফ্লিক্ট: {t1} ও {t2} একসাথে জীবিত থেকেও R{allocation[t1]} শেয়ার করছে!")

print("\nসঠিকতা যাচাই:", "FAIL" if conflict_found else "PASS -- কোনো দুটো একসাথে-জীবিত temp একই রেজিস্টার শেয়ার করেনি")
reused = len(set(allocation.values())) < len(allocation)
print("রিইউজ ঘটেছে কিনা:", "হ্যাঁ -- t1 মারা যাওয়ার পর t3 আবার সেই একই রেজিস্টার নিয়েছে" if reused else "না")