dominance-frontier-ssa-builder

Answer 1

Below is a complete minimal SSA form constructor for a subset of JavaScript. It implements the full pipeline: Lengauer–Tarjan dominator tree → dominance frontiers → ϕ-function insertion at iterated dominance frontiers → variable renaming.

Data Structures

Algorithm Pipeline

1. Lengauer–Tarjan dominators — DFS numbering + semi-dominator computation with path compression via union-find. Runs in near-linear time (O(|V| + |E| \cdot \alpha(|V|))).

2. Dominance frontiers — For each block with ≥2 predecessors, walk up the dominator tree and mark the frontier.

3. ϕ-function insertion — For each variable, collect its definition sites, then iteratively add ϕ-functions at dominance frontier blocks until a fixed point (the iterated dominance frontier).

4. Renaming — Walk the dominator tree pre-order. For each definition, push a fresh version number; for each use, read the current top-of-stack. Fill ϕ-function arguments by mapping predecessor edge indices → current version of the base variable. Pop on exit from each block.

Code

#!/usr/bin/env node

/**
 * Minimal SSA Form Constructor
 * ============================
 * Input:  CFG { entry, blocks: [{ id, instructions, succ, pred }] }
 * Output: CFG with ϕ-nodes inserted and variables renamed to SSA form
 */

// ── 1. Lengauer–Tarjan Dominator Tree ──────────────────────────────────────

function computeDominators(cfg) {
  const { blocks, entry } = cfg;
  const n = blocks.length;

  const semi   = new Int32Array(n);
  const parent = new Int32Array(n);
  const best   = new Int32Array(n);
  const idom   = new Int32Array(n).fill(-1);
  const ancestor = new Int32Array(n).fill(-1);
  const label  = new Int32Array(n);
  const vertex = new Int32Array(n).fill(-1);
  const dfs    = new Int32Array(n).fill(-1);
  const bucket = Array.from({ length: n }, () => []);

  let time = 0;

  function dfsVisit(v) {
    if (dfs[v] !== -1) return;
    dfs[v] = time;
    vertex[time] = v;
    semi[v] = time;
    label[v] = v;
    time++;
    for (const w of blocks[v].succ) {
      if (dfs[w] === -1) { parent[w] = v; dfsVisit(w); }
    }
  }
  dfsVisit(entry);

  function compress(v) {
    if (ancestor[ancestor[v]] !== -1) {
      compress(ancestor[v]);
      if (semi[label[ancestor[v]]] < semi[label[v]])
        label[v] = label[ancestor[v]];
      ancestor[v] = ancestor[ancestor[v]];
    }
  }

  function find(v) {
    if (ancestor[v] === -1) return v;
    compress(v);
    return semi[label[ancestor[v]]] < semi[label[v]]
      ? label[ancestor[v]] : label[v];
  }

  function link(v, w) { ancestor[w] = v; }

  // Reverse DFS order
  for (let i = time - 1; i > 0; i--) {
    const w = vertex[i]; if (w === -1) continue;
    for (const p of blocks[w].pred) {
      if (dfs[p] === -1) continue;
      const u = find(p);
      if (semi[u] < semi[w]) semi[w] = semi[u];
    }
    bucket[vertex[semi[w]]].push(w);
    link(parent[w], w);
    for (const v of bucket[parent[w]]) {
      const u = find(v);
      idom[v] = (semi[u] < semi[v]) ? u : parent[w];
    }
    bucket[parent[w]] = [];
  }

  for (let i = 1; i < time; i++) {
    const w = vertex[i]; if (w === -1) continue;
    if (idom[w] !== vertex[semi[w]]) idom[w] = idom[idom[w]];
  }
  idom[entry] = entry;

  const domTree = Array.from({ length: n }, () => []);
  for (let v = 0; v < n; v++) {
    if (v !== entry && idom[v] !== -1) domTree[idom[v]].push(v);
  }
  return { idom, domTree };
}

// ── 2. Dominance Frontiers ─────────────────────────────────────────────────

function computeDominanceFrontiers(cfg, idom) {
  const n = cfg.blocks.length;
  const frontiers = Array.from({ length: n }, () => new Set());
  for (let b = 0; b < n; b++) {
    const preds = cfg.blocks[b].pred;
    if (preds.length < 2) continue;
    for (const p of preds) {
      let runner = p;
      while (runner !== idom[b] && runner !== -1 && runner !== idom[runner]) {
        frontiers[runner].add(b);
        runner = idom[runner];
      }
    }
  }
  return frontiers.map(s => [...s].sort((a, b) => a - b));
}

