[DFG] Fold GetByVal if Array is CoW
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 20 Jul 2018 21:25:19 +0000 (21:25 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 20 Jul 2018 21:25:19 +0000 (21:25 +0000)
https://bugs.webkit.org/show_bug.cgi?id=186459

Reviewed by Saam Barati.

JSTests:

* stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds-foldable.js: Added.
(shouldBe):
(test0):
(test1):
(test2):
(test3):
(test4):
(test5):
* stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds.js: Added.
(shouldBe):
(test0):
(test1):
(test2):
(test3):
(test4):
(test5):
* stress/folding-get-by-val-with-immutable-butterfly-with-types.js: Added.
(shouldBe):
(test0):
(test1):
(test2):
(test3):
(test4):
(test5):
* stress/folding-get-by-val-with-immutable-butterfly.js: Added.
(shouldBe):
(checking):
(test):

Source/JavaScriptCore:

CoW indexing type means that we now tracks the changes in CoW Array by structure. So DFG has a chance to
fold GetByVal if the given array is CoW. This patch folds GetByVal onto the CoW Array. If the structure
is watched and the butterfly is JSImmutableButterfly, we can load the value from this butterfly.

This can be useful since these CoW arrays are used for a storage for constants. Constant-indexed access
to these constant arrays can be folded into an actual constant by this patch.

                                   baseline                  patched

template_string.es6          4993.9853+-147.5308   ^    824.1685+-44.1839       ^ definitely 6.0594x faster
template_string_tag.es5        67.0822+-2.0100     ^      9.3540+-0.5376        ^ definitely 7.1715x faster

* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):

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

JSTests/ChangeLog
JSTests/stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds-foldable.js [new file with mode: 0644]
JSTests/stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds.js [new file with mode: 0644]
JSTests/stress/folding-get-by-val-with-immutable-butterfly-with-types.js [new file with mode: 0644]
JSTests/stress/folding-get-by-val-with-immutable-butterfly.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h

index a2c16af..206fbed 100644 (file)
@@ -1,3 +1,39 @@
+2018-07-20  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [DFG] Fold GetByVal if Array is CoW
+        https://bugs.webkit.org/show_bug.cgi?id=186459
+
+        Reviewed by Saam Barati.
+
+        * stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds-foldable.js: Added.
+        (shouldBe):
+        (test0):
+        (test1):
+        (test2):
+        (test3):
+        (test4):
+        (test5):
+        * stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds.js: Added.
+        (shouldBe):
+        (test0):
+        (test1):
+        (test2):
+        (test3):
+        (test4):
+        (test5):
+        * stress/folding-get-by-val-with-immutable-butterfly-with-types.js: Added.
+        (shouldBe):
+        (test0):
+        (test1):
+        (test2):
+        (test3):
+        (test4):
+        (test5):
+        * stress/folding-get-by-val-with-immutable-butterfly.js: Added.
+        (shouldBe):
+        (checking):
+        (test):
+
 2018-07-20  Saam Barati  <sbarati@apple.com>
 
         CompareEq should be using KnownOtherUse instead of OtherUse
