Attachment 342560 Details for Bug 186459 – Patch

[patch] Patch

bug-186459-20180613023511.patch (text/plain), 13.75 KB, created by Yusuke Suzuki on 2018-06-12 10:35:12 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Yusuke Suzuki

Created: 2018-06-12 10:35:12 PDT

Size: 13.75 KB

patch

obsolete

>Subversion Revision: 232754
>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index 3f8bd5eb921888574490ea15caf9ce77712e40af..e2d02fac04fce0ea7ae6091da55ac7d28abeba15 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,25 @@
>+2018-06-12  Yusuke Suzuki  <utatane.tea@gmail.com>
>+
>+        [DFG] Fold GetByVal if Array is CoW
>+        https://bugs.webkit.org/show_bug.cgi?id=186459
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        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-06-11  Saam Barati  <sbarati@apple.com>
> 
>         Reduce graph size by replacing terminal nodes in blocks that have a ForceOSRExit with Unreachable
>diff --git a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
>index 3ccfaf6e48335392402a3170c6e748c4e0e78fed..6fa6fd38f8b06d5acff37533d70148e0546cb9b0 100644
>--- a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
>+++ b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
>@@ -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,90 @@ 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;
>+                int32_t index = indexConstant.asInt32();
>+
>+                // 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 later. If the indexing mode is CoW, the butterfly is
>+                // definitely JSImmutableButterfly since we do not have a transition from non-CoW to CoW.
>+                StructureID structureIDEarly = array->structureID();
>+                if (isNuked(structureIDEarly))
>+                    return false;
>+
>+                // To keep immutableButterfly alive, we first cast it to JSImmutableButterfly even if a butterfly is not
>+                // JSImmutableButterfly.
>+                WTF::loadLoadFence();
>+                JSImmutableButterfly* immutableButterfly = JSImmutableButterfly::fromButterfly(array->butterfly());
>+
>+                WTF::loadLoadFence();
>+                StrutureID structureIDLate = array->structureID();
>+
>+                if (strutureIDEarly != structureIDLate)
>+                    return false;
>+
>+                Structure* structure = array->structure(m_vm);
>+                if (!isCopyOnWrite(structure->indexingMode()))
>+                    return false;
>+
>+                if (static_cast<unsigned>(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);
>diff --git a/JSTests/ChangeLog b/JSTests/ChangeLog
>index a13eb29736b08503294cfe8ce9ce6e6efed8591f..cccf2717f7969f652bb6bee1831a20648f4fd0f8 100644
>--- a/JSTests/ChangeLog
>+++ b/JSTests/ChangeLog
>@@ -1,3 +1,39 @@
>+2018-06-12  Yusuke Suzuki  <utatane.tea@gmail.com>
>+
>+        [DFG] Fold GetByVal if Array is CoW
>+        https://bugs.webkit.org/show_bug.cgi?id=186459
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        * 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-06-12  Yusuke Suzuki  <utatane.tea@gmail.com>
> 
>         Update test262 for Array#sort
>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
>index 0000000000000000000000000000000000000000..f72c5768bcd835593efa3351094dc2821ecd7976
>--- /dev/null
>+++ b/JSTests/stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds-foldable.js
>@@ -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
>index 0000000000000000000000000000000000000000..400eeda658ca5ff1d87b208ddcb393e5d1ce4988
>--- /dev/null
>+++ b/JSTests/stress/folding-get-by-val-with-immutable-butterfly-out-of-bounds.js
>@@ -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
>index 0000000000000000000000000000000000000000..2114fa790db4803f50ff5413809f40df6a7ee5a8
>--- /dev/null
>+++ b/JSTests/stress/folding-get-by-val-with-immutable-butterfly-with-types.js
>@@ -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
>index 0000000000000000000000000000000000000000..cf09b55166abd8498cfa79a872d10cf48aa8c26a
>--- /dev/null
>+++ b/JSTests/stress/folding-get-by-val-with-immutable-butterfly.js
>@@ -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);

Actions: View | Formatted Diff | Diff

Attachments on bug 186459: 342367 | 342386 | 342516 | 342524 | 342547 | 342560 | 342561 | 342578 | 342623