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
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.
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 */ }}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.
// 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); }}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
initial state: all sets empty
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
Naive sequential copies
x = y // x_1 ← y_0
Parallel copy (cycle broken by temp)
t = x // save x_0 before it’s clobbered
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.
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
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}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.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.
- Phone
- (214) 723-2510
- 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.
$199/month
Billed monthly
$182.42/month
Billed yearly
$499/month
Billed monthly
$457.42/month
Billed yearly
- Scammers stopped from sending email as you
- Your website and systems scanned every week
- Your email settings checked every week
- Everything in the 1 to 10 plan
- Covers up to 50 people
$199/month
after a one-time setup fee
- A site planned, designed and built for you
- Hosting and updates every month
$499/month
Billed monthly
$457.42/month
Billed yearly
$999/month
Billed monthly
$915.75/month
Billed yearly
- Your Google profile, fully set up
- A Google post every week
- 2 social posts a week
- Everything in Get found
- 4 social posts a week
- Your top 10 Google searches tracked
from$500/month
after a one-time setup fee
- Your data gathered from the tools you use
- A first analysis that answers your questions
- New findings every month
Related reading
Engineering3 min readRoute optimization: when the shortest path is the wrong objective
How an interactive route planner went from the shortest path to the safest one, and what we learned building it.
Strategy3 min readBuild vs buy software: sort each process step before you write requirements
Sort every process step as commodity, differentiating or contextual before anyone writes a requirements document.
Systems5 min readConsensus is not the hard part: retries, compaction and partition moves
Consensus only replicates a log. Retried requests, log compaction and moving partitions between groups are what break in production.
