Bug 14868 – Import variable lookup optimizations from KJS

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Cameron Zwarich (cpst)]

We should take advantage of the recent optimizations to KJS.

[Cameron Zwarich (cpst)]

Created attachment 15815 [details]
Proposed patch

Here is a first attempt at a patch to import these changes into WebKit, most likely into the feature branch. I wasn't really sure how to deal with all of the different coding styles, so I am sure there are some problems in that area. I ported over all of our later changes where we diverge with KJS, so this passes all of our JSC and layout tests, with a few exceptions:

* Two of the JSC tests require function declarations to be processed in the scope of a with block, whereas this seems incorrect from my reading of the ECMA spec. Internet Explorer also agrees with my understanding of the spec and the new code, so it is unlikely that there would be any compatibility issues with this change.

* In the fast/js/kde/function test, there was a strange test case about nested function declarations. The new code fails this test, but the behaviour expected in the test case seems completely wrong to me. I don't really even know why it's there.

I've added the new and updated tests from KDE, which give pretty good coverage of any changes in functionality, but I would still like to make a set of tests with better code coverage of nodes.cpp than the current tests.

[Oliver Hunt]

Comment on attachment 15815 [details]
Proposed patch

Need an extra space for indenting the comment at
+  if (!body->builtSymbolList()) {
+   // now handle other locals (functions, variables)
+    body->processDecls(&newExec);

I'm less keen on +  //### Document this, ugh.

function.h should also probably have you copyright info now

ActivationImp
  putLocal -> replace assert with ASSERT
  putLocalChecked -> return on a new line
  isLocalReadOnly -> i'm not sure but i believe VS will want !!(_locals[propertyID].attr & ReadOnly)

VarAccessNode
  optimizeLocalAccess -> no braces for "} else {" (and the closing '}')

NonLocalVarAccessNode
  evaluateReference -> s/assert/ASSERT/

nodes.h should possibly gain your copyright

there are quite a few other places where assert is used instead of ASSERT

There are quite a few portions of this patch that look fairly trivial to make independent of this major patch -- for instance the [int] optimisation seems completely distinct from the improved scope lookup

[Cameron Zwarich (cpst)]

Created attachment 15958 [details]
Revised proposed patch

(In reply to comment #2)
> (From update of attachment 15815 [details] [edit])
> Need an extra space for indenting the comment at
> +  if (!body->builtSymbolList()) {
> +   // now handle other locals (functions, variables)
> +    body->processDecls(&newExec);

Fixed.

> I'm less keen on +  //### Document this, ugh.

I removed it. The same line it is commenting is without comment in the current WebKit tree.

> function.h should also probably have you copyright info now

Done.

> ActivationImp
>   putLocal -> replace assert with ASSERT

Fixed.

>   putLocalChecked -> return on a new line

Fixed.

>   isLocalReadOnly -> i'm not sure but i believe VS will want
> !!(_locals[propertyID].attr & ReadOnly)

Fixed.

> VarAccessNode
>   optimizeLocalAccess -> no braces for "} else {" (and the closing '}')

Fixed. I also made it so there are no lone returns inside of else if and else blocks.

> NonLocalVarAccessNode
>   evaluateReference -> s/assert/ASSERT/

Fixed.

> nodes.h should possibly gain your copyright

Done.

> there are quite a few other places where assert is used instead of ASSERT

I changed them all.

> There are quite a few portions of this patch that look fairly trivial to make
> independent of this major patch -- for instance the [int] optimisation seems
> completely distinct from the improved scope lookup

Can you be more specific?

[Mark Rowe (bdash)]

Created attachment 16192 [details]
Reduction showing bug in patch

The attachment contains two JavaScript files that demonstrate a bug in this patch.  Running "testkjs foo.js foo.js" with the patch applied gives the output:
--> undefined
--> 151
OK.

Without the patch it gives:
--> 202
--> 201
OK.

The numbers are timing-related so the different values are expected.  What is incorrect is "undefined" being displayed in the first instance.

[Mark Rowe (bdash)]

Created attachment 16194 [details]
Updated reduction, now with less code!

[Mark Rowe (bdash)]

Created attachment 16195 [details]
Further reduction after some insight from Maciej

[Cameron Zwarich (cpst)]

Thanks for the nicely reduced test case. I should be able to find the problem today. A few things to note:

1) It only occurs when result is being assigned a new value. If I make it var result = ... then it behaves properly. If I do the print inline then it behaves properly.

2) It does not require the function being called to be anonymous. If I make a normal function definition for f, then it still occurs.

3) It works every subsequent time in the interpreter, and also if it is called twice in the same file.

