DFG should be able to constant fold Object.create() with a constant prototype operand
authorrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 16 Apr 2019 00:28:47 +0000 (00:28 +0000)
committerrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 16 Apr 2019 00:28:47 +0000 (00:28 +0000)
https://bugs.webkit.org/show_bug.cgi?id=196886

Reviewed by Yusuke Suzuki.

JSTests:

Note that this new benchmark does not currently see a speedup with inlining removed.
The reason is that we do not yet have inline caching for Object.create(), we only optimize it when the DFG can see statically the prototype being passed.

* microbenchmarks/object-create-constant-prototype.js: Added.
(test):

Source/JavaScriptCore:

It is a fairly simple and limited patch, as it only works when the DFG can prove the exact object used as prototype.
But when it applies it can be a significant win:
                                                Baseline                   Optim
object-create-constant-prototype              3.6082+-0.0979     ^      1.6947+-0.0756        ^ definitely 2.1292x faster
object-create-null                           11.4492+-0.2510     ?     11.5030+-0.2402        ?
object-create-unknown-object-prototype       15.6067+-0.1851     ?     15.7500+-0.2322        ?
object-create-untyped-prototype               8.8873+-0.1240     ?      8.9806+-0.1202        ? might be 1.0105x slower
<geometric>                                   8.6967+-0.1208     ^      7.2408+-0.1367        ^ definitely 1.2011x faster

The only subtlety is that we need to to access the StructureCache concurrently from the compiler thread (see https://bugs.webkit.org/show_bug.cgi?id=186199)
I solved this with a simple lock, taken when the compiler thread tries to read it, and when the main thread tries to modify it.
I expect it to be extremely low contention, but will watch the bots just in case.
The lock is taken neither when the main thread is only reading the cache (it has no-one to race with), nor when the GC purges it of dead entries (it does not free anything while a compiler thread is in the middle of a phase).

* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGConstantFoldingPhase.cpp:
(JSC::DFG::ConstantFoldingPhase::foldConstants):
* runtime/StructureCache.cpp:
(JSC::StructureCache::createEmptyStructure):
(JSC::StructureCache::tryEmptyObjectStructureForPrototypeFromCompilerThread):
* runtime/StructureCache.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@244313 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JSTests/ChangeLog
JSTests/microbenchmarks/object-create-constant-prototype.js [new file with mode: 0644]
JSTests/stress/object-create-undefined.js
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
Source/JavaScriptCore/runtime/StructureCache.cpp
Source/JavaScriptCore/runtime/StructureCache.h

index ea428c7..a9c7fb8 100644 (file)
@@ -1,3 +1,16 @@
+2019-04-15  Robin Morisset  <rmorisset@apple.com>
+
+        DFG should be able to constant fold Object.create() with a constant prototype operand
+        https://bugs.webkit.org/show_bug.cgi?id=196886
+
+        Reviewed by Yusuke Suzuki.
+
+        Note that this new benchmark does not currently see a speedup with inlining removed.
+        The reason is that we do not yet have inline caching for Object.create(), we only optimize it when the DFG can see statically the prototype being passed.
+
+        * microbenchmarks/object-create-constant-prototype.js: Added.
+        (test):
+
 2019-04-15  Tadeu Zagallo  <tzagallo@apple.com>
 
         Incremental bytecode cache should not append function updates when loaded from memory
diff --git a/JSTests/microbenchmarks/object-create-constant-prototype.js b/JSTests/microbenchmarks/object-create-constant-prototype.js
new file mode 100644 (file)
index 0000000..014d878
--- /dev/null
@@ -0,0 +1,9 @@
+function test(prototype)
+{
+    return Object.create(prototype);
+}
+
+var prototype = {foo: 42};
+for (var i = 0; i < 1e5; ++i) {
+    test(prototype);
+}
index 9aa3c21..252ba07 100644 (file)
@@ -24,3 +24,10 @@ for (var i = 0; i < 1e4; ++i) {
         test(undefined);
     }, `TypeError: Object prototype may only be an Object or null.`);
 }