diff --git a/JSTests/stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds-foldable.js b/JSTests/stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds-foldable.js
new file mode 100644 (file)
index 0000000..f72c576
--- /dev/null
@@ -0,0 +1,56 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+var array0 = [1, 2, 3, 4, 5];
+var array1 = [1.2, 2.3, 3.4, 4.5, 5.6];
+var array2 = ["Hello", "New", "World", "Cappuccino", "Cocoa"];
+var array3 = [null, null, null, null, null];
+var array4 = [undefined, undefined, undefined, undefined, undefined];
+var array5 = [false, true, false, true, false];
+
+function test0()
+{
+    return array0[5];
+}
+noInline(test0);
+
+function test1()
+{
+    return array1[5];
+}
+noInline(test1);
+
+function test2()
+{
+    return array2[5];
+}
+noInline(test2);
+
+function test3()
+{
+    return array3[5];
+}
+noInline(test3);
+
+function test4()
+{
+    return array4[5];
+}
+noInline(test4);
+
+function test5()
+{
+    return array5[5];
+}
+noInline(test5);
+
+for (var i = 0; i < 1e5; ++i) {
+    shouldBe(test0(), undefined);
+    shouldBe(test1(), undefined);
+    shouldBe(test2(), undefined);
+    shouldBe(test3(), undefined);
+    shouldBe(test4(), undefined);
+    shouldBe(test5(), undefined);
+}
diff --git a/JSTests/stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds.js b/JSTests/stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds.js
new file mode 100644 (file)
index 0000000..400eeda
--- /dev/null
@@ -0,0 +1,66 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+var array0 = [1, 2, 3, 4, 5];
+var array1 = [1.2, 2.3, 3.4, 4.5, 5.6];
+var array2 = ["Hello", "New", "World", "Cappuccino", "Cocoa"];
+var array3 = [null, null, null, null, null];
+var array4 = [undefined, undefined, undefined, undefined, undefined];
+var array5 = [false, true, false, true, false];
+
+function test0()
+{
+    return array0[5];
+}
+noInline(test0);
+
+function test1()
+{
+    return array1[5];
+}
+noInline(test1);
+
+function test2()
+{
+    return array2[5];
+}
+noInline(test2);
+
+function test3()
+{
+    return array3[5];
+}
+noInline(test3);
+
+function test4()
+{
+    return array4[5];
+}
+noInline(test4);
+
+function test5()
+{
+    return array5[5];
+}
+noInline(test5);
+
+for (var i = 0; i < 1e5; ++i) {
+    shouldBe(test0(), undefined);
+    shouldBe(test1(), undefined);
+    shouldBe(test2(), undefined);
+    shouldBe(test3(), undefined);
+    shouldBe(test4(), undefined);
+    shouldBe(test5(), undefined);
+}
+// Breaking sane chains.
+Array.prototype[5] = 42;
+for (var i = 0; i < 1e5; ++i) {
+    shouldBe(test0(), 42);
+    shouldBe(test1(), 42);
+    shouldBe(test2(), 42);
+    shouldBe(test3(), 42);
+    shouldBe(test4(), 42);
+    shouldBe(test5(), 42);
+}
diff --git a/JSTests/stress/folding-get-by-val-with-immutable-butterfly-with-types.js b/JSTests/stress/folding-get-by-val-with-immutable-butterfly-with-types.js
new file mode 100644 (file)
index 0000000..2114fa7
--- /dev/null
@@ -0,0 +1,56 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+var array0 = [1, 2, 3, 4, 5];
+var array1 = [1.2, 2.3, 3.4, 4.5, 5.6];
+var array2 = ["Hello", "New", "World", "Cappuccino", "Cocoa"];
+var array3 = [null, null, null, null, null];
+var array4 = [undefined, undefined, undefined, undefined, undefined];
+var array5 = [false, true, false, true, false];
+
+function test0()
+{
+    return array0[0];
+}
+noInline(test0);
+
+function test1()
+{
+    return array1[0];
+}
+noInline(test1);
+
+function test2()
+{
+    return array2[0];
+}
+noInline(test2);
+
+function test3()
+{
+    return array3[0];
+}
+noInline(test3);
+
+function test4()
+{
+    return array4[0];
+}
+noInline(test4);
+
+function test5()
+{
+    return array5[0];
+}
+noInline(test5);
+
+for (var i = 0; i < 1e6; ++i) {
+    shouldBe(test0(), 1);
+    shouldBe(test1(), 1.2);
+    shouldBe(test2(), "Hello");
+    shouldBe(test3(), null);
+    shouldBe(test4(), undefined);
+    shouldBe(test5(), false);
+}
diff --git a/JSTests/stress/folding-get-by-val-with-immutable-butterfly.js b/JSTests/stress/folding-get-by-val-with-immutable-butterfly.js
new file mode 100644 (file)
index 0000000..cf09b55
--- /dev/null
@@ -0,0 +1,30 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+var array = [1, 2, 3, 4, 5];
+
+function checking(i)
+{
+    if (i === (1e6 - 1)) {
+        // array[0] = 42;
+        array.ok = 4000;
+    } else if (i === (2e6 - 4000)) {
+        array.hey = 4000;
+    } else if (i === (1e6 * 2)) {
+        array[0] = 42;
+    }
+}
+noInline(checking);
+
+function test(i)
+{
+    checking(i);
+    return array[0] + array[1];
+}
+noInline(test);
+
+for (var i = 0; i < 2e6; ++i)
+    shouldBe(test(i), 3);
+shouldBe(test(2e6), 44);
index 1d03a55..6f0132f 100644 (file)
@@ -1,5 +1,27 @@
 2018-07-20  Yusuke Suzuki  <utatane.tea@gmail.com>
 
+        [DFG] Fold GetByVal if Array is CoW
+        https://bugs.webkit.org/show_bug.cgi?id=186459
+
+        Reviewed by Saam Barati.
+
+        CoW indexing type means that we now tracks the changes in CoW Array by structure. So DFG has a chance to
+        fold GetByVal if the given array is CoW. This patch folds GetByVal onto the CoW Array. If the structure
+        is watched and the butterfly is JSImmutableButterfly, we can load the value from this butterfly.
+
+        This can be useful since these CoW arrays are used for a storage for constants. Constant-indexed access
+        to these constant arrays can be folded into an actual constant by this patch.
+
+                                           baseline                  patched
+
+        template_string.es6          4993.9853+-147.5308   ^    824.1685+-44.1839       ^ definitely 6.0594x faster
+        template_string_tag.es5        67.0822+-2.0100     ^      9.3540+-0.5376        ^ definitely 7.1715x faster
+
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+
+2018-07-20  Yusuke Suzuki  <utatane.tea@gmail.com>
+
         [JSC] Remove cellLock in JSObject::convertContiguousToArrayStorage
         https://bugs.webkit.org/show_bug.cgi?id=186602
 
