slige/compiler/middle/cfg.ts

import { Block, BlockId, Fn } from "./mir.ts";

export function createCfg(fn: Fn): Cfg {
    return new CfgBuilder(fn).build();
}

export class Cfg {
    public constructor(
        private graph: Map<BlockId, CfgNode>,
        private entry_: BlockId,
        private exit: BlockId,
    ) {}

    public entry(): Block {
        return this.graph.get(this.entry_)!.block;
    }

    public parents(block: Block): Block[] {
        return this.graph
            .get(block.id)!.parents
            .map((id) => this.graph.get(id)!.block);
    }

    public children(block: Block): Block[] {
        return this.graph
            .get(block.id)!.children
            .map((id) => this.graph.get(id)!.block);
    }

    public index(block: Block): number {
        return this.graph.get(block.id)!.index;
    }

    public print() {
        for (const [id, node] of this.graph.entries()) {
            const l = <T>(v: T[]) => v.map((v) => `${v}`).join(", ");

            console.log(`graph[${id}] = {`);
            console.log(`    id: ${node.block.id},`);
            console.log(`    index: ${node.index},`);
            console.log(`    parents: [${l(node.parents)}],`);
            console.log(`    children: [${l(node.children)}],`);
            console.log(`}`);
        }
    }
}

type CfgNode = {
    block: Block;
    index: number;
    parents: BlockId[];
    children: BlockId[];
};

class CfgBuilder {
    private nodes: [Block, number][] = [];
    private edges: [BlockId, BlockId][] = [];

    public constructor(private fn: Fn) {}

    public build(): Cfg {
        for (
            const [block, index] of this.fn.blocks
                .map((v, i) => [v, i] as const)
        ) {
            this.addNode(block, index);

            const tk = block.ter.kind;
            switch (tk.type) {
                case "error":
                    break;
                case "return":
                    break;
                case "jump":
                    this.addEdge(block.id, tk.target);
                    break;
                case "if":
                    this.addEdge(block.id, tk.truthy);
                    this.addEdge(block.id, tk.falsy);
                    break;
            }
        }

        const graph = new Map<BlockId, CfgNode>();
        for (const [block, index] of this.nodes) {
            const parents = this.edges
                .filter(([_from, to]) => to === block.id)
                .map(([from, _to]) => from);

            const children = this.edges
                .filter(([from, _to]) => from === block.id)
                .map(([_from, to]) => to);

            graph.set(block.id, { block, index, parents, children });
        }

        return new Cfg(graph, this.fn.entry, this.fn.exit);
    }

    private addNode(block: Block, index: number) {
        this.nodes.push([block, index]);
    }

    private addEdge(from: BlockId, to: BlockId) {
        this.edges.push([from, to]);
    }
}