Fixing a Stack Overflow Shrunk Js_of_ocaml Output by 16%

Jane Street ran into a puzzling problem: their OCaml programs, compiled to JavaScript with js_of_ocaml, were crashing with stack overflows, but the stack traces weren't deep at all.

The culprit? A single function with tens of thousands of local variables, eating up most of the stack before any real work began.

100KB Before Line One

Js_of_ocaml is a compiler from OCaml bytecode to JavaScript. It puts all initialization code into a single large toplevel function, a design that enables whole-program optimizations like dead code elimination, constant propagation, and inlining. Most JavaScript is hand-written or comes from compilers that generate many smaller functions, so this problem doesn't arise. But js_of_ocaml's whole-program-in-one-function approach means this function can become enormous.

Here's where V8's implementation bites us. V8 compiles JavaScript to its own bytecode, allocating one stack slot (8 bytes) for each local variable that isn't captured by a nested function. (Captured variables live on the heap in a "context" object.) For a function with 13,000 local variables, that's 100KB of stack consumed before a single line executes. We focused on V8, which is the most common target, but other engines may behave similarly.

The fix seems obvious: reduce the number of local variables. But how? Two complementary techniques get us there: variable coalescing and constant sinking.

Variable Coalescing: One Name, Many Lives

The key insight is that not all 13,000 variables are in use at the same time. If variable x is never used again by the time variable y gets defined, why give them different names? They can share the same one.

This is variable coalescing, a classic optimization from compiler construction, typically applied when converting out of SSA (Static Single Assignment) form, an internal representation in which each variable is assigned exactly once. I'd wanted to implement it for years, but kept putting it off. More on that later.

The Algorithm

