Fixing a Stack Overflow Shrank Js_of_ocaml Output by 16%

One of our customers 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 cause was a single function with tens of thousands of local variables, which used up most of the stack before doing any work.

13,000 Variables, 100 KB of Stack

Js_of_ocaml is a compiler from OCaml bytecode to JavaScript. It puts all initialisation code into a single large toplevel function, a design that enables whole-program optimisations 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. With js_of_ocaml, this one function can become enormous.

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 100 KB of stack consumed before the function starts running. We focused on V8, which is the most common target, but other engines may behave similarly.

The fix is to reduce the number of local variables, and two complementary techniques do this: variable coalescing and constant sinking.

Variable Coalescing Reuses the Names of Dead Variables

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, the two can share the same name.

This is variable coalescing, a classic optimisation from compiler construction, typically applied when converting out of SSA (Static Single Assignment) form, an internal representation in which each variable is assigned only once. I'd wanted to implement it for years, but kept putting it off, for reasons I come back to at the end.

Liveness First, Then Merging

The pass walks through the code, works out when each variable is "alive" (might still be used) or "dead" (won't be used again), then gives the same name to variables whose live periods don't overlap.

It adapts a technique called linear scan register allocation, originally designed for assigning variables to CPU registers. The usual alternative, graph colouring, builds a graph of the variables that can't share a name and then colours it. It can find better assignments, but it is expensive on large functions, and compile time is a concern in js_of_ocaml. Linear scan runs in time linear in the size of the function, which keeps it fast on tens of thousands of variables.

The pass 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 has four steps:

1. Build a control flow graph in which 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 the usual notation:

   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, processing them in the order in which they first become alive. For each variable, the pass tries 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.

Dead in One Branch, Live in the Other

A simple view of liveness treats a variable as alive from its first definition to its last use. Branches make this view too coarse. Consider this code:

1: var big = createLargeObject(); // 'big' is defined
2: if (someCondition) {
3:   // 'big' is dead in this branch: it is never read here.
4:   // It is still live in the other branch.
5:   var temp = doWork();
6:   // 'temp' can share a name with 'big'
7:   // because 'big' is dead here.
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, so its live range spans both. But inside the if branch, on lines 3-7, big is dead. The algorithm records this as a hole in big's live range and lets temp reuse the name, even though big is still needed on the other branch.

// Optimised: 'big' and 'temp' share variable 'a'
var a = createLargeObject();
if (someCondition) {
  // 'a' now holds 'temp'. Overwriting 'big' is safe
  // because this branch never reads it.
  a = doWork();
} else {
  use(a); // 'a' still holds 'big' here
}

Copy Hints Turn x = y into a No-op

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 name, the assignment becomes a no-op that later passes can eliminate.

This is important for js_of_ocaml because its internal representation is in SSA form. Assigning each variable 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, special constructs that pick 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.

For this to work, the pass must be precise about exactly when a variable dies. It uses a technique 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), the instruction reads y. If this is y's last use, its live range ends here.
• At time 2i+1 (output), it writes x. This is x's definition, so its live range begins here.

Because 2i < 2i+1, the two live ranges don't overlap, so x and y can get the same name and the assignment disappears.

Exception Handlers Extend Live Ranges

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.

Pretty Mode Keeps Your Variable Names

Coalescing makes generated code harder to read, since one name now stands for several variables. Js_of_ocaml output is minified by default, so this only affects "pretty mode", used for debugging. There, js_of_ocaml disables coalescing for user-defined variables and only merges compiler-generated temporaries. The variable names from your OCaml source are then preserved in the JavaScript output, which makes it easier to step through with a debugger.

Captured Variables Are Left Alone

The pass does not coalesce captured variables (variables used by nested functions), for two reasons:

1. They don't contribute to the problem. The stack overflow was caused by stack-allocated locals, and captured variables live on the heap, in V8's context objects.
2. Handling them would be complex. The pass tracks captured variables with a simple 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 possible in theory, but doing so safely is tricky.

Constant Sinking Moves Definitions Next to Their Uses

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

This leaves 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 uses.

Analyse, Plan, Transform

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 to handle dependencies. If constant y uses constant x in its initialiser, then y is a use of x, and where y ends up has to be known before x can be placed. For each constant, the pass finds the innermost scope that contains all its uses (the "nearest common ancestor" of the usage sites). 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.

Two Traversals Must Visit Scopes in the Same Order

To move a variable to "Scope #42", the transformation pass needs to know which scope is #42. The analysis and transformation passes must therefore traverse the abstract syntax tree (AST) in the same order and enter and leave scopes at the same moments.

At one point, I had an implementation that looked correct, but variables kept landing in the wrong scopes. The cause turned out to be 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. But OCaml doesn't specify the evaluation order of constructor arguments, and the current backend evaluates them right to left. The two traversals visited nodes in different orders, so their scope IDs silently drifted apart. I had to make the evaluation order explicit in the map traversal so that it matched the iterator.

Allocations Stay Out of Loops

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 avoids this by refusing to move allocations into loops or nested functions.

The Numbers

I measured both optimisations on two programs: ocamlc (the OCaml bytecode compiler, which produces about 2.3 MB of JavaScript) and PRT (the partial render table benchmark from the 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

For PRT, the two passes together cut the toplevel function from 13,539 variables to 1,263, a 91% reduction.

The two passes reinforce each other. Sinking shortens live ranges, which gives coalescing more room to merge variables, and it inlines single-use constants, which removes variables before coalescing runs. 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), but the measured reduction is 91%.

Programs with more toplevel initialisation 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 what these passes target.

What I Didn't Expect

I set out to fix the stack overflow, but the passes did more than that.

I'd wanted to implement variable coalescing for fifteen years. It's textbook stuff, standard practice when moving out of SSA form to remove the unnecessary assignments that phi nodes produce (var x = y). I had two reasons for putting it off. 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 optimisers. JS engines track values, not variables, so this isn't an issue. Second, these unnecessary assignments aren't that frequent, so the benefit seemed marginal. I was wrong about that second part.

Constant sinking also did more than I planned. I implemented it to help coalescing, since shorter live ranges mean more merging opportunities. But many constants turned out to have a single use, and these get inlined at that use, which removes the variable. Inlining wasn't in the original plan; it came up as an obvious improvement while writing the code.

The biggest gain was in compressed size. A 10–16% reduction in gzipped output is significant for web deployment, since compressed size is what users download.

Part of the gain is simple. 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...) repeats itself far less than code that keeps reusing about a thousand, and Deflate compresses repetition well.

Conclusion

What started as a fix for stack overflows also made the output smaller: 74–91% fewer variables, roughly 4–8% smaller output, and 10–16% smaller gzipped output. Our customer's stack overflows are fixed, at the cost of about 5% slower compilation. For performance work on the WebAssembly side, see our earlier post on Wasm_of_ocaml optimisations.

The implementation is available in the js_of_ocaml repository:

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

Until Next Time

If you use js_of_ocaml 6.4.0 or later, both passes are on by default, so you get the benefit without changing anything. We are always keen to hear how they behave on real applications, so please share your experience on OCaml's discussion forum.

You can connect with us on Bluesky, Mastodon, Threads, and LinkedIn or sign up for our mailing list to stay updated on our latest projects. We look forward to hearing from you!