Static Single Assignment Form — SSA in Compiler Design

class SSABuilder:
    def __init__(self):
        self.counter = {}
        self.stack = {}
        self.versions = {}

    def new_version(self, var):
        if var not in self.counter:
            self.counter[var] = 0
            self.stack[var] = []
        self.counter[var] += 1
        version = f"{var}_{self.counter[var]}"
        self.stack[var].append(version)
        return version

    def current_version(self, var):
        if var not in self.stack or not self.stack[var]:
            return var
        return self.stack[var][-1]

    def rename_block(self, block, blocks, phi_assignments):
        for phi_var in phi_assignments.get(block, []):
            self.new_version(phi_var)

        for instr in blocks[block]:
            if '=' in instr:
                parts = instr.split(' = ')
                lhs = parts[0]
                rhs = parts[1]
                renamed_rhs = rhs
                for var in self.extract_vars(rhs):
                    renamed_rhs = renamed_rhs.replace(var, self.current_version(var), 1)
                new_lhs = self.new_version(lhs)
                self.versions[(block, lhs)] = new_lhs
                yield f"{new_lhs} = {renamed_rhs}"

        for succ in self.get_successors(block, blocks):
            for instr in blocks.get(succ, []):
                if instr.startswith('phi'):
                    pass

    def extract_vars(self, expr):
        return [v for v in expr.split() if v.isalpha() and not v.isdigit()]

    def get_successors(self, block, blocks):
        last = blocks[block][-1] if blocks[block] else ''
        if 'goto' in last:
            parts = last.split('goto')
            targets = []
            for p in parts[1].split(','):
                targets.append(p.strip())
            return targets
        return []

blocks = {
    'entry': ['x = 1', 'goto loop'],
    'loop': ['x = phi(x, x)', 't = x + 1', 'if t < 10 goto loop', 'goto exit'],
    'exit': ['y = x']
}

builder = SSABuilder()
for block, instrs in blocks.items():
    print(f"\nBlock: {block}")
    for result in builder.rename_block(block, blocks, {}):
        print(f"  {result}")

def insert_phi_nodes(cfg, variables):
    phi_nodes = {}
    for var in variables:
        definitions = [b for b, blk in cfg.items()
                      if any(var in instr and '=' in instr
                      and instr.split('=')[0].strip() == var
                      for instr in blk)]
        worklist = list(definitions)
        while worklist:
            block = worklist.pop(0)
            for successor in cfg.get(block, [])[-1:] if isinstance(block, str) else []:
                phi_nodes.setdefault(successor, set()).add(var)
                if successor not in definitions:
                    definitions.append(successor)
                    worklist.append(successor)
    return phi_nodes

cfg = {
    'entry': ['x = 0', 'goto A'],
    'A': ['goto B', 'goto C'],
    'B': ['x = x + 1', 'goto D'],
    'C': ['x = x + 2', 'goto D'],
    'D': ['y = x']
}

phi_needed = insert_phi_nodes(cfg, ['x'])
for block, vars_needed in phi_needed.items():
    for var in vars_needed:
        print(f"phi({var}) needed at block {block}")

def ssa_constant_propagation(ssa_program):
    known_constants = {}
    optimized = []

    for instr in ssa_program:
        if '=' in instr:
            lhs, rhs = instr.split(' = ')
            rhs_parts = rhs.split()

            if len(rhs_parts) == 1 and rhs_parts[0].isdigit():
                known_constants[lhs] = int(rhs_parts[0])
                optimized.append(instr)
            elif len(rhs_parts) == 3:
                arg1 = known_constants.get(rhs_parts[0], rhs_parts[0])
                op = rhs_parts[1]
                arg2 = known_constants.get(rhs_parts[2], rhs_parts[2])
                if isinstance(arg1, int) and isinstance(arg2, int):
                    result = {'+': arg1 + arg2, '-': arg1 - arg2,
                              '*': arg1 * arg2, '/': arg1 // arg2}.get(op)
                    if result is not None:
                        known_constants[lhs] = result
                        optimized.append(f"{lhs} = {result}")
                        continue
                optimized.append(f"{lhs} = {arg1} {op} {arg2}")
    return optimized

ssa_code = [
    "x_1 = 5",
    "y_1 = 3",
    "z_1 = x_1 + y_1",
    "w_1 = z_1 * 2",
    "a_1 = w_1 + x_1]
]

result = ssa_constant_propagation(ssa_code)
for instr in result:
    print(instr)