// ── 3. ϕ-Function Insertion at Iterated Dominance Frontiers ────────────────

function insertPhiFunctions(cfg, defSites, domFrontiers) {
  const n = cfg.blocks.length;
  const hasPhi = Array.from({ length: n }, () => new Set());
  const worklist = [];

  for (const [v, blocks] of defSites)
    for (const b of blocks) worklist.push({ var: v, block: b });

  while (worklist.length > 0) {
    const { var: v, block: b } = worklist.pop();
    for (const d of domFrontiers[b]) {
      if (!hasPhi[d].has(v)) {
        hasPhi[d].add(v);
        if (!defSites.get(v).has(d)) {
          defSites.get(v).add(d);
          worklist.push({ var: v, block: d });
        }
      }
    }
  }

  for (let b = 0; b < n; b++) {
    if (hasPhi[b].size > 0) {
      const sortedVars = [...hasPhi[b]].sort();
      for (const v of sortedVars) {
        cfg.blocks[b].instructions.unshift({
          op: 'phi', dest: v,
          args: new Array(cfg.blocks[b].pred.length).fill(v),
          blockId: b,
        });
      }
    }
  }
  return hasPhi;
}

// ── 4. Variable Renaming ───────────────────────────────────────────────────

function isVarName(s) {
  return typeof s === 'string' && /^[a-zA-Z_$][a-zA-Z0-9_$]*$/.test(s);
}

function renameVariables(cfg, idom, domTree, entry) {
  const stacks   = new Map();
  const counters = new Map();

  function initVar(name) {
    if (!stacks.has(name)) { stacks.set(name, []); counters.set(name, 0); }
  }

  for (const block of cfg.blocks) {
    for (const insn of block.instructions) {
      if (insn.dest && isVarName(insn.dest)) initVar(insn.dest);
      for (const arg of insn.args) if (isVarName(arg)) initVar(arg);
    }
  }

  const freshName = name => {
    const idx = counters.get(name);
    counters.set(name, idx + 1);
    stacks.get(name).push(idx);
    return `${name}.${idx}`;
  };

  const topName = name => {
    const s = stacks.get(name);
    return (!s || s.length === 0) ? name : `${name}.${s[s.length - 1]}`;
  };

  // phiInfo[blockId] = [{ phiInsn, baseVar, predMap: { predBlock → argIdx } }]
  const phiInfo = new Map();
  for (const block of cfg.blocks) {
    for (const insn of block.instructions) {
      if (insn.op !== 'phi') break;
      if (!phiInfo.has(block.id)) phiInfo.set(block.id, []);
      const baseVar = insn.dest.replace(/\.\d+$/, '');
      const predMap = {};
      for (let ai = 0; ai < insn.args.length; ai++)
        predMap[block.pred[ai]] = ai;
      phiInfo.get(block.id).push({ phiInsn: insn, baseVar, predMap });
    }
  }

  function renameBlock(b) {
    const block = cfg.blocks[b];
    const pushed = [];

    // 4a. Rename ϕ destinations
    for (const insn of block.instructions) {
      if (insn.op === 'phi' && insn.dest && isVarName(insn.dest.replace(/\.\d+$/, ''))) {
        pushed.push(freshName(insn.dest.replace(/\.\d+$/, '')));
        insn.dest = pushed[pushed.length - 1];
      } else if (insn.op !== 'phi') break;
    }

    // 4b. Rename ordinary instructions (uses then defs)
    for (const insn of block.instructions) {
      if (insn.op === 'phi') continue;
      insn.args = insn.args.map(a => isVarName(a) ? topName(a) : a);
      if (insn.dest && isVarName(insn.dest)) {
        pushed.push(freshName(insn.dest));
        insn.dest = pushed[pushed.length - 1];
      }
    }

    // 4c. Fill ϕ arguments in successors
    for (const succId of block.succ) {
      const info = phiInfo.get(succId) || [];
      for (const { phiInsn, baseVar, predMap } of info) {
        const argIdx = predMap[b];
        if (argIdx !== undefined) phiInsn.args[argIdx] = topName(baseVar);
      }
    }

    // 4d. Recurse to children in dominator tree
    for (const child of domTree[b]) renameBlock(child);

    // 4e. Pop names defined in this block
    for (const name of pushed)
      stacks.get(name.replace(/\.\d+$/, '')).pop();
  }

  renameBlock(entry);
  return cfg;
}

