[DFG] Add ArrayIndexOf intrinsic
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 12 Jun 2017 03:58:23 +0000 (03:58 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 12 Jun 2017 03:58:23 +0000 (03:58 +0000)
https://bugs.webkit.org/show_bug.cgi?id=172421

Reviewed by Saam Barati.

JSTests:

* stress/array-indexof-array-prototype-change.js: Added.
(shouldBe):
(indexOfInt32):
* stress/array-indexof-have-a-bad-time-getter.js: Added.
(shouldBe):
(indexOfInt32):
* stress/array-indexof-have-a-bad-time.js: Added.
(shouldBe):
(indexOfInt32):
* stress/array-indexof-hole-with-prototype.js: Added.
(shouldBe):
(indexOf):
* stress/array-indexof-hole.js: Added.
(shouldBe):
(indexOf):
* stress/array-indexof-index.js: Added.
(shouldBe):
(indexOfInt32):
(indexOfDouble):
(indexOfString):
(indexOfObject):
(indexOfValue):
* stress/array-indexof-negative-index.js: Added.
(shouldBe):
(indexOfInt32):
(indexOfDouble):
(indexOfString):
(indexOfObject):
(indexOfValue):
* stress/array-indexof-non-int32-start-index.js: Added.
(shouldBe):
(indexOf):
(object.valueOf):
* stress/array-indexof-object-prototype-change.js: Added.
(shouldBe):
(indexOfInt32):
* stress/array-indexof-object.js: Added.
(shouldBe):
(indexOf):
* stress/array-indexof-original-array.js: Added.
(shouldBe):
(indexOfInt32):
* stress/array-indexof-string.js: Added.
(shouldBe):
(indexOf):
* stress/array-indexof-structure-change-convert.js: Added.
(shouldBe):
(indexOf):
* stress/array-indexof-structure-change.js: Added.
(shouldBe):
(indexOf):
* stress/array-indexof.js: Added.
(shouldBe):
(indexOf):

Source/JavaScriptCore:

This patch introduces ArrayIndexOfInstrinsic for DFG and FTL optimizations.
We emit array check and go fast path if the array is Array::Int32, Array::Double
or Array::Continugous. In addition, for Array::Int32 and Array::Double case,
we have inlined fast paths.

With updated ARES-6 Babylon,

Before
    firstIteration:     45.76 +- 3.87 ms
    averageWorstCase:   24.41 +- 2.17 ms
    steadyState:        8.01 +- 0.22 ms
After
    firstIteration:     45.64 +- 4.23 ms
    averageWorstCase:   23.03 +- 3.34 ms
    steadyState:        7.33 +- 0.34 ms

In SixSpeed.
                                 baseline                  patched

    map-set-lookup.es5      734.4701+-10.4383    ^    102.0968+-2.6357        ^ definitely 7.1939x faster
    map-set.es5              41.1396+-1.0558     ^     33.1916+-0.7986        ^ definitely 1.2395x faster
    map-set-object.es5       62.8317+-1.2518     ^     45.6944+-0.8369        ^ definitely 1.3750x faster

* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleIntrinsicCall):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGNode.h:
(JSC::DFG::Node::hasArrayMode):
* dfg/DFGNodeType.h:
* dfg/DFGOperations.cpp:
* dfg/DFGOperations.h:
* dfg/DFGPredictionPropagationPhase.cpp:
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileArrayIndexOf):
(JSC::DFG::SpeculativeJIT::speculateObject):
* dfg/DFGSpeculativeJIT.h:
(JSC::DFG::SpeculativeJIT::callOperation):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
(JSC::DFG::SpeculativeJIT::speculateInt32):
* ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileArrayIndexOf):
* jit/JITOperations.h:
* runtime/ArrayPrototype.cpp:
(JSC::ArrayPrototype::finishCreation):
* runtime/Intrinsic.cpp:
(JSC::intrinsicName):
* runtime/Intrinsic.h:

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

38 files changed:
JSTests/ChangeLog
JSTests/stress/array-indexof-array-prototype-change.js [new file with mode: 0644]
JSTests/stress/array-indexof-have-a-bad-time-getter.js [new file with mode: 0644]
JSTests/stress/array-indexof-have-a-bad-time.js [new file with mode: 0644]
JSTests/stress/array-indexof-hole-with-prototype.js [new file with mode: 0644]
JSTests/stress/array-indexof-hole.js [new file with mode: 0644]
JSTests/stress/array-indexof-index.js [new file with mode: 0644]
JSTests/stress/array-indexof-negative-index.js [new file with mode: 0644]
JSTests/stress/array-indexof-non-int32-start-index.js [new file with mode: 0644]
JSTests/stress/array-indexof-object-prototype-change.js [new file with mode: 0644]
JSTests/stress/array-indexof-object.js [new file with mode: 0644]
JSTests/stress/array-indexof-original-array.js [new file with mode: 0644]
JSTests/stress/array-indexof-string.js [new file with mode: 0644]
JSTests/stress/array-indexof-structure-change-convert.js [new file with mode: 0644]
JSTests/stress/array-indexof-structure-change.js [new file with mode: 0644]
JSTests/stress/array-indexof.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGDoesGC.cpp
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/dfg/DFGOperations.h
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGSafeToExecute.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/ftl/FTLCapabilities.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/JavaScriptCore/jit/JITOperations.h
Source/JavaScriptCore/runtime/ArrayPrototype.cpp
Source/JavaScriptCore/runtime/Intrinsic.cpp
Source/JavaScriptCore/runtime/Intrinsic.h

index dbeb90d..7c2b3b9 100644 (file)
@@ -1,3 +1,65 @@
+2017-06-09  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [DFG] Add ArrayIndexOf intrinsic
+        https://bugs.webkit.org/show_bug.cgi?id=172421
+
+        Reviewed by Saam Barati.
+
+        * stress/array-indexof-array-prototype-change.js: Added.
+        (shouldBe):
+        (indexOfInt32):
+        * stress/array-indexof-have-a-bad-time-getter.js: Added.
+        (shouldBe):
+        (indexOfInt32):
+        * stress/array-indexof-have-a-bad-time.js: Added.
+        (shouldBe):
+        (indexOfInt32):
+        * stress/array-indexof-hole-with-prototype.js: Added.
+        (shouldBe):
+        (indexOf):
+        * stress/array-indexof-hole.js: Added.
+        (shouldBe):
+        (indexOf):
+        * stress/array-indexof-index.js: Added.
+        (shouldBe):
+        (indexOfInt32):
+        (indexOfDouble):
+        (indexOfString):
+        (indexOfObject):
+        (indexOfValue):
+        * stress/array-indexof-negative-index.js: Added.
+        (shouldBe):
+        (indexOfInt32):
+        (indexOfDouble):
+        (indexOfString):
+        (indexOfObject):
+        (indexOfValue):
+        * stress/array-indexof-non-int32-start-index.js: Added.
+        (shouldBe):
+        (indexOf):
+        (object.valueOf):
+        * stress/array-indexof-object-prototype-change.js: Added.
+        (shouldBe):
+        (indexOfInt32):
+        * stress/array-indexof-object.js: Added.
+        (shouldBe):
+        (indexOf):
+        * stress/array-indexof-original-array.js: Added.
+        (shouldBe):
+        (indexOfInt32):
+        * stress/array-indexof-string.js: Added.
+        (shouldBe):
+        (indexOf):
+        * stress/array-indexof-structure-change-convert.js: Added.
+        (shouldBe):
+        (indexOf):
+        * stress/array-indexof-structure-change.js: Added.
+        (shouldBe):
+        (indexOf):
+        * stress/array-indexof.js: Added.
+        (shouldBe):
+        (indexOf):
+
 2017-06-11  Keith Miller  <keith_miller@apple.com>
 
         TypedArray constructor with string shouldn't throw
