Skip to content

Engineering

What building a compiler teaches about data modeling

How choosing an intermediate representation in a compiler maps onto choosing the data model of a business system.

Computing America. Applications, integrations, data analysis and AI/ML engineering.

Send the model
4 min readComputing America
A white card architectural model of a building's structural grid on a drafting table.

In short

  • In SSA, reaching definitions go from a fixed-point iteration to a lookup. When a feature is hard, ask whether the algorithm is hard or the representation is making it hard.
  • The naive placement of merge nodes is correct and unusable. A schema that allows every combination the business could imagine is correct the same way, and every query then has to rule out the combinations that never occur.
  • Lowering out of SSA is where the awkward cases surfaced: the lost copy and the swap. A clean internal model gets the same test when it is exported to a partner's format, so export its worst case.
  • A register allocator weights the cost of spilling a value by loop depth. Weight your model's design the same way, by how often each path runs.
  • Ask three things of a data model: can it express the awkward case directly, can a rule change be reviewed and reverted, and can it explain its answers.

Building a compiler taught us that the representation you choose decides what every later stage costs, and a business system's data model works the same way. We built one end to end as a study of representation: a typed language, six optimizing passes, a graph-coloring register allocator, about 37,000 lines. No client paid for it. Its intermediate representation, static single assignment (SSA), has a one-clause rule that made several hard analyses simpler.

The front end is the comfortable part

Lexing and parsing are the well-documented part of a compiler, and not where ours was hard. In business software, forms and screens are the comfortable part and can absorb attention that belongs to the representation of the domain. That representation decides whether the system can change.

compiler/Scanner.javaJava
public class Scanner implements Iterator<Token> {    private BufferedReader input;    private int lineNum, charPos;    private int nextChar, secondChar;   // 2-char lookahead     public Scanner(String name, Reader r) {        this.input = new BufferedReader(r);        this.nextChar   = readChar();        this.secondChar = readChar();    }    @Override public Token next() { /* DFA over the two-char window */ }}
The entire front end is this shape: a two-character window, a state machine, and an iterator so the parser can just call next().

One constraint pays for everything

Every value in SSA is assigned exactly once. Where two control-flow paths merge and both define a value, you insert a merge node saying the value here is whichever predecessor you arrived from. Cytron and colleagues (opens in a new tab) published the efficient construction in 1991, and SSA form is now standard in optimizing compilers such as LLVM and GCC.

Reaching definitions become a lookup. Use-def chains are implicit, so there's nothing to maintain. Constant propagation becomes a graph traversal, and dead-code elimination takes two passes over the use graph.

Correct and unusable is a real category

The naive SSA construction inserts a merge node at every join for every variable. It is correct, and it makes the representation so large that the passes it was meant to speed up get slower. Cytron's dominance frontier inserts only the merge nodes that can be needed. A further one-line check skips the merge node when the variable isn't live at the join. That turns minimal SSA into pruned SSA and stops every later pass from chasing definitions nothing reads. A schema has the same failure: a table that allows every combination of fields the business could imagine is correct, and every query then has to rule out the combinations that never occur.

compiler/SSA.java: phi placementJava
// For each variable v with definition sites D(v),// place a phi at every block in DF+(D(v)).var worklist = new ArrayDeque<>(entry.getValue());var hasPhi   = new HashSet<BasicBlock>();while (!worklist.isEmpty()) {    BasicBlock b = worklist.poll();    for (BasicBlock y : df.getOrDefault(b, Set.of())) {        if (hasPhi.contains(y)) continue;        if (!liveIn.get(y).contains(s)) continue;   // pruned SSA        y.addPhi(new Phi(s, y.getPredecessors().size()));        hasPhi.add(y);        worklist.add(y);    }}
Two of those lines are the whole difference between an intermediate representation you can run passes over and one that is technically correct and unusably large: the dominance-frontier lookup that bounds where a merge node can be needed, and the liveness check on line 9 that prunes the ones nothing will ever read.

The liveness check is a backward dataflow analysis that iterates until nothing changes. With a loop in the code, that takes more than one pass. Step through it below.

Interactive · Dataflow analysis

Liveness, iterated to a fixpoint

Liveness analysis · backward dataflow to fixpoint

For every block: live_out = ⋃ live_in[s] for s ∈ successors, live_in = uses ∪ (live_out − defs). Process bottom-up; iterate until nothing changes. Hover any variable name to see where it’s live.

step 0 / 13

initial state: all sets empty

in: ∅B0 · entryx = 1out: ∅in: ∅B1 · headert = x + 1if t < 10 → B2 else B3out: ∅in: ∅B2 · bodyx = x * 2out: ∅in: ∅B3 · exitreturn tout: ∅
live-inlive-outusesdefs
What this isA four-block control-flow graph with a backedge, so the analysis takes more than one pass to settle. This is the check that turns minimal SSA into pruned SSA and the input the interference graph is built from. Four blocks, not thirty-seven thousand lines: the shape is faithful, the scale is a teaching one.

Construction is easy, deconstruction is not

Real machines don't implement SSA, so merge nodes must be lowered back into ordinary copies before registers are allocated. The obvious lowering, a copy at the end of each predecessor block, fails twice. A copy can overwrite a value a later block still reads (the lost copy), and merge nodes that exchange values must execute in parallel, so sequential copies destroy one before the other reads it (the swap). Briggs and colleagues (opens in a new tab) named both problems in 1998, and Boissinot and colleagues (opens in a new tab) later rebuilt the lowering around parallel copies.

A data model has the same exit. The clean internal form eventually gets lowered into a partner's X12 214, a report or a legacy system's flat file, and the awkward cases surface there. Test a model by exporting its worst case, not its typical one. Step the naive lowering through either scenario below and you can see the register get clobbered.

Interactive · Compilers

Lowering out of SSA: the lost copy and the swap

Phi deconstruction · The swap problem

Two phis at a join exchange values. Naive copies destroy one before the other can read it.

step 0 / 3

Naive sequential copies

Lower each phi independently into a copy at the end of the predecessor block. Order matters and there is none.

x = y     // x_1 ← y_0
x7
y11

Parallel copy (cycle broken by temp)

Detect the cycle in the copy graph (x ↔ y) and insert one temporary to break it.

t = x     // save x_0 before it’s clobbered
x7
y11
t·
What this isTwo merge-node scenarios that the obvious lowering gets wrong, stepped one copy at a time, next to the parallel-copy lowering that gets them right. The register values and the orderings are worked through by hand and stored as a table: this panel steps you through the outcome the compiler’s rule produces, it does not run that rule.

Register allocation comes down to what you spill

The allocator builds an interference graph, with an edge between two values live at the same point, and colors it with as many colors as there are registers. When it can't, it picks a value to spill to memory, and the pick is by cost. Each load and store a spill would add is weighted by its cost times 10 raised to its loop-nesting depth (Briggs, Cooper and Torczon (opens in a new tab)). A value used inside a hot loop is therefore expensive to spill, and one touched once outside any loop is cheap. A data model has the same budget: it can't make every access fast, so weigh each by how often it runs, and spend the indexes and denormalized copies on the paths that run in a loop.

Fig. 1

times the base cost

