Control Flow Graph Construction and Analysis in Compilers

class BasicBlock:
    def __init__(self, block_id):
        self.id = block_id
        self.instructions = []
        self.preds = []
        self.succs = []

    def add_instr(self, instr):
        self.instructions.append(instr)

    def __repr__(self):
        return f"BB{self.id}: {self.instructions}"

def build_cfg(instructions):
    leaders = [0]

    for i, instr in enumerate(instructions):
        if instr.startswith('label'):
            if i > 0:
                leaders.append(i)

    for i, instr in enumerate(instructions):
        if instr.startswith(('goto', 'if', 'return')):
            if i + 1 < len(instructions):
                if i + 1 not in leaders:
                    leaders.append(i + 1)
            target = None
            parts = instr.split()
            for p in parts:
                if p.startswith('L'):
                    target = p
                    break
            if target is not None:
                label_idx = None
                for j, s in enumerate(instructions):
                    if s == f"label {target}":
                        label_idx = j
                        break
                if label_idx is not None and label_idx not in leaders:
                    leaders.append(label_idx)

    leaders = sorted(set(leaders))
    blocks = []
    for idx, leader in enumerate(leaders):
        block = BasicBlock(idx)
        end = leaders[idx + 1] if idx + 1 < len(leaders) else len(instructions)
        for i in range(leader, end):
            block.add_instr(instructions[i])
        blocks.append(block)

    for block in blocks:
        last = block.instructions[-1] if block.instructions else ''
        if last.startswith('goto'):
            target = last.split()[-1]
            for other in blocks:
                if other.instructions and other.instructions[0] == f"label {target}":
                    block.succs.append(other.id)
                    other.preds.append(block.id)
        elif last.startswith('if'):
            target = last.split()[-1]
            for other in blocks:
                if other.instructions and other.instructions[0] == f"label {target}":
                    block.succs.append(other.id)
                    other.preds.append(block.id)
            next_idx = block.id + 1
            if next_idx < len(blocks):
                block.succs.append(next_idx)
                blocks[next_idx].preds.append(block.id)
        else:
            next_idx = block.id + 1
            if next_idx < len(blocks):
                block.succs.append(next_idx)
                blocks[next_idx].preds.append(block.id)

    return blocks

instructions = [
    "label L0",
    "t1 = x > 0",
    "if t1 goto L1",
    "t2 = 0",
    "y = t2",
    "goto L2",
    "label L1",
    "t3 = x + 1",
    "y = t3",
    "label L2",
    "t4 = y + z",
    "w = t4",
]

blocks = build_cfg(instructions)
for block in blocks:
    print(f"{block}  preds={block.preds} succs={block.succs}")

def compute_dominators(cfg, entry=0):
    n = len(cfg)
    dom = [{0} if i == entry else set(range(n)) for i in range(n)]
    changed = True

    while changed:
        changed = False
        for i in range(n):
            if i == entry:
                continue
            new_dom = {i}
            preds = cfg[i].preds
            if preds:
                new_dom |= set.intersection(*[dom[p] for p in preds]) if preds else set()
            if new_dom != dom[i]:
                dom[i] = new_dom
                changed = True

    idom = {}
    for i in range(n):
        if i == entry:
            continue
        dom_without_i = dom[i] - {i}
        candidates = dom_without_i.copy()
        for d in dom_without_i:
            if d != entry and d in dom_without_i:
                for other in dom_without_i:
                    if other != d and other in dom[d]:
                        candidates.discard(other)
        idom[i] = list(candidates)[0] if candidates else entry

    return dom, idom

class CFGNode:
    def __init__(self, block_id):
        self.id = block_id
        self.preds = []
        self.succs = []

cfg = [CFGNode(0), CFGNode(1), CFGNode(2), CFGNode(3)]
cfg[0].succs = [1, 3]
cfg[1].succs = [2]
cfg[2].preds = [1, 3]
cfg[3].succs = [2]
cfg[0].preds = []
cfg[1].preds = [0]
cfg[3].preds = [0]
cfg[2].preds = [1, 3]

dom, idom = compute_dominators(cfg)
for i in range(len(cfg)):
    print(f"BB{i}: dom={dom[i]}, idom={idom.get(i, 'entry')}")

def find_natural_loops(cfg, idom):
    back_edges = []
    for i, block in enumerate(cfg):
        for succ in block.succs:
            if succ in dom[i] if i in dom else False:
                pass
    for target in range(len(cfg)):
        for source in range(len(cfg)):
            if target in cfg[source].succs:
                if target in compute_dominators(cfg)[0][source]:
                    back_edges.append((source, target))

    loops = []
    for source, header in back_edges:
        loop_nodes = {header, source}
        stack = [source]
        while stack:
            node = stack.pop()
            for pred in cfg[node].preds:
                if pred not in loop_nodes and pred != header:
                    loop_nodes.add(pred)
                    stack.append(pred)
        loops.append({'header': header, 'nodes': sorted(loop_nodes), 'back_edge': (source, header)})

    return loops

loops = find_natural_loops(cfg, idom)
for loop in loops:
    print(f"Loop: header=BB{loop['header']}, nodes={loop['nodes']}, "
          f"back_edge=BB{loop['back_edge'][0]} -> BB{loop['back_edge'][1]}")