index 3ccfaf6..83fd5c4 100644 (file)
@@ -28,6 +28,7 @@
 #if ENABLE(DFG_JIT)
 
 #include "ArrayConstructor.h"
+#include "ArrayPrototype.h"
 #include "DFGAbstractInterpreter.h"
 #include "DFGAbstractInterpreterClobberState.h"
 #include "DOMJITGetterSetter.h"
@@ -36,6 +37,7 @@
 #include "GetterSetter.h"
 #include "HashMapImpl.h"
 #include "JITOperations.h"
+#include "JSImmutableButterfly.h"
 #include "MathCommon.h"
 #include "NumberConstructor.h"
 #include "Operations.h"
@@ -1815,6 +1817,88 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
     case AtomicsStore:
     case AtomicsSub:
     case AtomicsXor: {
+        if (node->op() == GetByVal) {
+            auto foldGetByValOnCoWArray = [&] (Edge& arrayEdge, Edge& indexEdge) {
+                // FIXME: We can expand this for non x86 environments.
+                // https://bugs.webkit.org/show_bug.cgi?id=134641
+                if (!isX86())
+                    return false;
+
+                AbstractValue& arrayValue = forNode(arrayEdge);
+                if (node->arrayMode().arrayClass() != Array::OriginalCopyOnWriteArray)
+                    return false;
+
+                // Check the structure set is finite. This means that this constant's structure is watched and guaranteed the one of this set.
+                // When the structure is changed, this code should be invalidated. This is important since the following code relies on the
+                // constant object's is not changed.
+                if (!arrayValue.m_structure.isFinite())
+                    return false;
+
+                JSValue arrayConstant = arrayValue.value();
+                if (!arrayConstant)
+                    return false;
+
+                JSObject* array = jsDynamicCast<JSObject*>(m_vm, arrayConstant);
+                if (!array)
+                    return false;
+
+                JSValue indexConstant = forNode(indexEdge).value();
+                if (!indexConstant || !indexConstant.isInt32() || indexConstant.asInt32() < 0)
+                    return false;
+                uint32_t index = indexConstant.asUInt32();
+
+                // Check that the early StructureID is not nuked, get the butterfly, and check the late StructureID again.
+                // And we check the indexing mode of the structure. If the indexing mode is CoW, the butterfly is
+                // definitely JSImmutableButterfly.
+                StructureID structureIDEarly = array->structureID();
+                if (isNuked(structureIDEarly))
+                    return false;
+
+                WTF::loadLoadFence();
+                Butterfly* butterfly = array->butterfly();
+
+                WTF::loadLoadFence();
+                StructureID structureIDLate = array->structureID();
+
+                if (structureIDEarly != structureIDLate)
+                    return false;
+
+                if (!isCopyOnWrite(m_vm.getStructure(structureIDLate)->indexingMode()))
+                    return false;
+
+                JSImmutableButterfly* immutableButterfly = JSImmutableButterfly::fromButterfly(butterfly);
+                if (index < immutableButterfly->length()) {
+                    JSValue value = immutableButterfly->get(index);
+                    ASSERT(value);
+                    if (value.isCell())
+                        setConstant(node, *m_graph.freeze(value.asCell()));
+                    else
+                        setConstant(node, value);
+                    return true;
+                }
+
+                if (node->arrayMode().isOutOfBounds()) {
+                    JSGlobalObject* globalObject = m_graph.globalObjectFor(node->origin.semantic);
+                    Structure* arrayPrototypeStructure = globalObject->arrayPrototype()->structure(m_vm);
+                    Structure* objectPrototypeStructure = globalObject->objectPrototype()->structure(m_vm);
+                    if (arrayPrototypeStructure->transitionWatchpointSetIsStillValid()
+                        && objectPrototypeStructure->transitionWatchpointSetIsStillValid()
+                        && globalObject->arrayPrototypeChainIsSane()) {
+                        m_graph.registerAndWatchStructureTransition(arrayPrototypeStructure);
+                        m_graph.registerAndWatchStructureTransition(objectPrototypeStructure);
+                        didFoldClobberWorld();
+                        // Note that Array::Double and Array::Int32 return JSValue if array mode is OutOfBounds.
+                        setConstant(node, jsUndefined());
+                        return true;
+                    }
+                }
+                return false;
+            };
+
+            if (foldGetByValOnCoWArray(m_graph.child(node, 0), m_graph.child(node, 1)))
+                break;
+        }
+
         if (node->op() != GetByVal) {
             unsigned numExtraArgs = numExtraAtomicsArgs(node->op());
             Edge storageEdge = m_graph.child(node, 2 + numExtraArgs);