Parsing Binding Names for Efficient Representation

This post explains how binding names are parsed for efficient representation in the SpiderMonkey virtual machine. The story itself is a narrow one about JavaScript, but I should hope the lessons contained are more broadly applicable to other language runtimes where parsing of the source text is included in the perceived execution time.

To start, by “binding name” I mean the following.

A binding name is the name bound by a declaration. In JS, there are many forms of declarations. To name some: var, let, const declarations, function statements, and formal parameters. For example, x is the binding name in var x.

Representation of Bindings

The important constraint above is “efficient”. It is only correct to implement the JS specification literally by keeping bindings in a list of maps from strings to values. Such an implementation is inefficient in both time and space. It is slow to look up a name dynamically every time it is needed, and it is wasteful to keep around values that the program will never need again.

We aspire to optimize bindings along both the space and time axes. To optimize for space, we make the distinction between bindings that are live beyond the execution of their scope and bindings that are not and represent them differently. To optimize for time, we make the distinction between identifiers that always refer to the same binding and identifiers that do not and access them differently. The former arises from use of closures. When an inner function references a binding in an outer scope, we say that binding is closed over. The latter arises from the dynamicity of eval and with. When eval code references a binding in an outer environment, we call the access dynamic.

For example, in the following program, var x is closed over by g:

function f() {
  var x;
  function g() { x = 42; }
}

In the following program, it is unknown if eval(unknownInputStr) will close over x. For example, unknownInputStr may be "function g() { x = 42; }". For correctness, compilers must conservatively assume that it will.

function f(str) {
  var x = 42;
  eval(unknownInputStr);
}

In a language runtime where parsing time counts towards total execution time, we aspire to perform representation optimizations during parsing. This limits the heft of the optimizations that might be undertaken: heavyweight analyses lead to better optimizations, but do not pay for themselves.

In practice, this gives us the following tiers of representations on a per-binding basis, sorted from most to least optimized.

Elision

The binding is known to always hold the same value and is not accessed dynamically. It is treated as if it were a value.

On the stack frame

The binding is not closed over by an inner function or accessed dynamically. It may be put on the stack frame and accessed via constant offset.

On the environment

The binding is closed over by an inner function or accessed dynamically. It must be put in a heap-allocated environment record that maps binding names to values and persists beyond the lifetime of the frame. During execution, environments exist in a chain from outermost scope to innermost scope.

Dynamic accesses are via name, and non-dynamic access are via a coordinate: a pair of natural numbers (hops, slot). Hops is the number of environments to skip on the environment chain, and slot is the known offset for the binding in the environment’s map.

We ignore elisions for the rest of the post. A production parser can only afford cheap, weak analyses to determine if a binding may be elided and thus very rarely elides any bindings.

Detecting If a Binding Is Closed Over During Parsing

If a binding is closed over or dynamically accessed, it must reside on the environment. Otherwise it may reside on the stack frame. Detecting the presence of dynamic accesses boils down to detecting the presence of constructs like eval in the source, which is by and large uninteresting. Determining whether a binding is closed over is the more interesting problem.

Recall that the parser must be fast. Therefore determining closed-over bindings must be cheap and ideally should occur as the parsing happens. Herein lies some art. first an obvious solution is presented, then a solution that I believe to be a reasonable tradeoff between performance and simplicity.

JS adds two oddities.

The first is that declarations are hoisted. In the following example, x is closed over by g.

function f() {
  function g() { x = 42; }
  var x;
}

This would be a non-issue if the analysis were performed as a separate pass instead of during parsing itself. During parsing itself, there is no guarantee uses of the binding precede declarations in source text.

The second is that JS has both block-scoped declarations in the forms of let and const as well as function-scoped declarations in the form of var. This means a function can close over a binding declared in an inner scope. In the following example, x is closed over by g, because var declarations are visible in the entire function.

function f() {
  function g() { x = 42; }
  try { foo(); } catch (e) { var x; }
}

The Obvious Algorithm

The obvious solution is to keep a stack of sets of names during parsing. The algorithm is as follows.

Let Declared, Used, and Captured range over sets of names, Tag be 'block' or 'function', and ScopeStack be a stack of tuples of (Tag, Declared, Used, Captured).

1. When the parser reaches a new function scope, push the tuple of empty sets ('function', ∅, ∅, ∅) onto ScopeStack.
2. When the parser reaches a new block scope, push the tuple of empty sets ('block', ∅, ∅, ∅) onto ScopeStack.
3. When a var declaration is parsed, add its binding name to the Declared set of all tuples on ScopeStack from the top tuple to the nearest tuple, inclusive, with a 'function' Tag.
4. When a lexical declaration is parsed (e.g., a let or const declaration), add its binding name to the Declared set of the topmost tuple in ScopeStack.
5. When the parser reaches the end of a scope,
   1. Pop the topmost tuple (tag, declared, used, captured) from ScopeStack.
   2. Assert that captured ⊆ used.
   3. If ScopeStack is not empty:
      1. Let free be the set used - declared.
      2. Add all names in free to the used set of the topmost tuple of ScopeStack.
      3. If tag is 'function', add all names in free ∪ captured to the Captured set of the topmost tuple of ScopeStack.
      4. If tag is 'block', add all names in captured to the Captured set of the topmost tuple of ScopeStack.
      5. Mark all names in the set of declared ∩ captured as closed-over.