diff --git a/JSTests/stress/array-indexof-array-prototype-change.js b/JSTests/stress/array-indexof-array-prototype-change.js
new file mode 100644 (file)
index 0000000..1280d9b
--- /dev/null
@@ -0,0 +1,24 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOfInt32(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOfInt32);
+    var int32Array = [0, 1, 2, 3, 4, , 6, 7, 8, 9, 10, 11, 12];
+
+    var value = -1;
+    for (var i = 0; i < 1e5; ++i) {
+        shouldBe(indexOfInt32(int32Array, 5), value);
+        shouldBe(indexOfInt32(int32Array, 6), 6);
+        if (i === 1e4) {
+            Array.prototype[5] = 5;
+            value = 5;
+        }
+    }
+}());
diff --git a/JSTests/stress/array-indexof-have-a-bad-time-getter.js b/JSTests/stress/array-indexof-have-a-bad-time-getter.js
new file mode 100644 (file)
index 0000000..f5fb88d
--- /dev/null
@@ -0,0 +1,28 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOfInt32(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOfInt32);
+    var int32Array = [0, 1, 2, 3, 4, , 6, 7, 8, 9, 10, 11, 12];
+
+    var value = -1;
+    for (var i = 0; i < 1e5; ++i) {
+        shouldBe(indexOfInt32(int32Array, 5), value);
+        shouldBe(indexOfInt32(int32Array, 6), 6);
+        if (i === 1e4) {
+            value = 5;
+            Object.defineProperty(Array.prototype, 5, {
+                get: function () {
+                    return 5;
+                }
+            });
+        }
+    }
+}());
diff --git a/JSTests/stress/array-indexof-have-a-bad-time.js b/JSTests/stress/array-indexof-have-a-bad-time.js
new file mode 100644 (file)
index 0000000..9ed42f6
--- /dev/null
@@ -0,0 +1,35 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOfInt32(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOfInt32);
+    var int32Array = [0, 1, 2, 3, 4, , 6, 7, 8, 9, 10, 11, 12];
+
+    var value = -1;
+    for (var i = 0; i < 1e5; ++i) {
+        shouldBe(indexOfInt32(int32Array, 5), value);
+        shouldBe(indexOfInt32(int32Array, 6), 6);
+        if (i === 1e4) {
+            Object.defineProperty(Map.prototype, 5, {
+                get: function () {
+                    return 42;
+                }
+            });
+        }
+        if (i === 3e4) {
+            value = 5;
+            Object.defineProperty(Array.prototype, 5, {
+                get: function () {
+                    return 5;
+                }
+            });
+        }
+    }
+}());
diff --git a/JSTests/stress/array-indexof-hole-with-prototype.js b/JSTests/stress/array-indexof-hole-with-prototype.js
new file mode 100644 (file)
index 0000000..aa61b81
--- /dev/null
@@ -0,0 +1,35 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+Array.prototype[42] = 0;
+
+(function () {
+    function indexOf(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOf);
+
+    var array = new Array(100);
+    array.push(10);
+
+    for (var i = 0; i < 1e5; ++i)
+        shouldBe(indexOf(array, 0), 42);
+}());
+
+(function () {
+    function indexOf(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOf);
+
+    var array = new Array(100);
+    array.push(25.5);
+
+    for (var i = 0; i < 1e5; ++i)
+        shouldBe(indexOf(array, 0), 42);
+}());
diff --git a/JSTests/stress/array-indexof-hole.js b/JSTests/stress/array-indexof-hole.js
new file mode 100644 (file)
index 0000000..fb2aa2b
--- /dev/null
@@ -0,0 +1,33 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOf(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOf);
+
+    var array = new Array(100);
+    array.push(10);
+
+    for (var i = 0; i < 1e5; ++i)
+        shouldBe(indexOf(array, 0), -1);
+}());
+
+(function () {
+    function indexOf(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOf);
+
+    var array = new Array(100);
+    array.push(25.5);
+
+    for (var i = 0; i < 1e5; ++i)
+        shouldBe(indexOf(array, 0), -1);
+}());
diff --git a/JSTests/stress/array-indexof-index.js b/JSTests/stress/array-indexof-index.js
new file mode 100644 (file)
index 0000000..a1a56cd
--- /dev/null
@@ -0,0 +1,63 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOfInt32(array, value, index)
+    {
+        return array.indexOf(value, index);
+    }
+    noInline(indexOfInt32);
+
+    function indexOfDouble(array, value, index)
+    {
+        return array.indexOf(value, index);
+    }
+    noInline(indexOfDouble);
+
+    function indexOfString(array, value, index)
+    {
+        return array.indexOf(value, index);
+    }
+    noInline(indexOfString);
+
+    function indexOfObject(array, value, index)
+    {
+        return array.indexOf(value, index);
+    }
+    noInline(indexOfObject);
+
+    function indexOfValue(array, value, index)
+    {
+        return array.indexOf(value, index);
+    }
+    noInline(indexOfValue);
+
+    var key = {};
+    var int32Array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
+    var doubleArray = [0, 1, 2, 3, 4.2, 5, 6, 7, 8, 9, 10.5, 11, 12];
+    var stringArray = [ "cocoa", "cappuccino", "matcha", "rize", "kilimanjaro" ];
+    var objectArray = [ {}, {}, {}, {}, {}, key, {}, {}, {} ];
+    var valueArray = [ {}, {}, {}, {}, {}, null, {}, {}, {} ];
+
+    for (var i = 0; i < 1e5; ++i) {
+        shouldBe(indexOfInt32(int32Array, 3, 0), 3);
+        shouldBe(indexOfInt32(int32Array, 3, 8), -1);
+        shouldBe(indexOfDouble(doubleArray, 3, 0), 3);
+        shouldBe(indexOfDouble(doubleArray, 3, 20), -1);
+        shouldBe(indexOfDouble(doubleArray, 4.2, 8), -1);
+        shouldBe(indexOfDouble(doubleArray, 4.2, 0), 4);
+        shouldBe(indexOfDouble(doubleArray, 4.2, 20), -1);
+        shouldBe(indexOfString(stringArray, "cocoa", 0), 0);
+        shouldBe(indexOfString(stringArray, "cocoa", 4), -1);
+        shouldBe(indexOfString(stringArray, "cocoa", 20), -1);
+        shouldBe(indexOfObject(objectArray, key, 0), 5);
+        shouldBe(indexOfObject(objectArray, key, 6), -1);
+        shouldBe(indexOfObject(objectArray, key, 20), -1);
+        shouldBe(indexOfValue(valueArray, null, 0), 5);
+        shouldBe(indexOfValue(valueArray, null, 6), -1);
+        shouldBe(indexOfValue(valueArray, null, 20), -1);
+    }
+}());
diff --git a/JSTests/stress/array-indexof-negative-index.js b/JSTests/stress/array-indexof-negative-index.js
new file mode 100644 (file)
index 0000000..6de226b
--- /dev/null
@@ -0,0 +1,72 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOfInt32(array, value, index)
+    {
+        return array.indexOf(value, index);
+    }
+    noInline(indexOfInt32);
+
+    function indexOfDouble(array, value, index)
+    {
+        return array.indexOf(value, index);
+    }
+    noInline(indexOfDouble);
+
+    function indexOfString(array, value, index)
+    {
+        return array.indexOf(value, index);
+    }
+    noInline(indexOfString);
+
+    function indexOfObject(array, value, index)
+    {
+        return array.indexOf(value, index);
+    }
+    noInline(indexOfObject);
+
+    function indexOfValue(array, value, index)
+    {
+        return array.indexOf(value, index);
+    }
+    noInline(indexOfValue);
+
+    var key = {};
+    var int32Array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
+    var doubleArray = [0, 1, 2, 3, 4.2, 5, 6, 7, 8, 9, 10.5, 11, 12];
+    var stringArray = [ "cocoa", "cappuccino", "matcha", "rize", "kilimanjaro" ];
+    var objectArray = [ {}, {}, {}, {}, {}, key, {}, {}, {} ];
+    var valueArray = [ {}, {}, {}, {}, {}, null, {}, {}, {} ];
+
+    for (var i = 0; i < 1e5; ++i) {
+        shouldBe(indexOfInt32(int32Array, 3, -2), -1);
+        shouldBe(indexOfInt32(int32Array, 3, -10), 3);
+        shouldBe(indexOfInt32(int32Array, 3, -20), 3);
+        shouldBe(indexOfDouble(doubleArray, 3, -1), -1);
+        shouldBe(indexOfDouble(doubleArray, 3, -10), 3);
+        shouldBe(indexOfDouble(doubleArray, 3, -20), 3);
+        shouldBe(indexOfDouble(doubleArray, 4.2, -8), -1);
+        shouldBe(indexOfDouble(doubleArray, 4.2, -1), -1);
+        shouldBe(indexOfDouble(doubleArray, 4.2, -10), 4);
+        shouldBe(indexOfDouble(doubleArray, 4.2, -20), 4);
+        shouldBe(indexOfString(stringArray, "cocoa", -1), -1);
+        shouldBe(indexOfString(stringArray, "cocoa", -4), -1);
+        shouldBe(indexOfString(stringArray, "cocoa", -5), 0);
+        shouldBe(indexOfString(stringArray, "cocoa", -20), 0);
+        shouldBe(indexOfObject(objectArray, key, -1), -1);
+        shouldBe(indexOfObject(objectArray, key, -2), -1);
+        shouldBe(indexOfObject(objectArray, key, -3), -1);
+        shouldBe(indexOfObject(objectArray, key, -4), 5);
+        shouldBe(indexOfObject(objectArray, key, -6), 5);
+        shouldBe(indexOfObject(objectArray, key, -20), 5);
+        shouldBe(indexOfValue(valueArray, null, -1), -1);
+        shouldBe(indexOfValue(valueArray, null, -3), -1);
+        shouldBe(indexOfValue(valueArray, null, -4), 5);
+        shouldBe(indexOfValue(valueArray, null, -6), 5);
+        shouldBe(indexOfValue(valueArray, null, -20), 5);
+    }
+}());
diff --git a/JSTests/stress/array-indexof-non-int32-start-index.js b/JSTests/stress/array-indexof-non-int32-start-index.js
new file mode 100644 (file)
index 0000000..977d0a2
--- /dev/null
@@ -0,0 +1,21 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function indexOf(array, value, index)
+{
+    return array.indexOf(value, index);
+}
+noInline(indexOf);
+
+var object = {
+    valueOf()
+    {
+        return 0;
+    }
+}
+var array = [0,1,2,3,4,5,6,7,8,9];
+for (var i = 0; i < 1e5; ++i)
+    shouldBe(indexOf(array, 9, object), 9);
diff --git a/JSTests/stress/array-indexof-object-prototype-change.js b/JSTests/stress/array-indexof-object-prototype-change.js
new file mode 100644 (file)
index 0000000..b4c1acc
--- /dev/null
@@ -0,0 +1,24 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOfInt32(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOfInt32);
+    var int32Array = [0, 1, 2, 3, 4, , 6, 7, 8, 9, 10, 11, 12];
+
+    var value = -1;
+    for (var i = 0; i < 1e5; ++i) {
+        shouldBe(indexOfInt32(int32Array, 5), value);
+        shouldBe(indexOfInt32(int32Array, 6), 6);
+        if (i === 1e4) {
+            Object.prototype[5] = 5;
+            value = 5;
+        }
+    }
+}());
diff --git a/JSTests/stress/array-indexof-object.js b/JSTests/stress/array-indexof-object.js
new file mode 100644 (file)
index 0000000..26bba01
--- /dev/null
@@ -0,0 +1,42 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOf(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOf);
+
+    var array = [];
+    var object = {};
+    for (var i = 0; i < 100; ++i)
+        array.push({});
+    array.push(object);
+
+    for (var i = 0; i < 1e5; ++i)
+        shouldBe(indexOf(array, object), 100);
+}());
+
+(function () {
+    function indexOf(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOf);
+
+    var array = [];
+    var object = {};
+    for (var i = 0; i < 100; ++i) {
+        array.push(42);
+        array.push({});
+        array.push(String(i));
+    }
+    array.push(object);
+
+    for (var i = 0; i < 1e5; ++i)
+        shouldBe(indexOf(array, object), 100 * 3);
+}());
diff --git a/JSTests/stress/array-indexof-original-array.js b/JSTests/stress/array-indexof-original-array.js
new file mode 100644 (file)
index 0000000..3290927
--- /dev/null
@@ -0,0 +1,46 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOfInt32(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOfInt32);
+    var int32Array = [0, 1, 2, 3, 4, , 6, 7, 8, 9, 10, 11, 12];
+
+    var value = -1;
+    for (var i = 0; i < 1e5; ++i) {
+        shouldBe(indexOfInt32(int32Array, 5), value);
+        shouldBe(indexOfInt32(int32Array, 6), 6);
+        if (i === 1e4) {
+            int32Array.hello = 42;
+        }
+    }
+}());
+
+
+(function () {
+    function indexOfInt32(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOfInt32);
+    var int32Array = [0, 1, 2, 3, 4, , 6, 7, 8, 9, 10, 11, 12];
+
+    var value = -1;
+    for (var i = 0; i < 1e5; ++i) {
+        shouldBe(indexOfInt32(int32Array, 5), value);
+        shouldBe(indexOfInt32(int32Array, 6), 6);
+        if (i === 1e4) {
+            value = 5;
+            int32Array.__proto__ = {
+                __proto__: int32Array.__proto__,
+                5: 5
+            };
+        }
+    }
+}());
diff --git a/JSTests/stress/array-indexof-string.js b/JSTests/stress/array-indexof-string.js
new file mode 100644 (file)
index 0000000..f0f8804
--- /dev/null
@@ -0,0 +1,37 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOf(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOf);
+
+    var array = [];
+    for (var i = 0; i < 100; ++i)
+        array.push(String(i));
+
+    for (var i = 0; i < 1e5; ++i)
+        shouldBe(indexOf(array, "42"), 42);
+}());
+
+(function () {
+    function indexOf(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOf);
+
+    var array = [];
+    for (var i = 0; i < 100; ++i) {
+        array.push(String(i + 0.5));
+        array.push({});
+    }
+
+    for (var i = 0; i < 1e5; ++i)
+        shouldBe(indexOf(array, "42.5"), 42 * 2);
+}());
diff --git a/JSTests/stress/array-indexof-structure-change-convert.js b/JSTests/stress/array-indexof-structure-change-convert.js
new file mode 100644 (file)
index 0000000..d998a73
--- /dev/null
@@ -0,0 +1,32 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function indexOf(array, value)
+{
+    return array.indexOf(value);
+}
+noInline(indexOf);
+
+(function () {
+    var array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
+    var array2 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
+    var array3 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
+
+    array3[9] = 8;
+    array3[8] = 10.2;
+
+    for (var i = 0; i < 1e6; ++i)
+        shouldBe(indexOf(array, 8), 8);
+
+    array[9] = 8;
+    array[8] = 10.2;
+
+    for (var i = 0; i < 1e6; ++i)
+        shouldBe(indexOf(array, 8), 9);
+
+    for (var i = 0; i < 1e6; ++i)
+        shouldBe(indexOf(array2, 8), 8);
+}());
diff --git a/JSTests/stress/array-indexof-structure-change.js b/JSTests/stress/array-indexof-structure-change.js
new file mode 100644 (file)
index 0000000..7d03865
--- /dev/null
@@ -0,0 +1,20 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function indexOf(array, value)
+{
+    return array.indexOf(value);
+}
+noInline(indexOf);
+
+var array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
+for (var i = 0; i < 1e6; ++i) {
+    if (i === 1e6 - 1) {
+        array[8] = "Hello";
+        shouldBe(indexOf(array, 8), -1);
+    } else
+        shouldBe(indexOf(array, 8), 8);
+}
diff --git a/JSTests/stress/array-indexof.js b/JSTests/stress/array-indexof.js
new file mode 100644 (file)
index 0000000..d530bfe
--- /dev/null
@@ -0,0 +1,35 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+(function () {
+    function indexOf(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOf);
+
+    var array = [];
+    for (var i = 0; i < 100; ++i)
+        array.push(i);
+
+    for (var i = 0; i < 1e5; ++i)
+        shouldBe(indexOf(array, 42), 42);
+}());
+
+(function () {
+    function indexOf(array, value)
+    {
+        return array.indexOf(value);
+    }
+    noInline(indexOf);
+
+    var array = [];
+    for (var i = 0; i < 100; ++i)
+        array.push(i + 0.5);
+
+    for (var i = 0; i < 1e5; ++i)
+        shouldBe(indexOf(array, 42 + 0.5), 42);
+}());
index 342d253..e13e3a9 100644 (file)
@@ -1,3 +1,73 @@
+2017-06-09  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [DFG] Add ArrayIndexOf intrinsic
+        https://bugs.webkit.org/show_bug.cgi?id=172421
+
+        Reviewed by Saam Barati.
+
+        This patch introduces ArrayIndexOfInstrinsic for DFG and FTL optimizations.
+        We emit array check and go fast path if the array is Array::Int32, Array::Double
+        or Array::Continugous. In addition, for Array::Int32 and Array::Double case,
+        we have inlined fast paths.
+
+        With updated ARES-6 Babylon,
+
+        Before
+            firstIteration:     45.76 +- 3.87 ms
+            averageWorstCase:   24.41 +- 2.17 ms
+            steadyState:        8.01 +- 0.22 ms
+        After
+            firstIteration:     45.64 +- 4.23 ms
+            averageWorstCase:   23.03 +- 3.34 ms
+            steadyState:        7.33 +- 0.34 ms
+
+        In SixSpeed.
+                                         baseline                  patched
+
+            map-set-lookup.es5      734.4701+-10.4383    ^    102.0968+-2.6357        ^ definitely 7.1939x faster
+            map-set.es5              41.1396+-1.0558     ^     33.1916+-0.7986        ^ definitely 1.2395x faster
+            map-set-object.es5       62.8317+-1.2518     ^     45.6944+-0.8369        ^ definitely 1.3750x faster
+
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::handleIntrinsicCall):
+        * dfg/DFGClobberize.h:
+        (JSC::DFG::clobberize):
+        * dfg/DFGDoesGC.cpp:
+        (JSC::DFG::doesGC):
+        * dfg/DFGFixupPhase.cpp:
+        (JSC::DFG::FixupPhase::fixupNode):
+        * dfg/DFGNode.h:
+        (JSC::DFG::Node::hasArrayMode):
+        * dfg/DFGNodeType.h:
+        * dfg/DFGOperations.cpp:
+        * dfg/DFGOperations.h:
+        * dfg/DFGPredictionPropagationPhase.cpp:
+        * dfg/DFGSafeToExecute.h:
+        (JSC::DFG::safeToExecute):
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compileArrayIndexOf):
+        (JSC::DFG::SpeculativeJIT::speculateObject):
+        * dfg/DFGSpeculativeJIT.h:
+        (JSC::DFG::SpeculativeJIT::callOperation):
+        * dfg/DFGSpeculativeJIT32_64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * dfg/DFGSpeculativeJIT64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        (JSC::DFG::SpeculativeJIT::speculateInt32):
+        * ftl/FTLCapabilities.cpp:
+        (JSC::FTL::canCompile):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::compileNode):
+        (JSC::FTL::DFG::LowerDFGToB3::compileArrayIndexOf):
+        * jit/JITOperations.h:
+        * runtime/ArrayPrototype.cpp:
+        (JSC::ArrayPrototype::finishCreation):
+        * runtime/Intrinsic.cpp:
+        (JSC::intrinsicName):
+        * runtime/Intrinsic.h:
+
 2017-06-11  Keith Miller  <keith_miller@apple.com>
 
         TypedArray constructor with string shouldn't throw
