Bug 74708 – Optimize access to block-scoped local variables

• Status: RESOLVED
• Resolution: INVALID
• Component: JavaScriptCore

[Andy Wingo]

The patch to be attached has a changelog, thusly:

        This commit changes the bytecompiler to track static scope
        objects, allowing statically scoped (block-scoped) variables to be
        resolved at compile-time.  (Currently, only the exception
        identifier in catch blocks is block-scoped, in ES5.)

        The implementation is complicated by having to consider whether or
        not a function has a scope chain in the activation record or not.
        To get around this, we indicate that a negative depth, returned
        from findScopedProperty, indicates a local, block-scoped variable.
        The logic to check for a scope chain in the activation record or
        not only happens when looking for lexically captured variables --
        those with non-negative depth.

        This will allow block-scoped locals to be optimized by the
        baseline and DFG JITs.  A future patch will add support for ES6
        block locals, behind an #ifdef, using the same mechanism.

[Andy Wingo]

Created attachment 119603 [details]
Patch

[Geoffrey Garen]

In-band signaling is error-prone. It's not great that you had to add an explanatory comment to every call site.

I'd prefer to see some refactoring here:

(1) Rename findScopedProperty to resolve;

(2) Change resolve to return an object, ResolveResult, describing what it found.

(3) Add "I found a block-scoped variable" as a feature to ResolveResult.

(4) Add optimizations to take advantage of (3).

[Andy Wingo]

(In reply to comment #2)
> In-band signaling is error-prone. It's not great that you had to add an explanatory comment to every call site.
> 
> I'd prefer to see some refactoring here:
> 
> (1) Rename findScopedProperty to resolve;
> 
> (2) Change resolve to return an object, ResolveResult, describing what it found.
> 
> (3) Add "I found a block-scoped variable" as a feature to ResolveResult.
> 
> (4) Add optimizations to take advantage of (3).

Thanks for the review.  I will work on a new patch that does this.  Incidentally, V8's implementation of block-scoped lexicals drove a similar refactor within V8.

Andy

[Andy Wingo]

Created attachment 122960 [details]
Patch

[Andy Wingo]

I have a new patch that includes the work from bug 74633, and significantly improves on this one, according to feedback.  It happens to be based on the scopenode/codenode separation from bug 74509, which I still think is a good idea, but is not essential to this patch.

More details when I upload the thing.

[Andy Wingo]

Created attachment 132634 [details]
Patch

[Andy Wingo]

OK, attached the new patch.  It uses a visitor to compute the block scope depth, though perhaps it could reserve temporaries instead as Oliver suggested.  It is not tested enough.  It passes run-javascriptcore-tests with debugging settings, but I have not tried it with the classic interpreter, or the LLInt which doesn't yet work on my platform.

But, I think it is a great base for ES6 block scope.

What do you think about the opcode changes?  Would you prefer branching instructions for the barriers?  With some work we should be able to remove some barriers in the parser, and all possible barriers in the DFG.

Do we need an additional flag on symboltable entries indicating the need for r/w barriers?

I'm sure there are many open questions that you still might have.  I'm all ears!

[Andy Wingo]

Created attachment 132796 [details]
Patch

[Andy Wingo]

Just uploaded a new patch in response to some informal review by Oliver.

Changes:
  * Removed the nodevisitor stuff and the separate pre-pass.
  * Added an arg to op_reify_scope to explicitly give the base register.
  * Rebased on top of ToT instead of bug 74509.

Still untested with the classic interpreter.  Still no DFG support for the new opcodes.  Still untested with LLInt, and I still haven't run all the layout tests yet.  But it's a clean patch and review is welcome.

[Build Bot]

Comment on attachment 132796 [details]
Patch

Attachment 132796 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12005223

[Build Bot]

Comment on attachment 132796 [details]
Patch

Attachment 132796 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12005238

[Andy Wingo]

Created attachment 132810 [details]
Patch

[Andy Wingo]

Updated patch changes:

  * Turns out, op_unset is the same as op_init_lazy_reg.  So I removed op_unset and changed the compiler to emit init_lazy_reg instead.
  * Better baseline JIT code for the isEmpty / !isEmpty() checks.
  * Complete but untested llint implementation.

Problems:
  * I'm pretty sure that BytecodeCompiler::resolve is doing the wrong thing in the presence of lazy unreified block scopes.  It would be cleanest if we could count from the scope chain that was current when the function was entered.
  * The error messages you would get when falling afoul of the temporal dead zone are pretty bad.  I need to figure out something better.
  * Still haven't run the full tests.
  * Probably there are some symbol table files to update for the changes in opcodes.

[WebKit Review Bot]

Attachment 132810 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1
Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp:2323:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Total errors found: 1 in 22 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Build Bot]