This algorithm answers the question, for each binding name encountered during parsing, whether it is closed over. The first concern above of declaration hoisting is solved via delaying computation of whether a binding name is closed over to when the parser reaches the end of a scope, viz. step 5. The second concern above is addressed by step 4.

This algorithm is slow. Set difference, union, and intersection for every scope is expensive. Moreover, these operations are performed on every encountered identifier, while the question of “is the binding closed over” need only be determined for the binding names. The number of binding names is typically much smaller than the number of identifiers.

The Scope Numbering Algorithm

To refine the algorithm and do better, we rely on the insight that we need not propagate whether an identifier is used in inner functions for all identifiers. Instead, we only need to do so for binding names. That is, the used and captured sets in algorithm 1 may be tracked more efficiently. A list of identifier uses may be gathered and kept up-to-date for each identifier as we parse. No further computation need be done on this list of uses until the parser reaches the end of a scope with binding names, in which case the question of “is the binding name closed over” may be answered by only consulting the lists kept for the binding names.

What then is the sufficient information for this list of uses to determine whether a binding name is closed over? Intuitively, per the algorithm 1 above, it is whether the binding name occurs in the captured set at the end of the binding name’s scope. To efficiently represent the captured set, scopes and functions in the source may be monotonically numbered in textual order. This gives the following invariant:

Let a scope the parser has not yet finished parsing be called a live scope. At any particular point during parsing, a live scope numbered S encloses a live scope numbered P if and only if S < P.

Mutadis mutandis, the same holds for function numbers.

More formally, a use is encoded as a pair of numbers (F, S) where F ranges over function numbers and S ranges over scope numbers. A binding name is closed over if, when the parser reaches the end of the name’s scope in a function numbered F_c, there is a use (F, S) in the name’s use list such that F > F_c. Care must be taken to remove stale uses from the list for scopes we have finished parsing. This is done by, upon the parser reaching the end of a scope numbered S_c, removing all entries (F, S) from the list of uses such that S ≥ S_c. The list of uses is thus is accessed only in fiFO fashion, resulting in cheap upkeep.

Putting the above together, the full algorithm is presented below.

Let FunctionId and ScopeId range over natural numbers, Declared range over sets of names, Tag be 'block' or 'function', DeclaredStack be a stack of tuples (Tag, FunctionId, ScopeId, Declared), UsedMap be a map of names to stacks, and functionCounter and scopeCounter be 0.

1. When the parser starts parsing a new function scope,
   1. Let functionCounter be functionCounter+1.
   2. Let scopeCounter be scopeCounter+1.
   3. Push the tuple ('function', functionCounter, scopeCounter, ∅) onto DeclaredStack.
2. When the parser starts parsing a new block scope,
   1. Let scopeCounter be scopeCounter+1.
   2. Push the tuple ('block', functionCounter, scopeCounter, ∅) onto DeclaredStack.
3. When a var declaration is parsed, add its binding name to the Declared set of all tuples on DeclaredStack from the top tuple to the nearest tuple with a 'function' Tag.
4. When a lexical declaration is parsed (e.g., a let or const declaration), add its binding name to the Declared set of the topmost tuple in DeclaredStack.
5. When the parser encounters an identifier u,
   1. Let (tag, functionId, scopeId, declared) be the top tuple of DeclaredStack.
   2. If u is found in UsedMap, append the pair (functionId, scopeId) to UsedMap[u].
   3. Otherwise, let UsedMap[u] be the singleton stack [(functionId, scopeId)].
6. When the parser reaches the end of a function or block scope,
   1. Pop the topmost tuple (tag, functionId, scopeId, declared) from DeclaredStack.
   2. For each name d in declared that is found in UsedMap,
      1. Let uses be UsedMap[d].
      2. Mark d as closed over if, for the topmost tuple (innermostFunctionId, innermostScopeId) of uses, innermostFunctionId > functionId.
      3. Pop all tuples from uses until the topmost tuple (innermostFunctionId, innermostScopeId) is such that innermostScopeId < scopeId.

For the formally inclined, this algorithm is an imperative, single-pass moral equivalent to variable renaming, with JS allowances added.

I invite you to take a look at the implementation inside SpiderMonkey.

Bonus Caveat: Pooled Allocations

I should like to stress that pooled allocation, especially for sets of names as used in DeclaredStack in algorithm 2, is important for performance. The usual program has a low maximum number of nested scopes but has many sibling scopes at each depth. Since the set of declared names need not be kept after a scope has finished parsing, pooling allocations of data structures used in LIFO fashion and reusing them during parsing saves much allocation overhead.

Conclusion

In summary, I have presented an algorithm for determining whether binding names are closed over during parsing for JavaScript. That information is used to determine binding representation. Binding names that are not closed over may be stored on the stack frame, and those that are closed over must be stored on the environment. Dynamic constructs like eval forces all storage to be on the environment. I hope the lesson extends to runtimes of other dynamic languages for which parsing time is part of the total execution time.