index c8ddda5..c73a278 100644 (file)
@@ -1708,6 +1708,11 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
         forNode(node).set(m_graph, structureSet);
         break;
     }
+
+    case ArrayIndexOf: {
+        forNode(node).setType(SpecInt32Only);
+        break;
+    }
             
     case ArrayPop:
         clobberWorld(node->origin.semantic, clobberLimit);
index a1bfeb8..71e7516 100644 (file)
@@ -2323,6 +2323,7 @@ bool ByteCodeParser::handleIntrinsicCall(Node* callee, int resultOperand, Intrin
             InlineWatchpointSet& arrayPrototypeTransition = globalObject->arrayPrototype()->structure()->transitionWatchpointSet();
 
             // FIXME: We could easily relax the Array/Object.prototype transition as long as we OSR exitted if we saw a hole.
+            // https://bugs.webkit.org/show_bug.cgi?id=173171
             if (globalObject->arraySpeciesWatchpoint().state() == IsWatched
                 && globalObject->havingABadTimeWatchpoint()->isStillValid()
                 && arrayPrototypeTransition.isStillValid()
@@ -2379,6 +2380,72 @@ bool ByteCodeParser::handleIntrinsicCall(Node* callee, int resultOperand, Intrin
         RELEASE_ASSERT_NOT_REACHED();
         return false;
     }
+
+    case ArrayIndexOfIntrinsic: {
+        if (argumentCountIncludingThis < 2)
+            return false;
+
+        if (m_inlineStackTop->m_exitProfile.hasExitSite(m_currentIndex, BadIndexingType)
+            || m_inlineStackTop->m_exitProfile.hasExitSite(m_currentIndex, BadConstantCache)
+            || m_inlineStackTop->m_exitProfile.hasExitSite(m_currentIndex, BadCache)
+            || m_inlineStackTop->m_exitProfile.hasExitSite(m_currentIndex, BadType))
+            return false;
+
+        ArrayMode arrayMode = getArrayMode(m_currentInstruction[OPCODE_LENGTH(op_call) - 2].u.arrayProfile);
+        if (!arrayMode.isJSArray())
+            return false;
+
+        if (arrayMode.arrayClass() != Array::OriginalArray)
+            return false;
+
+        // We do not want to convert arrays into one type just to perform indexOf.
+        if (arrayMode.doesConversion())
+            return false;
+
+        switch (arrayMode.type()) {
+        case Array::Double:
+        case Array::Int32:
+        case Array::Contiguous: {
+            JSGlobalObject* globalObject = m_graph.globalObjectFor(currentNodeOrigin().semantic);
+
+            InlineWatchpointSet& objectPrototypeTransition = globalObject->objectPrototype()->structure()->transitionWatchpointSet();
+            InlineWatchpointSet& arrayPrototypeTransition = globalObject->arrayPrototype()->structure()->transitionWatchpointSet();
+
+            // FIXME: We could easily relax the Array/Object.prototype transition as long as we OSR exitted if we saw a hole.
+            // https://bugs.webkit.org/show_bug.cgi?id=173171
+            if (globalObject->havingABadTimeWatchpoint()->isStillValid()
+                && arrayPrototypeTransition.isStillValid()
+                && objectPrototypeTransition.isStillValid()
+                && globalObject->arrayPrototypeChainIsSane()) {
+
+                m_graph.watchpoints().addLazily(globalObject->havingABadTimeWatchpoint());
+                m_graph.watchpoints().addLazily(arrayPrototypeTransition);
+                m_graph.watchpoints().addLazily(objectPrototypeTransition);
+
+                insertChecks();
+
+                Node* array = get(virtualRegisterForArgument(0, registerOffset));
+                addVarArgChild(array);
+                addVarArgChild(get(virtualRegisterForArgument(1, registerOffset))); // Search element.
+                if (argumentCountIncludingThis >= 3)
+                    addVarArgChild(get(virtualRegisterForArgument(2, registerOffset))); // Start index.
+                addVarArgChild(nullptr);
+
+                Node* node = addToGraph(Node::VarArg, ArrayIndexOf, OpInfo(arrayMode.asWord()), OpInfo());
+                set(VirtualRegister(resultOperand), node);
+                return true;
+            }
+
+            return false;
+        }
+        default:
+            return false;
+        }
+
+        RELEASE_ASSERT_NOT_REACHED();
+        return false;
+
+    }
         
     case ArrayPopIntrinsic: {
         if (argumentCountIncludingThis != 1)
index bd6e713..fe7045e 100644 (file)
@@ -538,6 +538,31 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
         read(HeapObjectCount);
         write(HeapObjectCount);
         return;
+
+    case ArrayIndexOf: {
+        // FIXME: Should support a CSE rule.
+        // https://bugs.webkit.org/show_bug.cgi?id=173173
+        read(MiscFields);
+        read(JSCell_indexingType);
+        read(JSCell_structureID);
+        read(JSObject_butterfly);
+        read(Butterfly_publicLength);
+        switch (node->arrayMode().type()) {
+        case Array::Double:
+            read(IndexedDoubleProperties);
+            return;
+        case Array::Int32:
+            read(IndexedInt32Properties);
+            return;
+        case Array::Contiguous:
+            read(IndexedContiguousProperties);
+            return;
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+            return;
+        }
+        return;
+    }
         
     case GetById:
     case GetByIdFlush:
index 82eb571..5c30bd8 100644 (file)
@@ -320,6 +320,7 @@ bool doesGC(Graph& graph, Node* node)
     case CallDOMGetter:
     case CallDOM:
     case ArraySlice:
+    case ArrayIndexOf:
     case ParseInt: // We might resolve a rope even though we don't clobber anything.
         return true;
         
index 8edcfab..89e583d 100644 (file)
@@ -1022,6 +1022,45 @@ private:
                 fixEdge<Int32Use>(m_graph.varArgChild(node, 2));
             break;
         }
+
+        case ArrayIndexOf: {
+            Edge& array = m_graph.varArgChild(node, 0);
+            Edge& storage = m_graph.varArgChild(node, node->numChildren() == 3 ? 2 : 3);
+            blessArrayOperation(array, Edge(), storage);
+            ASSERT_WITH_MESSAGE(storage.node(), "blessArrayOperation for ArrayIndexOf must set Butterfly for storage edge.");
+
+            fixEdge<KnownCellUse>(array);
+            if (node->numChildren() == 4)
+                fixEdge<Int32Use>(m_graph.varArgChild(node, 2));
+
+            Edge& searchElement = m_graph.varArgChild(node, 1);
+            // FIXME: We have a chance to constant-fold this node to -1 by
+            // emitting non number edge filters.
+            // https://bugs.webkit.org/show_bug.cgi?id=173176
+            switch (node->arrayMode().type()) {
+            case Array::Double: {
+                if (searchElement->shouldSpeculateNumber())
+                    fixEdge<DoubleRepUse>(searchElement);
+                break;
+            }
+            case Array::Int32: {
+                if (searchElement->shouldSpeculateInt32())
+                    fixEdge<Int32Use>(searchElement);
+                break;
+            }
+            case Array::Contiguous: {
+                if (searchElement->shouldSpeculateString())
+                    fixEdge<StringUse>(searchElement);
+                else if (searchElement->shouldSpeculateObject())
+                    fixEdge<ObjectUse>(searchElement);
+                break;
+            }
+            default:
+                RELEASE_ASSERT_NOT_REACHED();
+                break;
+            }
+            break;
+        }
             
         case RegExpExec:
         case RegExpTest: {
index 0722652..77eff07 100644 (file)
@@ -1818,6 +1818,7 @@ public:
         case ArrayifyToStructure:
         case ArrayPush:
         case ArrayPop:
+        case ArrayIndexOf:
         case HasIndexedProperty:
         case AtomicsAdd:
         case AtomicsAnd:
index 6567ac7..cabc5cb 100644 (file)
@@ -262,6 +262,7 @@ namespace JSC { namespace DFG {
     macro(ArrayPush, NodeResultJS | NodeMustGenerate) \
     macro(ArrayPop, NodeResultJS | NodeMustGenerate) \
     macro(ArraySlice, NodeResultJS | NodeMustGenerate | NodeHasVarArgs) \
+    macro(ArrayIndexOf, NodeResultInt32 | NodeHasVarArgs) \
     \
     /* Optimizations for regular expression matching. */\
     macro(RegExpExec, NodeResultJS | NodeMustGenerate) \
index e2f5c14..ae1f5ff 100644 (file)
@@ -1905,6 +1905,70 @@ int32_t JIT_OPERATION operationHasOwnProperty(ExecState* exec, JSObject* thisObj
     return result;
 }
 
+int32_t JIT_OPERATION operationArrayIndexOfString(ExecState* exec, Butterfly* butterfly, JSString* searchElement, int32_t index)
+{
+    VM& vm = exec->vm();
+    NativeCallFrameTracer tracer(&vm, exec);
+    auto scope = DECLARE_THROW_SCOPE(vm);
+
+    int32_t length = butterfly->publicLength();
+    auto data = butterfly->contiguous().data();
+    for (; index < length; ++index) {
+        JSValue value = data[index].get();
+        if (!value || !value.isString())
+            continue;
+        auto* string = asString(value);
+        if (string == searchElement)
+            return index;
+        if (string->equal(exec, searchElement))
+            return index;
+        RETURN_IF_EXCEPTION(scope, { });
+    }
+    return -1;
+}
+
+int32_t JIT_OPERATION operationArrayIndexOfValueInt32OrContiguous(ExecState* exec, Butterfly* butterfly, EncodedJSValue encodedValue, int32_t index)
+{
+    VM& vm = exec->vm();
+    NativeCallFrameTracer tracer(&vm, exec);
+    auto scope = DECLARE_THROW_SCOPE(vm);
+
+    JSValue searchElement = JSValue::decode(encodedValue);
+
+    int32_t length = butterfly->publicLength();
+    auto data = butterfly->contiguous().data();
+    for (; index < length; ++index) {
+        JSValue value = data[index].get();
+        if (!value)
+            continue;
+        if (JSValue::strictEqual(exec, searchElement, value))
+            return index;
+        RETURN_IF_EXCEPTION(scope, { });
+    }
+    return -1;
+}
+
+int32_t JIT_OPERATION operationArrayIndexOfValueDouble(ExecState* exec, Butterfly* butterfly, EncodedJSValue encodedValue, int32_t index)
+{
+    VM& vm = exec->vm();
+    NativeCallFrameTracer tracer(&vm, exec);
+
+    JSValue searchElement = JSValue::decode(encodedValue);
+
+    if (!searchElement.isNumber())
+        return -1;
+    double number = searchElement.asNumber();
+
+    int32_t length = butterfly->publicLength();
+    const double* data = butterfly->contiguousDouble().data();
+    for (; index < length; ++index) {
+        // This comparison ignores NaN.
+        if (data[index] == number)
+            return index;
+    }
+    return -1;
+}
+
 void JIT_OPERATION operationLoadVarargs(ExecState* exec, int32_t firstElementDest, EncodedJSValue encodedArguments, int32_t offset, int32_t length, int32_t mandatoryMinimum)
 {
     VM& vm = exec->vm();
index f17ee8b..7c33cc1 100644 (file)
@@ -205,6 +205,11 @@ void JIT_OPERATION operationLoadVarargs(ExecState*, int32_t firstElementDest, En
 
 int32_t JIT_OPERATION operationHasOwnProperty(ExecState*, JSObject*, EncodedJSValue);
 
+int32_t JIT_OPERATION operationArrayIndexOfString(ExecState*, Butterfly*, JSString*, int32_t);
+int32_t JIT_OPERATION operationArrayIndexOfValue(ExecState*, Butterfly*, EncodedJSValue, int32_t);
+int32_t JIT_OPERATION operationArrayIndexOfValueDouble(ExecState*, Butterfly*, EncodedJSValue, int32_t);
+int32_t JIT_OPERATION operationArrayIndexOfValueInt32OrContiguous(ExecState*, Butterfly*, EncodedJSValue, int32_t);
+
 JSCell* JIT_OPERATION operationSpreadFastArray(ExecState*, JSCell*);
 JSCell* JIT_OPERATION operationSpreadGeneric(ExecState*, JSCell*);
 JSCell* JIT_OPERATION operationNewArrayWithSpreadSlow(ExecState*, void*, uint32_t);
index a919059..3d25eb0 100644 (file)
@@ -762,7 +762,8 @@ private:
             setPrediction(SpecBoolean);
             break;
 
-        case GetRestLength: {
+        case GetRestLength:
+        case ArrayIndexOf: {
             setPrediction(SpecInt32Only);
             break;
         }
index a3e2be6..f93a69e 100644 (file)
@@ -392,7 +392,8 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     case AtomicsIsLockFree:
         return true;
 
-    case ArraySlice: {
+    case ArraySlice:
+    case ArrayIndexOf: {
         // You could plausibly move this code around as long as you proved the
         // incoming array base structure is an original array at the hoisted location.
         // Instead of doing that extra work, we just conservatively return false.
index 2f1b581..f8dda7e 100644 (file)
@@ -7442,6 +7442,181 @@ void SpeculativeJIT::compileArraySlice(Node* node)
     cellResult(resultGPR, node);
 }
 
+void SpeculativeJIT::compileArrayIndexOf(Node* node)
+{
+    ASSERT(node->op() == ArrayIndexOf);
+
+    StorageOperand storage(this, m_jit.graph().varArgChild(node, node->numChildren() == 3 ? 2 : 3));
+    GPRTemporary index(this);
+    GPRTemporary tempLength(this);
+
+    GPRReg storageGPR = storage.gpr();
+    GPRReg indexGPR = index.gpr();
+    GPRReg lengthGPR = tempLength.gpr();
+
+    m_jit.load32(MacroAssembler::Address(storageGPR, Butterfly::offsetOfPublicLength()), lengthGPR);
+
+    if (node->numChildren() == 4) {
+        SpeculateInt32Operand startIndex(this, m_jit.graph().varArgChild(node, 2));
+        GPRReg startIndexGPR = startIndex.gpr();
+        MacroAssembler::JumpList done;
+        auto isPositive = m_jit.branch32(MacroAssembler::GreaterThanOrEqual, startIndexGPR, TrustedImm32(0));
+        m_jit.move(lengthGPR, indexGPR);
+        done.append(m_jit.branchAdd32(MacroAssembler::PositiveOrZero, startIndexGPR, indexGPR));
+        m_jit.move(TrustedImm32(0), indexGPR);
+        done.append(m_jit.jump());
+
+        isPositive.link(&m_jit);
+        m_jit.move(startIndexGPR, indexGPR);
+        done.append(m_jit.branch32(MacroAssembler::BelowOrEqual, indexGPR, lengthGPR));
+        m_jit.move(lengthGPR, indexGPR);
+
+        done.link(&m_jit);
+    } else
+        m_jit.move(TrustedImm32(0), indexGPR);
+
+    Edge& searchElementEdge = m_jit.graph().varArgChild(node, 1);
+    switch (searchElementEdge.useKind()) {
+    case Int32Use:
+    case ObjectUse: {
+        auto emitLoop = [&] (auto emitCompare) {
+            m_jit.zeroExtend32ToPtr(lengthGPR, lengthGPR);
+            m_jit.zeroExtend32ToPtr(indexGPR, indexGPR);
+
+            auto loop = m_jit.label();
+            auto notFound = m_jit.branch32(CCallHelpers::Equal, indexGPR, lengthGPR);
+
+            auto found = emitCompare();
+
+            m_jit.add32(TrustedImm32(1), indexGPR);
+            m_jit.jump().linkTo(loop, &m_jit);
+
+            notFound.link(&m_jit);
+            m_jit.move(TrustedImm32(-1), indexGPR);
+            found.link(&m_jit);
+            int32Result(indexGPR, node);
+        };
+
+#if USE(JSVALUE32_64)
+        GPRTemporary temp(this);
+        GPRReg tempGPR = temp.gpr();
+#endif
+
+        if (searchElementEdge.useKind() == Int32Use) {
+            ASSERT(node->arrayMode().type() == Array::Int32);
+#if USE(JSVALUE64)
+            JSValueOperand searchElement(this, searchElementEdge, ManualOperandSpeculation);
+            JSValueRegs searchElementRegs = searchElement.jsValueRegs();
+            speculateInt32(searchElementEdge, searchElementRegs);
+            GPRReg searchElementGPR = searchElementRegs.payloadGPR();
+#else
+            SpeculateInt32Operand searchElement(this, searchElementEdge);
+            GPRReg searchElementGPR = searchElement.gpr();
+#endif
+            emitLoop([&] () {
+#if USE(JSVALUE64)
+                auto found = m_jit.branch64(CCallHelpers::Equal, MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight), searchElementGPR);
+#else
+                auto skip = m_jit.branch32(CCallHelpers::NotEqual, MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight, TagOffset), TrustedImm32(JSValue::Int32Tag));
+                m_jit.load32(MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight, PayloadOffset), tempGPR);
+                auto found = m_jit.branch32(CCallHelpers::Equal, tempGPR, searchElementGPR);
+                skip.link(&m_jit);
+#endif
+                return found;
+            });
+        } else {
+            ASSERT(node->arrayMode().type() == Array::Contiguous);
+            SpeculateCellOperand searchElement(this, searchElementEdge);
+            GPRReg searchElementGPR = searchElement.gpr();
+            speculateObject(searchElementEdge, searchElementGPR);
+
+            emitLoop([&] () {
+#if USE(JSVALUE64)
+                auto found = m_jit.branch64(CCallHelpers::Equal, MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight), searchElementGPR);
+#else
+                auto skip = m_jit.branch32(CCallHelpers::NotEqual, MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight, TagOffset), TrustedImm32(JSValue::CellTag));
+                m_jit.load32(MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight, PayloadOffset), tempGPR);
+                auto found = m_jit.branch32(CCallHelpers::Equal, tempGPR, searchElementGPR);
+                skip.link(&m_jit);
+#endif
+                return found;
+            });
+        }
+        break;
+    }
+
+    case DoubleRepUse: {
+        ASSERT(node->arrayMode().type() == Array::Double);
+        SpeculateDoubleOperand searchElement(this, searchElementEdge);
+        FPRTemporary tempDouble(this);
+
+        FPRReg searchElementFPR = searchElement.fpr();
+        FPRReg tempFPR = tempDouble.fpr();
+
+        m_jit.zeroExtend32ToPtr(lengthGPR, lengthGPR);
+        m_jit.zeroExtend32ToPtr(indexGPR, indexGPR);
+
+        auto loop = m_jit.label();
+        auto notFound = m_jit.branch32(CCallHelpers::Equal, indexGPR, lengthGPR);
+        m_jit.loadDouble(MacroAssembler::BaseIndex(storageGPR, indexGPR, MacroAssembler::TimesEight), tempFPR);
+        auto found = m_jit.branchDouble(CCallHelpers::DoubleEqual, tempFPR, searchElementFPR);
+        m_jit.add32(TrustedImm32(1), indexGPR);
+        m_jit.jump().linkTo(loop, &m_jit);
+
+        notFound.link(&m_jit);
+        m_jit.move(TrustedImm32(-1), indexGPR);
+        found.link(&m_jit);
+        int32Result(indexGPR, node);
+        break;
+    }
+
+    case StringUse: {
+        ASSERT(node->arrayMode().type() == Array::Contiguous);
+        SpeculateCellOperand searchElement(this, searchElementEdge);
+
+        GPRReg searchElementGPR = searchElement.gpr();
+
+        speculateString(searchElementEdge, searchElementGPR);
+
+        flushRegisters();
+
+        callOperation(operationArrayIndexOfString, lengthGPR, storageGPR, searchElementGPR, indexGPR);
+        m_jit.exceptionCheck();
+
+        int32Result(lengthGPR, node);
+        break;
+    }
+
+    case UntypedUse: {
+        JSValueOperand searchElement(this, searchElementEdge);
+
+        JSValueRegs searchElementRegs = searchElement.jsValueRegs();
+
+        flushRegisters();
+        switch (node->arrayMode().type()) {
+        case Array::Double:
+            callOperation(operationArrayIndexOfValueDouble, lengthGPR, storageGPR, searchElementRegs, indexGPR);
+            break;
+        case Array::Int32:
+        case Array::Contiguous:
+            callOperation(operationArrayIndexOfValueInt32OrContiguous, lengthGPR, storageGPR, searchElementRegs, indexGPR);
+            break;
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+            break;
+        }
+        m_jit.exceptionCheck();
+
+        int32Result(lengthGPR, node);
+        break;
+    }
+
+    default:
+        RELEASE_ASSERT_NOT_REACHED();
+        break;
+    }
+}
+
 void SpeculativeJIT::compileNotifyWrite(Node* node)
 {
     WatchpointSet* set = node->watchpointSet();
@@ -8428,15 +8603,18 @@ void SpeculativeJIT::speculateCellOrOther(Edge edge)
     ok.link(&m_jit);
 }
 
+void SpeculativeJIT::speculateObject(Edge edge, GPRReg cell)
+{
+    DFG_TYPE_CHECK(JSValueSource::unboxedCell(cell), edge, SpecObject, m_jit.branchIfNotObject(cell));
+}
+
 void SpeculativeJIT::speculateObject(Edge edge)
 {
     if (!needsTypeCheck(edge, SpecObject))
         return;
     
     SpeculateCellOperand operand(this, edge);
-    GPRReg gpr = operand.gpr();
-    DFG_TYPE_CHECK(
-        JSValueSource::unboxedCell(gpr), edge, SpecObject, m_jit.branchIfNotObject(gpr));
+    speculateObject(edge, operand.gpr());
 }
 
 void SpeculativeJIT::speculateFunction(Edge edge)
index d3c8b84..1430610 100644 (file)
@@ -1006,6 +1006,11 @@ public:
         m_jit.setupArgumentsWithExecState(obj, impl);
         return appendCallSetResult(operation, result);
     }
+    JITCompiler::Call callOperation(Z_JITOperation_EBJssZ operation, GPRReg result, GPRReg butterfly, GPRReg string, GPRReg index)
+    {
+        m_jit.setupArgumentsWithExecState(butterfly, string, index);
+        return appendCallSetResult(operation, result);
+    }
     JITCompiler::Call callOperation(P_JITOperation_ESt operation, GPRReg result, RegisteredStructure structure)
     {
         m_jit.setupArgumentsWithExecState(TrustedImmPtr(structure));
@@ -1887,6 +1892,11 @@ public:
         m_jit.setupArgumentsWithExecState(arg1, TrustedImm32(arg2));
         return appendCallSetResult(operation, result);
     }
+    JITCompiler::Call callOperation(Z_JITOperation_EBJZ operation, GPRReg result, GPRReg arg1, JSValueRegs arg2, GPRReg arg3)
+    {
+        m_jit.setupArgumentsWithExecState(arg1, arg2.payloadGPR(), arg3);
+        return appendCallSetResult(operation, result);
+    }
     JITCompiler::Call callOperation(V_JITOperation_EZJZZZ operation, unsigned arg1, GPRReg arg2, unsigned arg3, GPRReg arg4, unsigned arg5)
     {
         m_jit.setupArgumentsWithExecState(TrustedImm32(arg1), arg2, TrustedImm32(arg3), arg4, TrustedImm32(arg5));
@@ -2420,6 +2430,11 @@ public:
         m_jit.setupArgumentsWithExecState(EABI_32BIT_DUMMY_ARG arg1.payloadGPR(), arg1.tagGPR(), TrustedImm32(arg2));
         return appendCallSetResult(operation, result);
     }
+    JITCompiler::Call callOperation(Z_JITOperation_EBJZ operation, GPRReg result, GPRReg arg1, JSValueRegs arg2, GPRReg arg3)
+    {
+        m_jit.setupArgumentsWithExecState(arg1, arg2.payloadGPR(), arg2.tagGPR(), arg3);
+        return appendCallSetResult(operation, result);
+    }
     JITCompiler::Call callOperation(V_JITOperation_EZJZZZ operation, unsigned arg1, JSValueRegs arg2, unsigned arg3, GPRReg arg4, unsigned arg5)
     {
         m_jit.setupArgumentsWithExecState(TrustedImm32(arg1), arg2.payloadGPR(), arg2.tagGPR(), TrustedImm32(arg3), arg4, TrustedImm32(arg5));
@@ -2829,6 +2844,7 @@ public:
     void compileNewArrayWithSpread(Node*);
     void compileGetRestLength(Node*);
     void compileArraySlice(Node*);
+    void compileArrayIndexOf(Node*);
     void compileNotifyWrite(Node*);
     bool compileRegExpExec(Node*);
     void compileIsObjectOrNull(Node*);
@@ -2949,6 +2965,7 @@ public:
 #if USE(JSVALUE64)
     void convertAnyInt(Edge, GPRReg resultGPR);
     void speculateAnyInt(Edge);
+    void speculateInt32(Edge, JSValueRegs);
     void speculateDoubleRepAnyInt(Edge);
 #endif // USE(JSVALUE64)
     void speculateNumber(Edge);
@@ -2957,6 +2974,7 @@ public:
     void speculateBoolean(Edge);
     void speculateCell(Edge);
     void speculateCellOrOther(Edge);
+    void speculateObject(Edge, GPRReg cell);
     void speculateObject(Edge);
     void speculateArray(Edge, GPRReg cell);
     void speculateArray(Edge);
index 7d36938..fa6bfa6 100644 (file)
@@ -3583,6 +3583,11 @@ void SpeculativeJIT::compile(Node* node)
         break;
     }
 
+    case ArrayIndexOf: {
+        compileArrayIndexOf(node);
+        break;
+    }
+
     case DFG::Jump: {
         jump(node->targetBlock());
         noResult(node);
index 9babd8a..205b3fc 100644 (file)
@@ -3721,6 +3721,11 @@ void SpeculativeJIT::compile(Node* node)
         compileArraySlice(node);
         break;
     }
+
+    case ArrayIndexOf: {
+        compileArrayIndexOf(node);
+        break;
+    }
         
     case ArrayPop: {
         ASSERT(node->arrayMode().isJSArray());
@@ -6168,6 +6173,11 @@ void SpeculativeJIT::speculateAnyInt(Edge edge)
     convertAnyInt(edge, temp.gpr());
 }
 
+void SpeculativeJIT::speculateInt32(Edge edge, JSValueRegs regs)
+{
+    DFG_TYPE_CHECK(regs, edge, SpecInt32Only, m_jit.branchIfNotInt32(regs));
+}
+
 void SpeculativeJIT::speculateDoubleRepAnyInt(Edge edge)
 {
     if (!needsTypeCheck(edge, SpecAnyIntAsDouble))
index 7f56eff..e659244 100644 (file)
@@ -282,6 +282,7 @@ inline CapabilityLevel canCompile(Node* node)
     case CallDOM:
     case CallDOMGetter:
     case ArraySlice:
+    case ArrayIndexOf:
     case ParseInt:
     case AtomicsAdd:
     case AtomicsAnd:
index 85a03e8..b477efc 100644 (file)
@@ -726,6 +726,9 @@ private:
         case ArraySlice:
             compileArraySlice();
             break;
+        case ArrayIndexOf:
+            compileArrayIndexOf();
+            break;
         case CreateActivation:
             compileCreateActivation();
             break;
@@ -4050,6 +4053,111 @@ private:
         mutatorFence();
         setJSValue(arrayResult.array);
     }
+
+    void compileArrayIndexOf()
+    {
+        LValue storage = lowStorage(m_node->numChildren() == 3 ? m_graph.varArgChild(m_node, 2) : m_graph.varArgChild(m_node, 3));
+        LValue length = m_out.load32(storage, m_heaps.Butterfly_publicLength);
+
+        LValue startIndex;
+        if (m_node->numChildren() == 4) {
+            startIndex = lowInt32(m_graph.varArgChild(m_node, 2));
+            startIndex = m_out.select(m_out.greaterThanOrEqual(startIndex, m_out.int32Zero),
+                m_out.select(m_out.above(startIndex, length), length, startIndex),
+                m_out.select(m_out.lessThan(m_out.add(length, startIndex), m_out.int32Zero), m_out.int32Zero, m_out.add(length, startIndex)));
+        } else
+            startIndex = m_out.int32Zero;
+
+        Edge& searchElementEdge = m_graph.varArgChild(m_node, 1);
+        switch (searchElementEdge.useKind()) {
+        case Int32Use:
+        case ObjectUse:
+        case DoubleRepUse: {
+            LBasicBlock loopHeader = m_out.newBlock();
+            LBasicBlock loopBody = m_out.newBlock();
+            LBasicBlock loopNext = m_out.newBlock();
+            LBasicBlock notFound = m_out.newBlock();
+            LBasicBlock continuation = m_out.newBlock();
+
+            LValue searchElement;
+            if (searchElementEdge.useKind() == Int32Use) {
+                ASSERT(m_node->arrayMode().type() == Array::Int32);
+                speculate(searchElementEdge);
+                searchElement = lowJSValue(searchElementEdge, ManualOperandSpeculation);
+            } else if (searchElementEdge.useKind() == ObjectUse) {
+                ASSERT(m_node->arrayMode().type() == Array::Contiguous);
+                searchElement = lowObject(searchElementEdge);
+            } else {
+                ASSERT(m_node->arrayMode().type() == Array::Double);
+                searchElement = lowDouble(searchElementEdge);
+            }
+
+            startIndex = m_out.zeroExtPtr(startIndex);
+            length = m_out.zeroExtPtr(length);
+
+            ValueFromBlock initialStartIndex = m_out.anchor(startIndex);
+            m_out.jump(loopHeader);
+
+            LBasicBlock lastNext = m_out.appendTo(loopHeader, loopBody);
+            LValue index = m_out.phi(pointerType(), initialStartIndex);
+            m_out.branch(m_out.notEqual(index, length), unsure(loopBody), unsure(notFound));
+
+            m_out.appendTo(loopBody, loopNext);
+            ValueFromBlock foundResult = m_out.anchor(index);
+            if (searchElementEdge.useKind() == Int32Use) {
+                // Empty value is ignored because of TagTypeNumber.
+                LValue value = m_out.load64(m_out.baseIndex(m_heaps.indexedInt32Properties, storage, index));
+                m_out.branch(m_out.equal(value, searchElement), unsure(continuation), unsure(loopNext));
+            } else if (searchElementEdge.useKind() == ObjectUse) {
+                // Empty value never matches against object pointers.
+                LValue value = m_out.load64(m_out.baseIndex(m_heaps.indexedContiguousProperties, storage, index));
+                m_out.branch(m_out.equal(value, searchElement), unsure(continuation), unsure(loopNext));
+            } else {
+                // Empty value is ignored because of NaN.
+                LValue value = m_out.loadDouble(m_out.baseIndex(m_heaps.indexedDoubleProperties, storage, index));
+                m_out.branch(m_out.doubleEqual(value, searchElement), unsure(continuation), unsure(loopNext));
+            }
+
+            m_out.appendTo(loopNext, notFound);
+            LValue nextIndex = m_out.add(index, m_out.intPtrOne);
+            m_out.addIncomingToPhi(index, m_out.anchor(nextIndex));
+            m_out.jump(loopHeader);
+
+            m_out.appendTo(notFound, continuation);
+            ValueFromBlock notFoundResult = m_out.anchor(m_out.constIntPtr(-1));
+            m_out.jump(continuation);
+
+            m_out.appendTo(continuation, lastNext);
+            setInt32(m_out.castToInt32(m_out.phi(pointerType(), notFoundResult, foundResult)));
+            break;
+        }
+
+        case StringUse:
+            ASSERT(m_node->arrayMode().type() == Array::Contiguous);
+            setInt32(vmCall(Int32, m_out.operation(operationArrayIndexOfString), m_callFrame, storage, lowString(searchElementEdge), startIndex));
+            break;
+
+        case UntypedUse:
+            switch (m_node->arrayMode().type()) {
+            case Array::Double:
+                setInt32(vmCall(Int32, m_out.operation(operationArrayIndexOfValueDouble), m_callFrame, storage, lowJSValue(searchElementEdge), startIndex));
+                break;
+            case Array::Int32:
+            case Array::Contiguous:
+                setInt32(vmCall(Int32, m_out.operation(operationArrayIndexOfValueInt32OrContiguous), m_callFrame, storage, lowJSValue(searchElementEdge), startIndex));
+                break;
+            default:
+                RELEASE_ASSERT_NOT_REACHED();
+                break;
+            }
+            break;
+
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+            break;
+        }
+    }
+
     
     void compileArrayPop()
     {
index db17d26..4f10c27 100644 (file)
@@ -233,6 +233,8 @@ typedef int32_t (JIT_OPERATION *Z_JITOperation_EJZ)(ExecState*, EncodedJSValue,
 typedef int32_t (JIT_OPERATION *Z_JITOperation_EJZZ)(ExecState*, EncodedJSValue, int32_t, int32_t);
 typedef int32_t (JIT_OPERATION *Z_JITOperation_EOI)(ExecState*, JSObject*, UniquedStringImpl*);
 typedef int32_t (JIT_OPERATION *Z_JITOperation_EOJ)(ExecState*, JSObject*, EncodedJSValue);
+typedef int32_t (JIT_OPERATION *Z_JITOperation_EBJssZ)(ExecState*, Butterfly*, JSString*, int32_t);
+typedef int32_t (JIT_OPERATION *Z_JITOperation_EBJZ)(ExecState*, Butterfly*, EncodedJSValue, int32_t);
 typedef size_t (JIT_OPERATION *S_JITOperation_EO)(ExecState*, JSObject*);
 typedef size_t (JIT_OPERATION *S_JITOperation_ECC)(ExecState*, JSCell*, JSCell*);
 typedef size_t (JIT_OPERATION *S_JITOperation_EGC)(ExecState*, JSGlobalObject*, JSCell*);
index e9e1b3a..8f16943 100644 (file)
@@ -105,7 +105,7 @@ void ArrayPrototype::finishCreation(VM& vm, JSGlobalObject* globalObject)
     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("every", arrayPrototypeEveryCodeGenerator, DontEnum);
     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("forEach", arrayPrototypeForEachCodeGenerator, DontEnum);
     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("some", arrayPrototypeSomeCodeGenerator, DontEnum);
-    JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("indexOf", arrayProtoFuncIndexOf, DontEnum, 1);
+    JSC_NATIVE_INTRINSIC_FUNCTION_WITHOUT_TRANSITION("indexOf", arrayProtoFuncIndexOf, DontEnum, 1, ArrayIndexOfIntrinsic);
     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("lastIndexOf", arrayProtoFuncLastIndexOf, DontEnum, 1);
     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("filter", arrayPrototypeFilterCodeGenerator, DontEnum);
     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("reduce", arrayPrototypeReduceCodeGenerator, DontEnum);
index 97e02cc..4d46090 100644 (file)
@@ -71,6 +71,8 @@ const char* intrinsicName(Intrinsic intrinsic)
         return "SinhIntrinsic";
     case TanhIntrinsic:
         return "TanhIntrinsic";
+    case ArrayIndexOfIntrinsic:
+        return "ArrayIndexOfIntrinsic";
     case ArrayPushIntrinsic:
         return "ArrayPushIntrinsic";
     case ArrayPopIntrinsic:
index 639590b..d70cd48 100644 (file)
@@ -51,6 +51,7 @@ enum Intrinsic {
     ArrayPushIntrinsic,
     ArrayPopIntrinsic,
     ArraySliceIntrinsic,
+    ArrayIndexOfIntrinsic,
     CharCodeAtIntrinsic,
     CharAtIntrinsic,
     FromCharCodeIntrinsic,