Comment on attachment 132810 [details]
Patch

Attachment 132810 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12005245

[Build Bot]

Comment on attachment 132810 [details]
Patch

Attachment 132810 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/12009153

[Early Warning System Bot]

Comment on attachment 132810 [details]
Patch

Attachment 132810 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/11994305

[Early Warning System Bot]

Comment on attachment 132810 [details]
Patch

Attachment 132810 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/12000300

[Gustavo Noronha (kov)]

Comment on attachment 132810 [details]
Patch

Attachment 132810 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/12000314

[Andy Wingo]

Created attachment 132839 [details]
Patch

[Andy Wingo]

Changes in the new patch:

  * Possibly fix 32_64 builds.
  * Add a flag to SymbolTableEntry to indicate variables that need the temporal dead zone.  Only emit the assert_lazy_var_init / assert_lazy_var_not_init opcodes for block-scoped locals that need the TDZ.


To see what sort of code this produces:


> try { foo; } catch (e) { e; }
28 m_instructions; 224 bytes at 0x1bcb310; 1 parameter(s); 4 callee register(s); 0 variable(s)

[   0] enter
[   1] mov		 r0, Undefined(@k0)
[   4] resolve_global	 r0, foo(@id0)
[  10] jmp		 16(->26)
[  12] catch		 r1
[  14] init_lazy_reg	 r2
[  16] init_lazy_reg	 r3
[  18] mov		 r2, r1
[  21] mov		 r0, r2
[  24] tear_off_scope	 r3
[  26] end		 r0


Here r2 is for the one block-scoped identifier, "e", and r3 is the lazy register for the reified scope.  In this case the block scope does not get reified, as there is no nested function expression or call to eval.


> try { foo; } catch (e) { (function(s){return eval(s);}) }
32 m_instructions; 256 bytes at 0x1bd5550; 1 parameter(s); 4 callee register(s); 0 variable(s)

[   0] enter
[   1] mov		 r0, Undefined(@k0)
[   4] resolve_global	 r0, foo(@id0)
[  10] jmp		 20(->30)
[  12] catch		 r1
[  14] init_lazy_reg	 r2
[  16] init_lazy_reg	 r3
[  18] mov		 r2, r1
[  21] reify_scope	 r3, Cell: 0x7f660d17fca0(@k1), r2
[  25] new_func_exp	 r0, f0
[  28] tear_off_scope	 r3
[  30] end		 r0

In this case we do get a reified scope, before the new_func_exp.  It is torn off afterwards.


> (function () {try { foo; } catch (e) { (function(s){return eval(s);})}})()
[...]
40 m_instructions; 320 bytes at 0x1bd8aa0; 1 parameter(s); 7 callee register(s); 3 variable(s)

[   0] enter
[   1] init_lazy_reg	 r0
[   3] init_lazy_reg	 r2
[   5] init_lazy_reg	 r1
[   7] create_activation r0
[   9] convert_this	 r-7
[  11] resolve		 r3, foo(@id0)
[  15] jmp		 20(->35)
[  17] catch		 r3
[  19] init_lazy_reg	 r4
[  21] init_lazy_reg	 r5
[  23] mov		 r4, r3
[  26] reify_scope	 r5, Cell: 0x7f660d17fbe0(@k0), r4
[  30] new_func_exp	 r6, f0
[  33] tear_off_scope	 r5
[  35] tear_off_activation	 r0, r2
[  38] ret		 Undefined(@k1)