The core idea: walk through the code, figure out when each variable is "alive" (might still be used) versus "dead" (definitely won't be used again), then give the same name to variables whose alive-times don't overlap.

The pass adapts a technique called linear scan register allocation. It was originally designed for assigning variables to CPU registers, but it works just as well for merging JavaScript variables. Why linear scan instead of the theoretically optimal approach, graph coloring, which builds a graph of the variables that can't share a name and then colors it? Speed. Graph coloring can be expensive for large functions, and compile time matters a lot in js_of_ocaml. Linear scan is linear in the size of the function, which matters when you're processing tens of thousands of variables.

It builds on Mössenböck and Pfeiffer's extension of linear scan that supports holes in live ranges: a variable may be alive, then dead for a while, then alive again. Another variable can reuse the name during that gap.

The algorithm:

1. Build a control flow graph: represent the function as a graph where statements are nodes and control flow (if/else branches, loops, try/catch) creates edges.

2. Compute liveness by working backwards through the graph. At each node, track which variables might still be needed. In compiler-speak:

   LiveIn(n) = Use(n) ∪ (LiveOut(n) - Def(n))
   LiveOut(n) = ∪ LiveIn(succ) for all successors
   

   where Use(n) is the set of variables read at node n, Def(n) those written at n, and the successors of n are the nodes that can execute next.

3. Compute live ranges for each variable: the spans of code where it's alive.

4. Merge variables by processing them in order of when they first become alive. For each variable, try to reuse an existing name:

   • Hint-based: If this variable comes from a copy (x = y), try to reuse y's name. If it works, the copy becomes a no-op.
   • Opportunistic: Reuse a variable from the free list (completely dead) or find a fit in the inactive list (currently in a "hole").

   If no merging is possible, the variable keeps its own name.

Holes: When a Variable Takes a Break

One simplified view of liveness is that a variable is "alive" from its first definition to its last use. But real programs have branches. Consider this code:

1: var big = createLargeObject(); // 'big' is defined
2: if (someCondition) {
3:   // 'big' is NOT used here. It's technically "live" (still
4:   // needed on the other branch), but there's a gap in the timeline.
5:   var temp = doWork();
6:   // 'temp' can inhabit the same stack slot as 'big'
7:   // because 'big' is effectively paused.
8: } else {
9:   use(big); // 'big' is used here
10: }

In a linear view of the code (lines 1-10), big is defined at line 1 and used at line 9. But during lines 5-6, big is effectively dormant. The algorithm identifies this "hole" in big's lifetime and allows temp to reuse the same name, even though big is still needed on the other branch.

// Optimized: 'big' and 'temp' share variable 'a'
var a = createLargeObject();
if (someCondition) {
  // 'a' is reused for 'temp' here!
  // The value of 'big' is overwritten because it's never used in this branch.
  a = doWork();
} else {
  use(a); // 'a' still holds 'big' here
}

Copy Hints: Killing x = y

When the pass sees var x = y where y is a local variable, it records a "hint" that x should reuse y's name if possible. If they end up sharing the same name, the assignment becomes a no-op that later passes can eliminate.

This matters a lot for js_of_ocaml, because its internal representation is in SSA form. Assigning each variable exactly once creates a problem at control flow join points, where an if and else branch merge back together. If the if branch sets x1 = 1 and the else branch sets x2 = 2, what variable holds the result after the merge? Textbook SSA solves this with phi nodes: a special construct that picks the right value based on which branch was taken. Js_of_ocaml uses an equivalent formulation: each branch passes its value as an argument to the block it jumps to, which receives it as a parameter.

When compiled to JavaScript, passing such an argument becomes a plain assignment: var x3 = x1 in one branch, var x3 = x2 in the other. With copy hints, the pass often merges x3 with x1 or x2.

But to make this work reliably, we need to be precise about exactly when a variable dies. The trick comes from the register allocation literature: split every instruction into two time points, an "input" step and an "output" step.

Consider var x = y at instruction i:

• At time 2i (input), we read y. If this is y's last use, its life ends here.
• At time 2i+1 (output), we write x. This is x's definition, so its life begins here.

Because 2i < 2i+1, the two lifetimes don't overlap. This guarantees we can assign x and y to the exact same variable, turning the assignment into a no-op that disappears entirely.

The Try/Catch Wrinkle

Exception handlers require special care. Since an exception can be thrown from any point in a try block, variables live at the handler entry must be considered live throughout the entire try block. The pass extends their live ranges accordingly.

Developer Experience: Keeping It Readable

Aggressive optimization typically turns code into unreadable soup. While js_of_ocaml output is already minified by default, the debugging experience still matters. When users compile in "pretty mode" (for debugging), js_of_ocaml disables coalescing for user-defined variables, effectively only merging compiler-generated temporaries. This ensures that the variable names you wrote in your OCaml source are preserved in the JavaScript output, making it much easier to step through with a debugger.

Captured Variables: Hands Off

The pass explicitly excludes captured variables (variables used by nested functions) from coalescing.

Two reasons driven by pragmatism:

1. The Goal: The stack overflow crash was caused by stack-allocated locals. Captured variables live on the heap (in V8's "context" objects), so optimizing them wouldn't help.
2. The Complexity: The tracking of captured variables is intentionally simple: just a flag set when a variable is used in a nested function. Merging a captured variable with a non-captured one that dies before the closure is created is theoretically possible, but doing so safely is tricky, and it buys nothing against the stack overflow.

Constant Sinking: Don't Define It Until You Need It

Variable coalescing alone wasn't enough. Indeed, js_of_ocaml places shared constants at the top of the generated code, and there can be a lot of them. OCaml bytecode stores constants in a table loaded at program start, which js_of_ocaml faithfully reproduces. A separate pass also deduplicates strings and numbers, hoisting these shared literals to the top.

The result? Hundreds of variables defined at line 10 that aren't used until line 10,000. Each one blocks coalescing for 9,990 lines.

Constant sinking fixes this by moving definitions closer to their usage sites.

The Three Phases

1. Analysis: Walk through the code to find constant declarations: primitives like numbers and strings, and allocations like arrays and objects. For each constant, record every place it's used and what scope (function, loop, block) that use lives in. Also track dependencies: if constant x is used to define constant y, then where x goes affects where y can go.

2. Planning: The pass processes constants in reverse definition order. Why? To handle dependencies. If constant y uses constant x in its initializer, then y is a usage site of x, and where y ends up has to be known before x can be placed. Processing later definitions first ensures this. For each constant, it finds the "nearest common ancestor" of all usage sites: the innermost scope that contains all uses. Then:

   • Primitives (numbers, strings) can move freely to that location.
   • Allocations (arrays, objects) are more restricted: they can't cross into loops or nested functions.
   • Single-use constants get inlined directly at their usage site when safe.

3. Transformation: Remove the original declarations and re-insert them at their new positions.

The Implementation Trap

Step 3 hides a trap. To move a variable to "Scope #42", the transformation pass needs to know exactly which scope is #42.

This means the Analysis and Transformation passes must run in perfect lockstep. They must traverse the abstract syntax tree (AST) in the exact same order and enter/exit scopes at the exact same moments.

At some point, I had an implementation that looked correct, but variables kept landing in the wrong scopes. After much head-scratching, I found the culprit: OCaml's evaluation order. The analysis used an iterator, which only visits nodes, and the transformation used a map, which rebuilds the tree as it goes: two generic traversals over the AST. But OCaml doesn't specify evaluation order for constructor arguments (and the current backend evaluates them right-to-left). The two traversals were visiting nodes in different orders, causing scope IDs to drift silently. I had to make the evaluation order explicit in the map traversal, matching the iterator exactly. An invisible bug at the source, but it inserted variables into completely wrong functions.

Why We Can't Sink Everything

Consider this code:

var arr = [1, 2, 3];
for (var i = 0; i < 10; i++) {
  process(arr);
}

If we moved arr's definition into the loop:

for (var i = 0; i < 10; i++) {
  var arr = [1, 2, 3];  // Creates 10 different arrays!
  process(arr);
}

We'd create 10 different array objects instead of one. This changes semantics if process mutates arr, stores a reference to it, or compares array identity. Constant sinking carefully avoids this by refusing to move allocations across loop or function boundaries.

The Numbers

I measured both optimizations on two programs: ocamlc (the OCaml bytecode compiler, which produces about 2.3MB of JavaScript) and PRT (the partial render table benchmark from Jane Street's Bonsai web framework). For each, the tables below report the number of local variables in the toplevel function and the size of the generated JavaScript in bytes, before and after gzip compression.

OCaml Compiler (ocamlc)

PRT

What the Numbers Tell Us

The variable reduction is dramatic. For PRT, the toplevel function went from 13,539 variables to 1,263, a 91% reduction, leaving under a tenth as many.

The optimizations multiply each other. Neither pass gets anywhere near the combined result alone. Two effects compound: sinking creates shorter live ranges, giving coalescing more room to merge variables; and sinking inlines single-use constants, eliminating variables entirely so there are fewer left to coalesce. For PRT, sinking alone removes 63% of the variables and coalescing alone 30%. If the two acted independently, combining them would leave about a quarter of the variables, a 74% reduction. I measured 91%.

Programs with more toplevel initialization benefit more. With both passes enabled, PRT improves more than ocamlc on every metric, despite producing less code overall: its toplevel function starts with 4.5× as many variables (13,539 vs 3,005). Bonsai applications build up a lot of state at startup, which is exactly what these passes target.

What I Didn't Expect

The goal was simple: fix the stack overflow. But the results surprised me.

I'd wanted to implement variable coalescing for fifteen years. It's textbook stuff, standard practice when moving out of SSA form, eliminating unnecessary assignments from phi nodes (var x = y). So why hadn't I done it? Two reasons. First, back then I didn't understand JavaScript engines nearly as well as I do now, and I worried that reusing a variable for different purposes might confuse their optimizers. It turns out JS engines track values, not variables, so this isn't an issue. Second, the unnecessary phi assignments aren't that frequent, so the benefit seemed marginal.

I was wrong about that second part.

Constant sinking surprised me as well. I implemented it as an enabler for coalescing, since shorter live ranges mean more merging opportunities. But many constants turned out to have only a single use. These get inlined directly, eliminating the variable entirely. Inlining wasn't even in the original plan; it emerged as an obvious improvement while writing the code.

The compression numbers were a real surprise. A 10–16% reduction in gzipped output is significant for web deployment, where every kilobyte matters.

Part of it is straightforward: with 1,263 variables instead of 13,539, most names shrink from two or three characters to one or two, so the uncompressed file gets smaller as well. The rest comes from how compression algorithms like Deflate work: they look for repeated patterns. Code drawing on thousands of distinct names (a, b, c, ... aa, ab...) offers far less repetition than code that keeps reusing a few hundred. The file isn't just smaller; it's more repetitive, which is exactly what compressors love.

Conclusion

What started as a targeted fix for stack overflows turned into a substantial win across the board: 74–91% fewer variables, roughly 4–8% smaller output, 10–16% smaller gzipped output. Jane Street's stack overflow issue? Fixed. The cost? About 5% slower compilation, well worth it. These passes are now part of js_of_ocaml's standard optimization pipeline.

Sometimes the best optimizations are the ones you kept putting off.

The implementation is available in the js_of_ocaml repository:

• compiler/lib/js_variable_coalescing.ml
• compiler/lib/js_constant_sinking.ml