Optimization — কোনটা safe, কোনটা profitable, কোনটা fast

আগের লেসনের cfg_liveness.py-এর TACInstr, BasicBlock, build_cfg একই ফাইলে রাখুন — নিচের কোড সরাসরি তার উপর চলে।

ARITH = {'+', '-', '*'}                      # toy ভাষা: শুধু int!

def lit(x):                                  # '#12'-জাতীয় literal?
    return x is not None and x.startswith('#')

def val(x):
    return int(x[1:])

def simplify_algebraic(op, a, b):
    """শুধু integer toy ভাষার জন্য SAFE identities"""
    if op == '+' or op == '-':
        if lit(b) and val(b) == 0:
            return a                         # x ± 0 → x
        if op == '+' and lit(a) and val(a) == 0:
            return b                         # 0 + x → x
    if op == '*':
        if (lit(a) and val(a) == 0) or (lit(b) and val(b) == 0):
            return '#0'                      # x*0 → 0 (float হলে ভুল হত!)
        if lit(a) and val(a) == 1:
            return b                         # 1*x → x
        if lit(b) and val(b) == 1:
            return a                         # x*1 → x
    return None

def fold_pass(blocks):
    """per-block constant folding + propagation + algebraic simplify"""
    killed = 0
    for blk in blocks:
        env = {}                             # var → known '#const'
        kept = []
        for ins in blk.instrs:
            if ins.op == 'label':
                env.clear()                  # join-point: conservative reset
                kept.append(ins)
                continue
            if ins.op in ARITH and ins.dest:
                a, b = env.get(ins.a, ins.a), env.get(ins.b, ins.b)
                if lit(a) and lit(b):        # pure folding
                    r = {'+': val(a)+val(b), '-': val(a)-val(b),
                         '*': val(a)*val(b)}[ins.op]
                    env[ins.dest] = f'#{r}'
                    killed += 1
                    continue                 # instruction মুছে গেল
                rep = simplify_algebraic(ins.op, a, b)
                if rep is not None:          # identity hit
                    env[ins.dest] = rep
                    kept.append(TACInstr('copy', ins.dest, rep))
                    killed += 1
                    continue
                ins = TACInstr(ins.op, ins.dest, a, b)
                kept.append(ins)
                continue
            if ins.op == 'copy' and lit(env.get(ins.a, ins.a)):
                env[ins.dest] = env.get(ins.a, ins.a)
                killed += 1                  # copy-of-const → env entry
                continue
            kept.append(TACInstr(ins.op, ins.dest,      # বাকিগুলোতে
                                 env.get(ins.a, ins.a), # const ঢোকাও
                                 env.get(ins.b, ins.b), ins.label))
        blk.instrs[:] = kept
    return killed

SIDE_EFFECT = {'print', 'return', 'goto', 'if_>=', 'if_<', 'store'}

def dce(cfg):
    """mark-sweep: side-effect seeds থেকে def-use transitive closure"""
    def_sites = {}
    for b in cfg.blocks:
        for idx, ins in enumerate(b.instrs):
            if ins.dest:
                def_sites.setdefault(ins.dest, []).append((b.bid, idx))
    marked, stack = set(), []
    for b in cfg.blocks:
        for idx, ins in enumerate(b.instrs):
            if ins.op in SIDE_EFFECT:
                marked.add((b.bid, idx)); stack.append((b.bid, idx))
    while stack:                             # MARK phase
        bid, idx = stack.pop()
        for v in cfg.blocks[bid].instrs[idx].uses():
            for site in def_sites.get(v, []):
                if site not in marked:
                    marked.add(site); stack.append(site)
    removed = 0                              # SWEEP phase
    for b in cfg.blocks:
        kept = [i for j, i in enumerate(b.instrs)
                if (b.bid, j) in marked or i.op == 'label']
        removed += len(b.instrs) - len(kept)
        b.instrs[:] = kept
    return removed

demo = [
    TACInstr('copy', 'x', '#6'),
    TACInstr('*',    'y', 'x', '#7'),     # 6*7 → 42
    TACInstr('*',    'z', 'y', '#0'),     # 42*0 → 0 (algebraic)
    TACInstr('+',    'w', 'z', 'y'),
    TACInstr('+',    'v', 'w', 'y'),
    TACInstr('return', None, 'v'),
]
cfg = build_cfg(demo)
before = sum(len(b.instrs) for b in cfg.blocks)
k1 = fold_pass(cfg.blocks); k2 = dce(cfg)
after = sum(len(b.instrs) for b in cfg.blocks)
print(f'আগে: {before} | fold/simplify: -{k1} | DCE: -{k2} | পরে: {after}')
for b in cfg.blocks:
    for ins in b.instrs:
        print(f'  B{b.bid}: {ins.op:6} {ins.dest or ""} {ins.a or ""} {ins.b or ""}')

প্রত্যাশিত output:

আগে: 6 | fold/simplify: -5 | DCE: -0 | পরে: 1
  B0: return #84

example section-এর trace-এর সাথে মিলুন: v-র মান compile time-ই জানা হয়ে গেছে, তাই return-এর operand propagation-এ constant হয়ে গেছে।

নিজে বাড়ান: (১) z ← y * 0.0-জাতীয় float variant যোগ করে দেখান fold আটকে যায়; (২) CSE pass লিখুন — ব্লকে expression→temp map; (৩) LICM: loop header-এ back-edge detect করে invariant তুলুন।