Here is the same thing but in function code instead of global code.  We see that the function activation was created eagerly, though that is only because of the use of eval.



A different example:

> (function () {var a = 10; try { throw 20; } catch (b) { return (function(s){return a + b;})()}})()
[...]
60 m_instructions; 480 bytes at 0x1be0760; 1 parameter(s); 15 callee register(s); 4 variable(s)

[   0] enter
[   1] init_lazy_reg	 r0
[   3] init_lazy_reg	 r2
[   5] init_lazy_reg	 r1
[   7] mov		 r3, Int32: 10(@k0)
[  10] throw		 Int32: 20(@k1)
[  12] jmp		 43(->55)
[  14] catch		 r4
[  16] init_lazy_reg	 r5
[  18] init_lazy_reg	 r6
[  20] mov		 r5, r4
[  23] create_activation r0
[  25] reify_scope	 r6, Cell: 0x7f660d17f8e0(@k2), r5
[  29] new_func_exp	 r7, f0
[  32] mov		 r8, Undefined(@k3)
[  35] call	 r7, 1, 15
[  41] op_call_put_result		 r7
[  44] tear_off_scope	 r6
[  46] jmp		 2(->48)
[  48] tear_off_activation	 r0, r2
[  51] ret		 r7
[  53] tear_off_scope	 r6
[  55] tear_off_activation	 r0, r2
[  58] ret		 Undefined(@k3)

Constants:
   k0 = Int32: 10
   k1 = Int32: 20
   k2 = Cell: 0x7f660d17f8e0
   k3 = Undefined
[...]
30

Here we see lazy reification of the activation and of the scope, and corresponding tearoff.  There is no more jmp_scopes because things are getting too complicated for an opcode: better to emit what the opcode should do, directly.

[Build Bot]

Comment on attachment 132839 [details]
Patch

Attachment 132839 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/11994360

[Andy Wingo]

Created attachment 133011 [details]
Patch

[Andy Wingo]

Changes in updated patch:

  * Remove op_assert_lazy_reg_not_init.  I was under the mistaken impression that it was permitted to assign to const variables.  No write barrier is needed, because the compiler should throw an error on an attempt to mutate a read-only binding.  If it goes through the generic path the runtime will see isReadOnly() on the symboltableentry.

  * Attempt to fix the llint.

  * We no longer clear registers when leaving a block scope.

  * An attempt to tame the combinatoric explosion of ResolveResult::type() by separating type in to type proper and attributes (e.g. read-only, needs-barrier, is-arguments, etc).

[Early Warning System Bot]

Comment on attachment 133011 [details]
Patch

Attachment 133011 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/12035396

[Early Warning System Bot]

Comment on attachment 133011 [details]
Patch

Attachment 133011 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/12086336

[Philippe Normand]

Comment on attachment 133011 [details]
Patch

Attachment 133011 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/12034367

[Andy Wingo]

Created attachment 133014 [details]
Patch

[Andy Wingo]

The last patch was b0rken.  Uploading again!

[Andy Wingo]

Created attachment 133795 [details]
Patch

[Andy Wingo]

The new patch gives good errors when a user tries to access an uninitialized block-scoped local.

Next up is to fix the scope depth stuff, and then this patch will be fully baked.  Review in advance is appreciated though :)

[Andy Wingo]

Created attachment 133822 [details]
Patch

[Andy Wingo]

Latest patch avoids init_lazy_reg for block-scoped locals that don't need the TDZ.

[Filip Pizlo]

Comment on attachment 133822 [details]
Patch

This looks like it needs a massive rebase.