+for (var i = 0; i < 1e4; ++i) {
+    // Some folding does not happen in the non-inlined version, so this can test a different path through the compiler
+    // than the previous loop.
+    shouldThrow(() => {
+        Object.create(undefined);
+    }, `TypeError: Object prototype may only be an Object or null.`);
+}
index b6ba2be..0a1c5c8 100644 (file)
@@ -1,3 +1,34 @@
+2019-04-15  Robin Morisset  <rmorisset@apple.com>
+
+        DFG should be able to constant fold Object.create() with a constant prototype operand
+        https://bugs.webkit.org/show_bug.cgi?id=196886
+
+        Reviewed by Yusuke Suzuki.
+
+
+        It is a fairly simple and limited patch, as it only works when the DFG can prove the exact object used as prototype.
+        But when it applies it can be a significant win:
+                                                        Baseline                   Optim                                       
+        object-create-constant-prototype              3.6082+-0.0979     ^      1.6947+-0.0756        ^ definitely 2.1292x faster
+        object-create-null                           11.4492+-0.2510     ?     11.5030+-0.2402        ?
+        object-create-unknown-object-prototype       15.6067+-0.1851     ?     15.7500+-0.2322        ?
+        object-create-untyped-prototype               8.8873+-0.1240     ?      8.9806+-0.1202        ? might be 1.0105x slower
+        <geometric>                                   8.6967+-0.1208     ^      7.2408+-0.1367        ^ definitely 1.2011x faster
+
+        The only subtlety is that we need to to access the StructureCache concurrently from the compiler thread (see https://bugs.webkit.org/show_bug.cgi?id=186199)
+        I solved this with a simple lock, taken when the compiler thread tries to read it, and when the main thread tries to modify it.
+        I expect it to be extremely low contention, but will watch the bots just in case.
+        The lock is taken neither when the main thread is only reading the cache (it has no-one to race with), nor when the GC purges it of dead entries (it does not free anything while a compiler thread is in the middle of a phase).
+
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+        * dfg/DFGConstantFoldingPhase.cpp:
+        (JSC::DFG::ConstantFoldingPhase::foldConstants):
+        * runtime/StructureCache.cpp:
+        (JSC::StructureCache::createEmptyStructure):
+        (JSC::StructureCache::tryEmptyObjectStructureForPrototypeFromCompilerThread):
+        * runtime/StructureCache.h:
+
 2019-04-15  Devin Rousso  <drousso@apple.com>
 
         Web Inspector: fake value descriptors for promises add a catch handler, preventing "rejectionhandled" events from being fired
index cf05921..0fc9be6 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013-2018 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -43,6 +43,7 @@
 #include "Operations.h"
 #include "PutByIdStatus.h"
 #include "StringObject.h"
+#include "StructureCache.h"
 #include "StructureRareDataInlines.h"
 #include <wtf/BooleanLattice.h>
 #include <wtf/CheckedArithmetic.h>
@@ -2586,17 +2587,20 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
 
     case ObjectCreate: {
         if (JSValue base = forNode(node->child1()).m_value) {
-            if (base.isNull()) {
-                JSGlobalObject* globalObject = m_graph.globalObjectFor(node->origin.semantic);
+            JSGlobalObject* globalObject = m_graph.globalObjectFor(node->origin.semantic);
+            Structure* structure = nullptr;
+            if (base.isNull())
+                structure = globalObject->nullPrototypeObjectStructure();
+            else if (base.isObject())
+                structure = globalObject->vm().structureCache.emptyObjectStructureConcurrently(globalObject, base.getObject(), JSFinalObject::defaultInlineCapacity());
+            
+            if (structure) {
                 m_state.setFoundConstants(true);
                 if (node->child1().useKind() == UntypedUse)
                     didFoldClobberWorld();
-                setForNode(node, globalObject->nullPrototypeObjectStructure());
+                setForNode(node, structure);
                 break;
             }
-            // FIXME: We should get a structure for a constant prototype. We need to allow concurrent
-            // access to StructureCache from compiler threads.
-            // https://bugs.webkit.org/show_bug.cgi?id=186199
         }
         if (node->child1().useKind() == UntypedUse)
             clobberWorld();
index 5e7e481..4a2f142 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2012-2018 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -39,6 +39,7 @@
 #include "GetByIdStatus.h"
 #include "JSCInlines.h"
 #include "PutByIdStatus.h"
+#include "StructureCache.h"
 
 namespace JSC { namespace DFG {
 
@@ -750,15 +751,18 @@ private:
 
             case ObjectCreate: {
                 if (JSValue base = m_state.forNode(node->child1()).m_value) {
-                    if (base.isNull()) {
-                        JSGlobalObject* globalObject = m_graph.globalObjectFor(node->origin.semantic);
-                        node->convertToNewObject(m_graph.registerStructure(globalObject->nullPrototypeObjectStructure()));
+                    JSGlobalObject* globalObject = m_graph.globalObjectFor(node->origin.semantic);
+                    Structure* structure = nullptr;
+                    if (base.isNull())
+                        structure = globalObject->nullPrototypeObjectStructure();
+                    else if (base.isObject())
+                        structure = globalObject->vm().structureCache.emptyObjectStructureConcurrently(globalObject, base.getObject(), JSFinalObject::defaultInlineCapacity());
+                    
+                    if (structure) {
+                        node->convertToNewObject(m_graph.registerStructure(structure));
                         changed = true;
                         break;
                     }
-                    // FIXME: We should get a structure for a constant prototype. We need to allow concurrent
-                    // access to StructureCache from compiler threads.
-                    // https://bugs.webkit.org/show_bug.cgi?id=186199
                 }
                 break;
             }
index 7dcdea2..b5584c3 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013-2017 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -26,9 +26,9 @@
 #include "config.h"
 #include "StructureCache.h"
 
-#include "IndexingType.h"
 #include "JSGlobalObject.h"
 #include "JSCInlines.h"
+#include <wtf/Locker.h>
 
 namespace JSC {
 
@@ -36,6 +36,7 @@ inline Structure* StructureCache::createEmptyStructure(JSGlobalObject* globalObj
 {
     RELEASE_ASSERT(!!prototype); // We use nullptr inside the HashMap for prototype to mean poly proto, so user's of this API must provide non-null prototypes.
 
+    // We don't need to lock here because only the main thread can get here, and only the main thread can mutate the cache
     PrototypeKey key { makePolyProtoStructure ? nullptr : prototype, executable, inlineCapacity, classInfo, globalObject };
     if (Structure* structure = m_structures.get(key)) {
         if (makePolyProtoStructure) {
@@ -58,11 +59,24 @@ inline Structure* StructureCache::createEmptyStructure(JSGlobalObject* globalObj
         structure = Structure::create(
             vm, globalObject, prototype, typeInfo, classInfo, indexingType, inlineCapacity);
     }
+    auto locker = holdLock(m_lock);
     m_structures.set(key, structure);
-
     return structure;
 }
 
+Structure* StructureCache::emptyObjectStructureConcurrently(JSGlobalObject* globalObject, JSObject* prototype, unsigned inlineCapacity)
+{
+    RELEASE_ASSERT(!!prototype); // We use nullptr inside the HashMap for prototype to mean poly proto, so user's of this API must provide non-null prototypes.
+    
+    PrototypeKey key { prototype, nullptr, inlineCapacity, JSFinalObject::info(), globalObject };
+    auto locker = holdLock(m_lock);
+    if (Structure* structure = m_structures.get(key)) {
+        ASSERT(prototype->mayBePrototype());
+        return structure;
+    }
+    return nullptr;
+}
+
 Structure* StructureCache::emptyStructureForPrototypeFromBaseStructure(JSGlobalObject* globalObject, JSObject* prototype, Structure* baseStructure)
 {
     // We currently do not have inline capacity static analysis for subclasses and all internal function constructors have a default inline capacity of 0.
index 8e7e365..7a583a0 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013-2017 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2019 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -29,6 +29,7 @@
 #include "JSTypeInfo.h"
 #include "PrototypeKey.h"
 #include "WeakGCMap.h"
+#include <wtf/Lock.h>
 #include <wtf/TriState.h>
 
 namespace JSC {
@@ -51,12 +52,14 @@ public:
 
     JS_EXPORT_PRIVATE Structure* emptyObjectStructureForPrototype(JSGlobalObject*, JSObject*, unsigned inlineCapacity, bool makePolyProtoStructure = false, FunctionExecutable* = nullptr);
     JS_EXPORT_PRIVATE Structure* emptyStructureForPrototypeFromBaseStructure(JSGlobalObject*, JSObject*, Structure*);
+    JS_EXPORT_PRIVATE Structure* emptyObjectStructureConcurrently(JSGlobalObject*, JSObject* prototype, unsigned inlineCapacity);
 
 private:
     Structure* createEmptyStructure(JSGlobalObject*, JSObject* prototype, const TypeInfo&, const ClassInfo*, IndexingType, unsigned inlineCapacity, bool makePolyProtoStructure, FunctionExecutable*);
 
     using StructureMap = WeakGCMap<PrototypeKey, Structure>;
     StructureMap m_structures;
+    Lock m_lock;
 };
 
 } // namespace JSC