30. Building a Source Compiler: Contracts, CFGs, and SSA Construction
The analysis exercise in Chapter 21 began with a hand-written graph. This chapter builds the graph
from source. The implementation is minicc, a separate compiler whose purpose is to expose control
flow, effects, verification, and backend decisions that tensor expressions can hide. It complements
uopc; it does not replace its autodiff or GPU pipeline.
Run the complete example before reading the implementation:
.venv/bin/python -m minicc
.venv/bin/python -m pytest tests/test_minicc.py -q
The example compiles a loop with a conditional accumulation and obtains 87 through an SSA interpreter, a register-constrained machine, and generated native C. Agreement across these paths is useful, but not sufficient by itself: they share the IR. The tests also execute trusted source programs with Python as an independent oracle over a small range that avoids overflow. Overflow and memory errors have separate tests against the compiler's explicitly different semantics.
30.1 Define the language before optimizing it
The source syntax is a restricted Python function, parsed by Python's ast module. This delegates
lexing and parsing, not execution or language semantics. No source function is evaluated by the
compiler. Function calls, comprehensions, imports, general objects, exceptions, chained comparisons,
short-circuit and/or, and unsupported statements are rejected on the lowered path.
The supported language includes scalar variables, integer constants, +, -, *, comparisons,
not, assignment, if, while, break, continue, and explicit return. Buffer parameters use
an annotation naming buffer; scalar parameters may be unannotated or annotated int. Buffers are
rank-one indexed storage. An integer result is required on every structurally reachable exit.
Unreachable statements after a terminator need not be lowered; this is not a general Python validator.
Every scalar value is signed i32. Arithmetic wraps modulo 2^32 and is reinterpreted as signed.
Comparisons operate on those signed values and produce 0 or 1. A condition is true when nonzero.
Input scalar integers and constants are normalized to that domain. For example, 2147483647+1
is -2147483648. A compiler that tests only tiny positive values could accidentally implement
mathematical integers or undefined C overflow without noticing.
Buffer indices must be in [0,length). Negative indexing does not have Python's meaning. A failed
access reports a bounds error; earlier stores remain visible, and later instructions do not execute.
Two buffer arguments may overlap. The compiler therefore cannot assume that storing through a leaves
loads through b unchanged. No generated restrict promise is made.
These choices define optimization legality. Removing an unused add is valid. Removing an unused load is not generally valid, because the load can fail. Reordering a store before a potentially failing load can change the state visible after an error. Treat trapping and memory effects as part of the program, rather than incidental implementation details.
30.2 An inspectable intermediate representation
A function owns parameters, named blocks, and an entry label. An instruction has an operation, an optional result, and operands that are either integer literals or value names. Stores have no scalar result. A terminator is a jump, conditional branch, or return.
A block's instruction order preserves memory effects. The representation does not yet have memory SSA or general alias analysis: it establishes safety by declining to reorder accesses. That is a useful baseline against which a future alias analysis must prove additional transformations.
"""Small control-flow IR with explicit effects and signed, wrapping i32 arithmetic."""
from __future__ import annotations
from dataclasses import dataclass, field
from enum import Enum
Operand = str | int
class Kind(Enum):
I32 = "i32"
BUFFER = "buffer"
@dataclass(frozen=True)
class Parameter:
name: str
kind: Kind = Kind.I32
@dataclass
class Instruction:
op: str
dest: str | None
args: tuple[Operand, ...]
@dataclass
class Phi:
base: str
dest: str
incoming: dict[str, Operand] = field(default_factory=dict)
@dataclass
class Terminator:
op: str
args: tuple[Operand, ...] = ()
targets: tuple[str, ...] = ()
@dataclass
class Block:
instructions: list[Instruction] = field(default_factory=list)
terminator: Terminator | None = None
phis: list[Phi] = field(default_factory=list)
@dataclass
class Function:
name: str
parameters: tuple[Parameter, ...]
blocks: dict[str, Block]
entry: str = "entry"
ssa: bool = False
PURE = {"copy": 1, "add": 2, "sub": 2, "mul": 2, "lt": 2, "le": 2, "eq": 2, "ne": 2}
EFFECTS = {"load": 2, "store": 3} # Even an unused load can raise a bounds error.
def i32(value: int) -> int:
value = int(value) & 0xffffffff
return value - 0x100000000 if value & 0x80000000 else value
def alu(op: str, args) -> int:
if op == "copy": return i32(args[0])
a, b = args
if op == "add": return i32(a + b)
if op == "sub": return i32(a - b)
if op == "mul": return i32(a * b)
if op == "lt": return int(a < b)
if op == "le": return int(a <= b)
if op == "eq": return int(a == b)
if op == "ne": return int(a != b)
raise ValueError(f"unknown arithmetic operation: {op}")
def successors(function, name):
term = function.blocks[name].terminator
if term is None: raise ValueError(f"unterminated block: {name}")
return term.targets
def graph(function):
if function.entry not in function.blocks: raise ValueError("missing entry")
predecessors = {name: set() for name in function.blocks}
for name in function.blocks:
for target in successors(function, name):
if target not in function.blocks: raise ValueError(f"unknown block: {target}")
predecessors[target].add(name)
reachable, todo = set(), [function.entry]
while todo:
name = todo.pop()
if name in reachable: continue
reachable.add(name)
todo.extend(successors(function, name))
return predecessors, reachable
def prune(function):
_, reachable = graph(function)
function.blocks = {name: block for name, block in function.blocks.items() if name in reachable}
predecessors, _ = graph(function)
for name, block in function.blocks.items():
for phi in block.phis:
phi.incoming = {p: value for p, value in phi.incoming.items() if p in predecessors[name]}
return function
def operands(args): return {arg for arg in args if isinstance(arg, str)}
def format_ir(function):
params = ", ".join(f"{p.name}: {p.kind.value}" for p in function.parameters)
lines = [f"{'ssa ' if function.ssa else ''}func {function.name}({params}):"]
for name, block in function.blocks.items():
lines.append(f"{name}:")
for phi in block.phis:
incoming = ", ".join(f"{p}: {v}" for p, v in sorted(phi.incoming.items()))
lines.append(f" {phi.dest} = phi [{incoming}]")
for instruction in block.instructions:
lhs = f"{instruction.dest} = " if instruction.dest else ""
lines.append(f" {lhs}{instruction.op} {', '.join(map(str, instruction.args))}")
term = block.terminator
if term is not None: lines.append(f" {term.op} {', '.join(map(str, (*term.args, *term.targets)))}")
return "\n".join(lines)
Trace: lower x=a[0]; b[0]=2; return x. The return uses the loaded scalar x even if a and b alias.
Change it to b[0]=2; return a[0]; now the aliasing case returns the updated value. An expression-level
common-subexpression rule must not identify the two loads across an intervening possibly aliased store.
30.3 Constructing blocks from structured syntax
An assignment emits its expression's operations followed by a copy into the mutable variable name. Temporary names are compiler-generated and cannot collide with source identifiers. Right-hand-side expressions are lowered before the assignment target, preserving the chosen evaluation order.
An if creates then, else, and merge blocks. Both arms end by jumping to the merge unless they
already returned or transferred control. If both arms return, the merge is unreachable and is removed.
A while creates a header, body, and exit. The current block jumps to the header; the header computes
the condition and branches; a normal body completion jumps back to the header.
A stack of (header,exit) pairs implements nested continue and break: they target the innermost
loop. After emitting any terminator, the frontend stops appending statements to that path. This
prevents an apparent assignment after a return from becoming an executed side effect.
"""Lower a deliberately restricted Python AST to mutable-variable control-flow IR.
Python supplies lexing/parsing only. minicc defines its own i32 and buffer semantics.
Supported: assignments, integer expressions/comparisons, if, while, break, continue,
return, buffer indexing/stores. Unsupported Python syntax is rejected, never executed.
"""
import ast
from minicc.ir import Block, Function, Instruction, Kind, Parameter, Terminator, i32, prune
class Frontend:
def __init__(self, source):
module = ast.parse(source)
if len(module.body) != 1 or not isinstance(module.body[0], ast.FunctionDef):
raise ValueError("source must contain exactly one function")
self.node = node = module.body[0]
args = node.args
if node.decorator_list or args.posonlyargs or args.kwonlyargs or args.defaults or args.kw_defaults or args.vararg or args.kwarg:
raise ValueError("decorators, defaults, and special argument forms are unsupported")
if node.returns is not None and (not isinstance(node.returns, ast.Name) or node.returns.id != "int"):
raise ValueError("return annotation must be int")
parameters = []
for arg in args.args:
if arg.annotation is None: kind = Kind.I32
elif isinstance(arg.annotation, ast.Name) and arg.annotation.id in ("int", "buffer"):
kind = Kind.BUFFER if arg.annotation.id == "buffer" else Kind.I32
else: raise ValueError("parameter annotations must be int or buffer")
parameters.append(Parameter(arg.arg, kind))
if len({p.name for p in parameters}) != len(parameters): raise ValueError("duplicate parameter")
self.function = Function(node.name, tuple(parameters), {"entry": Block()})
self.buffers = {p.name for p in parameters if p.kind == Kind.BUFFER}
self.current, self.counter, self.temp_counter = "entry", 0, 0
self.loops = []
@property
def block(self): return self.function.blocks[self.current]
def new_block(self, hint):
self.counter += 1
name = f"{hint}_{self.counter}"
self.function.blocks[name] = Block()
return name
def emit(self, op, *args):
self.temp_counter += 1
name = f"$t{self.temp_counter}"
self.block.instructions.append(Instruction(op, name, args))
return name
def scalar_name(self, node):
if not isinstance(node, ast.Name) or node.id in self.buffers: raise ValueError("expected scalar variable")
return node.id
def address(self, node):
if not isinstance(node, ast.Subscript) or not isinstance(node.value, ast.Name) or node.value.id not in self.buffers:
raise ValueError("indexing requires a buffer parameter")
return node.value.id, self.expression(node.slice)
def expression(self, node):
if isinstance(node, ast.Constant) and type(node.value) in (int, bool): return i32(node.value)
if isinstance(node, ast.Name): return self.scalar_name(node)
if isinstance(node, ast.Subscript): return self.emit("load", *self.address(node))
if isinstance(node, ast.UnaryOp):
if isinstance(node.op, ast.USub): return self.emit("sub", 0, self.expression(node.operand))
if isinstance(node.op, ast.Not): return self.emit("eq", self.expression(node.operand), 0)
if isinstance(node, ast.BinOp):
operations = {ast.Add: "add", ast.Sub: "sub", ast.Mult: "mul"}
if type(node.op) in operations:
return self.emit(operations[type(node.op)], self.expression(node.left), self.expression(node.right))
if isinstance(node, ast.Compare) and len(node.ops) == 1:
operations = {ast.Lt: "lt", ast.LtE: "le", ast.Eq: "eq", ast.NotEq: "ne", ast.Gt: "lt", ast.GtE: "le"}
op = type(node.ops[0])
if op in operations:
left, right = self.expression(node.left), self.expression(node.comparators[0])
if op in (ast.Gt, ast.GtE): left, right = right, left
return self.emit(operations[op], left, right)
raise ValueError(f"unsupported expression: {ast.dump(node)}")
def statements(self, statements):
for node in statements:
if self.block.terminator is not None: break
self.statement(node)
def statement(self, node):
if isinstance(node, ast.Assign) and len(node.targets) == 1:
value = self.expression(node.value)
target = node.targets[0]
if isinstance(target, ast.Name):
self.block.instructions.append(Instruction("copy", self.scalar_name(target), (value,)))
elif isinstance(target, ast.Subscript):
self.block.instructions.append(Instruction("store", None, (*self.address(target), value)))
else: raise ValueError("unsupported assignment target")
elif isinstance(node, ast.AugAssign) and isinstance(node.target, ast.Name):
name = self.scalar_name(node.target)
operations = {ast.Add: "add", ast.Sub: "sub", ast.Mult: "mul"}
if type(node.op) not in operations: raise ValueError("unsupported augmented operation")
self.block.instructions.append(Instruction(operations[type(node.op)], name, (name, self.expression(node.value))))
elif isinstance(node, ast.Return) and node.value is not None:
self.block.terminator = Terminator("return", (self.expression(node.value),))
elif isinstance(node, ast.If):
condition = self.expression(node.test)
yes, no, merge = self.new_block("then"), self.new_block("else"), self.new_block("merge")
self.block.terminator = Terminator("branch", (condition,), (yes, no))
for name, statements in ((yes, node.body), (no, node.orelse)):
self.current = name
self.statements(statements)
if self.block.terminator is None: self.block.terminator = Terminator("jump", targets=(merge,))
self.current = merge
elif isinstance(node, ast.While) and not node.orelse:
head, body, end = self.new_block("while"), self.new_block("body"), self.new_block("end")
self.block.terminator = Terminator("jump", targets=(head,))
self.current = head
condition = self.expression(node.test)
self.block.terminator = Terminator("branch", (condition,), (body, end))
self.loops.append((head, end))
self.current = body
self.statements(node.body)
if self.block.terminator is None: self.block.terminator = Terminator("jump", targets=(head,))
self.loops.pop()
self.current = end
elif isinstance(node, (ast.Break, ast.Continue)):
if not self.loops: raise ValueError("break/continue outside a loop")
self.block.terminator = Terminator("jump", targets=(self.loops[-1][1 if isinstance(node, ast.Break) else 0],))
elif isinstance(node, ast.Pass): pass
else: raise ValueError(f"unsupported statement: {ast.dump(node)}")
def lower(self):
self.statements(self.node.body)
# Unreachable merge blocks may remain after both arms return. Give all blocks
# a structural terminator, then prune. Reachable fallthrough is rejected.
for block in self.function.blocks.values():
if block.terminator is None: block.terminator = Terminator("missing_return")
prune(self.function)
if any(b.terminator.op == "missing_return" for b in self.function.blocks.values()):
raise ValueError("function may fall through without returning")
return self.function
def lower(source): return Frontend(source).lower()
Exercise: draw the graph for a loop whose body contains an early continue, a nested loop, and
an early return. Identify every backedge and the destination of each break. Compare your graph with
format_ir(lower(source)), then execute the mutable CFG before introducing SSA.
30.4 Definite assignment is a must analysis
Consider a variable x assigned only in one arm of an unknown branch, then used at the merge. A may-have-been-assigned analysis is insufficient. Every predecessor must establish x. For each block, intersect predecessor OUT sets, then add definitions performed by the block:
IN(entry) = parameters
IN(b) = intersection(OUT(p) for p in predecessors(b))
OUT(b) = IN(b) union DEF(b)
Initialize non-entry sets to the universe of names and iterate downward to a fixed point. Using the empty set would compute the wrong extremal solution for some cycles. After convergence, scan each block in order, checking every use before adding its instruction's result to the defined set.
A loop that assigns x only in its body cannot establish x after the loop, because the loop may
execute zero times. An assignment x=x+1 cannot establish the old x required by its own right-hand
side. The tests exercise both errors. This conservative analysis runs before branch optimization;
it can reject source that is safe only because a later constant-propagation pass could prove a
branch always executes. That restriction is explicit rather than a hidden inconsistency.
30.5 Dominators, immediate dominators, and frontiers
The fixed-point dominator sets from Chapter 21 let us form a tree. For each non-entry block b, its immediate dominator is the strict dominator nearest to b. Strict dominators form a chain; in this implementation, the one with the deepest dominator set is the nearest.
The dominance frontier of d contains blocks where paths from the region dominated by d meet a path not strictly dominated by d. At a diamond merge, each arm has the merge in its frontier. A loop header can belong to its own frontier: it dominates the backedge source but does not strictly dominate itself. That self-frontier is how a loop-carried assignment discovers its header phi.
For each join b and predecessor p, walk from p up the immediate-dominator tree until reaching
idom(b), placing b in each visited node's frontier. Analyze reachable blocks only, and require a
separate entry without predecessors to make the initial parameter definitions unambiguous.
"""Fixed-point dominance/liveness, definite assignment, and IR/SSA verification."""
from minicc.ir import EFFECTS, PURE, Kind, graph, operands, successors
def dominators(function):
predecessors, reachable = graph(function)
entry = function.entry
result = {b: ({b} if b == entry else set(reachable)) for b in reachable}
while True:
changed = False
for b in sorted(reachable - {entry}):
value = {b} | set.intersection(*(result[p] for p in predecessors[b] & reachable))
if value != result[b]: result[b], changed = value, True
if not changed: return result
def dominance_tree(function):
dom = dominators(function)
immediate = {b: max(dom[b] - {b}, key=lambda d: len(dom[d])) for b in dom if b != function.entry}
children = {b: [] for b in dom}
for b, parent in immediate.items(): children[parent].append(b)
for values in children.values(): values.sort()
return immediate, children
def dominance_frontiers(function):
predecessors, reachable = graph(function)
immediate, _ = dominance_tree(function)
result = {b: set() for b in reachable}
for b in reachable:
if len(predecessors[b] & reachable) < 2: continue
for parent in predecessors[b] & reachable:
runner = parent
while runner != immediate.get(b):
result[runner].add(b)
if runner not in immediate: break
runner = immediate[runner]
return result
def liveness(function):
_, reachable = graph(function)
uses, defs = {}, {}
for name in reachable:
block = function.blocks[name]
defined, used = {p.dest for p in block.phis}, set()
for instruction in block.instructions:
used |= operands(instruction.args) - defined
if instruction.dest is not None: defined.add(instruction.dest)
used |= operands(block.terminator.args) - defined
uses[name], defs[name] = used, defined
incoming, outgoing = {b: set() for b in reachable}, {b: set() for b in reachable}
while True:
changed = False
for b in sorted(reachable, reverse=True):
live = set()
for target in successors(function, b):
block = function.blocks[target]
live |= (incoming[target] - {p.dest for p in block.phis}) | operands(p.incoming[b] for p in block.phis)
value = uses[b] | (live - defs[b])
if value != incoming[b] or live != outgoing[b]: incoming[b], outgoing[b], changed = value, live, True
if not changed: return incoming, outgoing
def definite_assignment(function):
predecessors, reachable = graph(function)
parameters = {p.name for p in function.parameters}
definitions = {b: {i.dest for i in function.blocks[b].instructions if i.dest is not None} for b in reachable}
universe = parameters | set.union(set(), *definitions.values())
incoming = {b: (set(parameters) if b == function.entry else set(universe)) for b in reachable}
outgoing = {b: incoming[b] | definitions[b] for b in reachable}
while True:
changed = False
for b in sorted(reachable):
value = set(parameters) if b == function.entry else set.intersection(*(outgoing[p] for p in predecessors[b] & reachable))
after = value | definitions[b]
if value != incoming[b] or after != outgoing[b]: incoming[b], outgoing[b], changed = value, after, True
if not changed: break
for name in reachable:
defined = set(incoming[name])
block = function.blocks[name]
for instruction in block.instructions:
missing = operands(instruction.args) - defined
if missing: raise ValueError(f"possibly uninitialized in {name}: {sorted(missing)}")
if instruction.dest is not None: defined.add(instruction.dest)
missing = operands(block.terminator.args) - defined
if missing: raise ValueError(f"possibly uninitialized in {name}: {sorted(missing)}")
def verify(function):
predecessors, reachable = graph(function)
if reachable != set(function.blocks): raise ValueError("prune unreachable blocks before verification")
if predecessors[function.entry]: raise ValueError("entry must not have predecessors")
parameters = {p.name: p.kind for p in function.parameters}
if len(parameters) != len(function.parameters): raise ValueError("duplicate parameter")
definitions = {p.name: (function.entry, -2) for p in function.parameters}
buffers = {name for name, kind in parameters.items() if kind == Kind.BUFFER}
for name, block in function.blocks.items():
if block.phis and not function.ssa: raise ValueError("phis require SSA form")
for phi in block.phis:
if set(phi.incoming) != predecessors[name]: raise ValueError(f"phi edge mismatch in {name}")
for position, instruction in enumerate(block.instructions):
if any(type(arg) not in (int, str) for arg in instruction.args): raise ValueError("operands must be i32 literals or value names")
if any(isinstance(arg, int) and not -(2**31) <= arg < 2**31 for arg in instruction.args): raise ValueError("literal outside i32 domain")
arity = (PURE | EFFECTS).get(instruction.op)
if arity is None or len(instruction.args) != arity: raise ValueError(f"invalid instruction: {instruction}")
if (instruction.dest is None) != (instruction.op == "store"): raise ValueError("invalid instruction result")
if instruction.dest in buffers: raise ValueError("cannot redefine buffer parameter")
if instruction.op in EFFECTS:
if instruction.args[0] not in buffers: raise ValueError("memory operation requires a buffer")
scalar_args = instruction.args[1:]
else: scalar_args = instruction.args
if operands(scalar_args) & buffers: raise ValueError("buffer used as scalar")
term = block.terminator
if term.op not in ("return", "branch", "jump"): raise ValueError("invalid terminator")
if len(term.args) != (0 if term.op == "jump" else 1) or len(term.targets) != {"return": 0, "branch": 2, "jump": 1}[term.op]:
raise ValueError("invalid terminator arity")
if any(type(arg) not in (int, str) for arg in term.args): raise ValueError("invalid terminator operand")
if any(isinstance(arg, int) and not -(2**31) <= arg < 2**31 for arg in term.args): raise ValueError("literal outside i32 domain")
if operands(term.args) & buffers: raise ValueError("buffer used as scalar condition or return")
if function.ssa:
for position, dest in [(-1, p.dest) for p in block.phis] + [(i, instruction.dest) for i, instruction in enumerate(block.instructions) if instruction.dest is not None]:
if dest in definitions: raise ValueError(f"duplicate SSA definition: {dest}")
definitions[dest] = (name, position)
if not function.ssa:
definite_assignment(function)
return
dom = dominators(function)
def check(args, block, position):
for arg in args:
if isinstance(arg, int):
if not -(2**31) <= arg < 2**31: raise ValueError("literal outside i32 domain")
continue
if arg not in definitions: raise ValueError(f"undefined SSA value: {arg}")
origin, index = definitions[arg]
if origin not in dom[block] or (origin == block and index >= position):
raise ValueError(f"{arg} does not dominate use in {block}")
for name, block in function.blocks.items():
for phi in block.phis:
if operands(phi.incoming.values()) & buffers: raise ValueError("buffer phi unsupported")
for parent, value in phi.incoming.items(): check((value,), parent, len(function.blocks[parent].instructions))
for position, instruction in enumerate(block.instructions): check(instruction.args, name, position)
check(block.terminator.args, name, len(block.instructions))
The same module verifies block structure, instruction arity, buffer/scalar use, literal range, unique SSA definitions, phi edge sets, and dominance of ordinary and edge uses. Verification is part of the pipeline. A malformed program should fail close to the pass that created it, rather than survive until a native crash.
30.6 Phi placement needs an iterated frontier
For a variable with definitions in blocks D, put phis at their dominance frontiers. A newly inserted phi is itself a definition and may require another phi in a further frontier. Continue until no new placement is needed. This is the iterated dominance frontier.
Placing every possible phi is correct but noisy. Pruned SSA inserts one only when the original variable is live into the candidate block. If both arms assign a dead variable that is never read, the merge needs no phi. Compute pre-SSA liveness before placement; there are no phi edge uses yet.
For the running example, i and total receive header phis joining initial values with backedge values. The conditional update of total receives a second phi at the branch merge. The result of that merge feeds total's loop-header phi. Placing phis only at the first visible diamond would miss the loop-carried value.
30.7 Renaming with scoped stacks
Maintain one stack of current SSA versions per mutable variable. Parameters seed their stacks. Walking the dominator tree, first assign names to block phis, then rewrite instruction operands using current stack tops and push fresh names for definitions. After the terminator, fill every successor phi's incoming operand for this edge from the current stacks.
Recursively process dominated children, then pop exactly the definitions introduced in this block. Without popping, a name from one branch leaks into its sibling. Filling phi edges at the predecessor also handles loop backedges: the header phi name already exists when the body is renamed.
"""Pruned iterated-dominance-frontier phi placement and dominator-tree renaming."""
from collections import defaultdict
from copy import deepcopy
from minicc.analysis import dominance_frontiers, dominance_tree, liveness, verify
from minicc.ir import Phi
def to_ssa(original):
if original.ssa: raise ValueError("already in SSA")
function = deepcopy(original)
verify(function)
frontiers = dominance_frontiers(function)
_, children = dominance_tree(function)
live_in, _ = liveness(function)
defsites = defaultdict(set)
for parameter in function.parameters: defsites[parameter.name].add(function.entry)
for name, block in function.blocks.items():
for instruction in block.instructions:
if instruction.dest is not None: defsites[instruction.dest].add(name)
for variable, sites in sorted(defsites.items()):
pending, placed = sorted(sites), set()
while pending:
origin = pending.pop()
for target in sorted(frontiers[origin]):
if target in placed or variable not in live_in[target]: continue
function.blocks[target].phis.append(Phi(variable, variable))
placed.add(target)
if target not in sites: pending.append(target)
stacks = defaultdict(list)
counters = defaultdict(int)
for parameter in function.parameters: stacks[parameter.name].append(parameter.name)
def read(operand):
if isinstance(operand, int): return operand
if not stacks[operand]: raise ValueError(f"uninitialized during rename: {operand}")
return stacks[operand][-1]
def define(variable, pushed):
counters[variable] += 1
name = f"{variable}.{counters[variable]}"
stacks[variable].append(name)
pushed.append(variable)
return name
def rename(name):
block, pushed = function.blocks[name], []
for phi in block.phis: phi.dest = define(phi.base, pushed)
for instruction in block.instructions:
instruction.args = tuple(read(arg) for arg in instruction.args)
if instruction.dest is not None: instruction.dest = define(instruction.dest, pushed)
block.terminator.args = tuple(read(arg) for arg in block.terminator.args)
for target in block.terminator.targets:
for phi in function.blocks[target].phis: phi.incoming[name] = read(phi.base)
for child in children[name]: rename(child)
for variable in reversed(pushed): stacks[variable].pop()
rename(function.entry)
function.ssa = True
verify(function)
return function
Acceptance: inspect the generated loop phis, run zero-trip and multi-trip loops, and mutate a phi edge or an ordinary use to demonstrate verifier rejection. Then generate small trusted programs and compare mutable execution, SSA execution, and a source oracle. The next chapter adds transformations on this verified representation.