  • Outside any loop1×
  • One loop deep10×
  • Two loops deep100×

Each loop level multiplies a spill's cost by ten, so a value used two loops deep costs 100 times as much to spill as one used outside any loop.

SourceThe weighting this article describes, cost times 10 raised to the loop-nesting depth, for a base cost of 1.

Interactive · Register allocation

Graph coloring, and what gets spilled

Simplify · Color · 3 registers

Toy interference graph, K = 3. Phase 1 pushes any node with degree < K onto the stack and removes it. Phase 2 pops the stack and assigns each node the lowest color not used by its (original) neighbors.

abcde

phase

1 · simplify

stack (0)

empty

next

push a (deg 2 < 3)

palette

R0R1R2
What this isFive values, three registers, the simplify-then-color heuristic run one step at a time. The real allocator carries per-value statistics so it can prefer to spill something short-lived outside a loop; this graph is small enough that the heuristic never has to make that call, which is precisely the part the write-up says is where the quality lives.
compiler/RIG.javaJava
public class RIG {    record Edge(Variable a, Variable b) {}    private Set<Edge> edges = new HashSet<>();     private Stack<Variable> varStack = new Stack<>();    private Set<Variable> spilled    = new HashSet<>();     static class VarStats {        int usesDefs     = 0;        int maxLoopDepth = 0;    }    private Map<Variable, VarStats> varStats = new HashMap<>();    private Map<Variable, Variable> alias    = new HashMap<>();   // coalescing}
Two integers per value, and they are the entire spill policy: how often it is touched, and how deep in a loop nest. Everything else in the allocator is the textbook algorithm; those two fields are the part that decides whether the generated code takes a memory access on every iteration.

Ask the same question of your data model

Business software often has the same shape. Pricing engines evaluate versioned rule sets. Eligibility logic has to explain its own output. Integration layers translate one domain's vocabulary into another's. Each is a question about representation before it is a question about logic. Ask of your current model:

  • Can it express the awkward case directly, or only as an exception?
  • Can a rule change be reviewed, dated and reverted, or does it live in a WHERE clause?
  • Can the system explain why it produced an answer, or only that it did?

Sources

  1. 1.Efficiently Computing Static Single Assignment Form and the Control Dependence Graph (opens in a new tab), Cytron, Ferrante, Rosen, Wegman & Zadeck,

Next step

Send us the model you are stuck on.

The schema, or the diagram, however rough. We will tell you what that shape makes easy, what it makes impossible, and which of the two you would be paying for later.

Reply
A person replies, not a sequence: within one business day, from someone who would be on the engagement.

Packages

Start with a package

Four packages, each with its price on the page. Pick one and buy it online.

Billing