542071 - Analyze implementation of closures in V8

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[David Mandelin [:dmandelin]]

See bug 542070.

Comment 1

[David Mandelin [:dmandelin]]

1. Closure Representation

A function object is a pair (context, code). |Context| in V8 means an activation context (like traditional "activation record" or EMCA-262 "activation object") (see context.h). Key elements of |Context|:

  closure          Backpointer to the function object (i.e., closure) of this
                   context
  fcontext         Immediately enclosing context; analogous to SM Call parent.
  previous         Used for |with|.
  extension        JSObject to hold variables created by with/eval; created
                   on demand
  global           Pointer to global object for this function
  [slots]          Slots to hold local variables accessed from inner functions

To create a function, they have a builtin NewClosure (runtime.cc), which mostly just calls NewFunctionFromBoilerplate (factory.cc). This calls AllocateFunction (heap.cc), which allocates the memory and then initializes properties, elements, the SharedFunctionInfo (which holds instance-invariant stuff, like the code), prototype, context, and literals (array, object, and regexp literals used in the function). All of these are basically initialized to 'empty' except |shared|, |prototype|, and |literals|.

They also have a fast path that can be used when the function doesn't have any (object, array, or regexp) literals. (The function also must be a function as opposed to the top-level script, because the fast path can only allocate in the new generation, and top-level scripts are allocated in the old generation.) This generates code that allocates memory, copies the function map (like our objectmap, I think; 3 loads and a store), and copies over the other basic fields. 

For reasons I don't understand, the fast path is generated as a separate function. It is a "stub function", which in their terminology seems to be a short-function that uses a V8-specific fast calling convention (e.g., for a one-argument function, pass the arg in eax). 

2. Closure Variable Read Operations

V8 classifies the "mode" of variable accesses. DYNAMIC_LOCAL means that the value is defined in a enclosing lexical scope. (They call it DYNAMIC_LOCAL because their code generator thinks of it as a dynamic lookup that must check for variables created by eval, etc., but the value is expected to be found as a local.)

(See codegen-ia32.cc LoadFromSlot) The code generator iterates over the lexical scopes between the current one and the one that defines the variable. Thus, it generates code to walk up the scopes. If a scope calls eval, then they check that the "context extension" is null, i.e., that with/eval have not dynamically created variables in this scope. If the check fails, they call a builtin LoadContextSlot (see runtime.cc). They always do this check in the target scope; I'm not sure why. Finally, they load the value from its slot.

The fast path above is generated only if the variable is a local variable. If it is an argument, they call the builtin. I believe this is a limitation they have because arguments are not slots of the same kind as variables.

3. Closure Variable Write Operations

They always call a builtin StoreContextSlot (see runtime.cc).

X. Other notes

When reading their assembler code, note that the destination is first. So

  __ mov (foo.reg(), bar.reg)

is like:

  foo := bar

Comment 2

[David Mandelin [:dmandelin]]

Here is an illustration of how the closure creation fast path requires that the closure not contain array, object, or regexp literals:

                                    TM             Nitro             V8
    create_xc.js            	  899.00	  114.00	   15.00
    create_xc_literal.js    	  901.00	  112.00	  130.00

Comment 3

[David Mandelin [:dmandelin]]

Running with gdb I discovered they have a no-call fast path for setting closure vars (if the variable can be totally resolved statically), and also I refined my picture of reading closure vars:

* Key classes.

|VariableProxy| is the AST node for identifier expressions. It is mostly just the name of the variable. It is linked to a |Variable| as part of semantic analysis.

|Variable| represents a resolved variable, with a name, scope, etc. 

|Slot| represents an abstract location that is a slot of some 'thing'. It is also considered an AST node. I think the idea is that a variable can be 'rewritten' to a slot expression as an intermediate step in compilation. Slots have a |type| attribute. Important types:

    LOCAL     a local variable. Parameterized by the index in the locals array
    CONTEXT   a slot in a heap context. Parameterized by the index in the
              context's slots array, and the lexical scope containing the slot.
    LOOKUP    a slot in a heap context accessed by name. Parameterized by a
              name.

* Reading. 

If there is no |eval| in play, a closure var will turn into a CONTEXT slot. The code generator will generate code to walk up the scope chain and read the slot. If |eval| is in play, the closure var will turn into a LOOKUP slot, but the variable itself will be mode DYNAMIC_LOCAL, which means the code generator will generate code to walk up the scope chain, verifying |eval| scopes have not changed as it goes. Thus, what I said in comment is basically right, except the details of how variables and scopes are classified.

* Writing.

If there is no |eval| in play, the closure var will again be rewritten as a CONTEXT slot. The code generator can then generate code to walk up the scope chain and write directly, without using a builtin as I said in comment 1. The code to do the writing is a bit more complex than for reading. I don't know all the details, but one is that the semantics of their assignment operation require the assigned value to be left on top of the value stack (to support code like |x = y = z|, just as in SM) so they duplicate and pop the value, at least logically.