4) It only works with 28 or more assignments in the function the way it is. However, for each additional declaration at the top level (including the function itself if it is declared), it takes one less assignment to trigger the bug. But after adding too many, it gets harder to trigger the bug.

[Maciej Stachowiak]

I figured out exactly what the problem is. The sequence of steps in an assignment under the patch is:

- Left side is evaluated to a reference, this involves getting a writeable PropertySlot pointing into the global object's PropertyMap hashtable
- Right side is evaluated, adding new properties to the global object and causing a rehash of the global PropertyMap
- As a result, the PropertySlot points to the right place

This can be fixed by not using writeable PropertySlots for HashMap properties, it might be too hard to be worth the effort to make it actually work right (you would need a way to detect if it has been invalidated before writing). I fixed these places and verified that you still get an 18% improvement on JS iBench. There may be other trouble spots too though. I didn't think through whether giving direct access to an Array's storage is ok, for instance.

[Cameron Zwarich (cpst)]

I agree that it isn't worth it trying to make the hash table optimization work right, at least for now. We can just disable it. There is also a problem with having directly writeable array slots, due to the possibility of the array being resized.

I will make both changes and upload a new version of the patch.

[Cameron Zwarich (cpst)]

Created attachment 16203 [details]
Revised proposed patch

This hopefully fixes the problems with directly writeable slots in every place they might occur.

[Maciej Stachowiak]

Your new patch might have been slightly overzealous in removing it, I think direct access to __proto__ is still ok for instance (but perhaps irrelevant). Also, it would be nice to add a test case based on Mark's reduction to LayoutTests, and perhaps also one that reproduces a similar problem for arrays.

[Cameron Zwarich (cpst)]

Created attachment 16215 [details]
Revised proposed patch

Here's a revised patch. It has the following differences:

- it now patches cleanly against ToT.
- I cleaned up some style problems, like a few ASSERT usages that I somehow missed
- I added test cases for the direct write bugs. The array one wouldn't actually fail for any version of the code, because AssignBracketNode doesn't do direct writes.

I hope I didn't miss anything. There is only one bad thing of which I am aware. When I run the entirety of the layout tests or just fast/dom, fast/dom/constructors-overriding.html will sometimes crash, but I can't get it to crash on its own. The crash is in ActivationImp::mark(), which is modified by this patch. It doesn't seem to crash without the patch (I didn't try on my machine, I am just going by the build bot and Mark).

[Cameron Zwarich (cpst)]

I found a possible source for the GC crash. With a debug build, there are assertion failures at line 2026 of nodes.cpp, which is

        ASSERT(variableObject->getDirect(ident) || ident == exec->propertyNames().arguments);

[Geoffrey Garen]

FYI, the claim in this assertion is that a statement like

var x = 1;

should first create 'x', initialized to 'undefined', before the '= 1' assignment executes. This assert would trigger if processVarDecls did not run before evaluate, or if processVarDecls put 'x' in the wrong place, or if 'x' was deleted before evaluate ran.

[Maciej Stachowiak]

Geoff is working on reviewing the patch and cleaning it up to land (possibly in pieces).

[Geoffrey Garen]

Here are a few problems I've noticed with the patch so far:

1. The ASSERT mentioned above happens because some code calls getDirect on an ActivationImp, looking for a local variable. Since local variables are not stored in the PropertyMap, this call is not valid. It's easy enough to fix the ASSERT by changing it to use hasProperty. However, we need to audit all calls to getDirect and its ilk, since they are no longer valid in all cases.

2. As seen in JavaScriptCore/tests/mozilla/js1_5/Regress/regress-159334.js, a sufficiently long script causes stack overflow due to too much recursion in SemanticChecker::check because SemanticChecker::check uses recursion to follow arbitrary `next' pointers in a linked list. The same problem probably applies to other NodeVisitors. (The same problem does not apply to normal execution because normal execution follows `next' pointers in linked lists iteratively.)

3. The HashTraits for Identifier will cause crashes if used in other contexts since they do not ref/deref the UString::Rep*. They seem OK in this context, but I can't prove that.

Despite these problems, I see some parts of this patch that can land immediately. I'm going to try to break those off and land them.

[Geoffrey Garen]

Created attachment 16490 [details]
reduction

Reduction of the recursion crash.

[Darin Adler]

Comment on attachment 16215 [details]
Revised proposed patch

Thanks for this excellent work!

Geoff Garen is working on integrating this code. For now I'm going to clear the review flag on this patch; but he's on the case.

[Cameron Zwarich (cpst)]

This was dealt with long ago, and we are now on SquirrelFish, so we can definitely close this.