// ── 5. Main entry point ────────────────────────────────────────────────────

function buildSSA(cfg) {
  const cloned = JSON.parse(JSON.stringify(cfg));

  const { idom, domTree } = computeDominators(cloned);
  cloned._idom    = idom;
  cloned._domTree = domTree;

  const frontiers = computeDominanceFrontiers(cloned, idom);
  cloned._frontiers = frontiers;

  const defSites = new Map();
  for (let b = 0; b < cloned.blocks.length; b++)
    for (const insn of cloned.blocks[b].instructions)
      if (insn.dest) {
        if (!defSites.has(insn.dest)) defSites.set(insn.dest, new Set());
        defSites.get(insn.dest).add(b);
      }

  insertPhiFunctions(cloned, defSites, frontiers);
  renameVariables(cloned, idom, domTree, cloned.entry);

  return cloned;
}

module.exports = { buildSSA, computeDominators, computeDominanceFrontiers,
                   insertPhiFunctions, renameVariables };

Answer 2

The implementation is in ~/ssa_builder.py and implements the classic Cytron et al. SSA construction algorithm (1991) with these components:

1. IR Layer (CFG, BasicBlock, Instr) — A simplified three-address-code IR with: - Instructions: mov, add/sub/mul (via binop), br, jmp, ret, phi - Each instruction has an opcode, a destination variable, and a tuple of source operands - Basic blocks form a CFG with predecessor/successor edges

2. Dominator Tree — Uses the iterative data-flow algorithm:

dom(b) = {b} ∪ (∩_{p ∈ preds(b)} dom(p))

Iterates to fixed point, then immediate dominator is the proper dominator with the largest dom set (closest to b).

3. Dominance Frontier — For each block with ≥2 predecessors, walks up the dominator tree from each predecessor to the join block's idom, adding the join to each node's DF.

4. Iterated Dominance Frontier (DF⁺) — Fixed-point iteration over DF sets to handle irreducible loops.

5. φ-Function Insertion — For each variable v defined in Defs(v), places φ(v) at every block in the iterated dominance frontier of Defs(v).

6. Variable Renaming — Top-down dominator tree traversal: - Each phi destination gets a fresh SSA name (x_0, x_1, ...) - Each use is replaced with the current top-of-stack for that variable - Each definition pushes a fresh name onto the stack - Phi operands in successor blocks are filled with the current reaching definition

Key design decisions: - Immutable instructions (@dataclass(frozen=True)) — renaming replaces instructions rather than mutating them - Hashable basic blocks (@dataclass(unsafe_hash=True)) — enables set/dict operations needed by DF computation - Variable detection uses dynamic analysis (names used as destinations) rather than heuristics, making it robust across test cases

Answer 3

The implementation is in ~/ssa_builder.py and implements the classic Cytron et al. SSA construction algorithm (1991) with these components:

1. IR Layer (CFG, BasicBlock, Instr) — A simplified three-address-code IR with: - Instructions: mov, add/sub/mul (via binop), br, jmp, ret, phi - Each instruction has an opcode, a destination variable, and a tuple of source operands - Basic blocks form a CFG with predecessor/successor edges

2. Dominator Tree — Uses the iterative data-flow algorithm:

dom(b) = {b} ∪ (∩_{p ∈ preds(b)} dom(p))

Iterates to fixed point, then immediate dominator is the proper dominator with the largest dom set (closest to b).

3. Dominance Frontier — For each block with ≥2 predecessors, walks up the dominator tree from each predecessor to the join block's idom, adding the join to each node's DF.

4. Iterated Dominance Frontier (DF⁺) — Fixed-point iteration over DF sets to handle irreducible loops.

5. φ-Function Insertion — For each variable v defined in Defs(v), places φ(v) at every block in the iterated dominance frontier of Defs(v).

6. Variable Renaming — Top-down dominator tree traversal: - Each phi destination gets a fresh SSA name (x_0, x_1, ...) - Each use is replaced with the current top-of-stack for that variable - Each definition pushes a fresh name onto the stack - Phi operands in successor blocks are filled with the current reaching definition

Key design decisions: - Immutable instructions (@dataclass(frozen=True)) — renaming replaces instructions rather than mutating them - Hashable basic blocks (@dataclass(unsafe_hash=True)) — enables set/dict operations needed by DF computation - Variable detection uses dynamic analysis (names used as destinations) rather than heuristics, making it robust across test cases