Fix InBounds speculation of typed array PutByVal and add extra step to integer range...
authorjustin_michaud@apple.com <justin_michaud@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 16 Aug 2019 21:33:28 +0000 (21:33 +0000)
committerjustin_michaud@apple.com <justin_michaud@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 16 Aug 2019 21:33:28 +0000 (21:33 +0000)
https://bugs.webkit.org/show_bug.cgi?id=200782

Reviewed by Saam Barati.

JSTests:

* microbenchmarks/int8-out-of-bounds.js: Added.
(foo):
* microbenchmarks/memcpy-typed-loop.js: Added.
(doTest):
(let.arr1.new.Int32Array.1000.let.arr2.new.Int32Array.1000):
(arr2):
* stress/int8-repeat-in-then-out-of-bounds.js: Added.
(foo):

Source/JavaScriptCore:

Speculate that putByVals on typed arrays are in bounds initially, and add an extra rule to integer range optimization to
remove CheckInBounds when we are looping over two arrays. We do this by fixing a bug in the llint slow paths that marked
typed array accesses as out of bounds, and we also add an extra step to integer range optimization to search for equality
relationships on the RHS value.

Microbenchmarks give a 40% improvement on the memcpy loop test, and neutral on the out-of-bounds typed array test.

* dfg/DFGIntegerRangeOptimizationPhase.cpp:
* dfg/DFGOperations.cpp:
(JSC::DFG::putByVal):
* jit/JITOperations.cpp:
* llint/LLIntSlowPaths.cpp:
(JSC::LLInt::LLINT_SLOW_PATH_DECL):
* runtime/JSGenericTypedArrayView.h:
* runtime/JSObject.h:
(JSC::JSObject::putByIndexInline):
(JSC::JSObject::canGetIndexQuickly const):
(JSC::JSObject::getIndexQuickly const):
(JSC::JSObject::tryGetIndexQuickly const):
(JSC::JSObject::canSetIndexQuickly):
(JSC::JSObject::setIndexQuickly):
* runtime/JSObjectInlines.h:
(JSC::JSObject::canGetIndexQuicklyForTypedArray const):
(JSC::JSObject::canSetIndexQuicklyForTypedArray const):
(JSC::JSObject::getIndexQuicklyForTypedArray const):
(JSC::JSObject::setIndexQuicklyForTypedArray):

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

12 files changed:
JSTests/ChangeLog
JSTests/microbenchmarks/int8-out-of-bounds.js [new file with mode: 0644]
JSTests/microbenchmarks/memcpy-typed-loop.js [new file with mode: 0644]
JSTests/stress/int8-repeat-in-then-out-of-bounds.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/jit/JITOperations.cpp
Source/JavaScriptCore/llint/LLIntSlowPaths.cpp
Source/JavaScriptCore/runtime/JSGenericTypedArrayView.h
Source/JavaScriptCore/runtime/JSObject.h
Source/JavaScriptCore/runtime/JSObjectInlines.h

index bd87c05..7c9ce49 100644 (file)
@@ -1,3 +1,19 @@
+2019-08-16  Justin Michaud  <justin_michaud@apple.com>
+
+        Fix InBounds speculation of typed array PutByVal and add extra step to integer range optimization to search for equality relationships on the RHS value
+        https://bugs.webkit.org/show_bug.cgi?id=200782
+
+        Reviewed by Saam Barati.
+
+        * microbenchmarks/int8-out-of-bounds.js: Added.
+        (foo):
+        * microbenchmarks/memcpy-typed-loop.js: Added.
+        (doTest):
+        (let.arr1.new.Int32Array.1000.let.arr2.new.Int32Array.1000):
+        (arr2):
+        * stress/int8-repeat-in-then-out-of-bounds.js: Added.
+        (foo):
+
 2019-08-16  Mark Lam  <mark.lam@apple.com>
 
         [Re-land] ProxyObject should not be allow to access its target's private properties.
diff --git a/JSTests/microbenchmarks/int8-out-of-bounds.js b/JSTests/microbenchmarks/int8-out-of-bounds.js
new file mode 100644 (file)
index 0000000..e5f9bd1
--- /dev/null
@@ -0,0 +1,17 @@
+function foo(a, inBounds) {
+    a[0] = 1;
+    if (!inBounds) {
+        a[1] = 2;
+        a[2] = 3;
+    }
+}
+
+noInline(foo);
+
+var array = new Int8Array(1);
+
+for (var i = 0; i < 100000; ++i)
+    foo(array, true);
+
+for (var i = 0; i < 100000; ++i)
+    foo(array, false);
diff --git a/JSTests/microbenchmarks/memcpy-typed-loop.js b/JSTests/microbenchmarks/memcpy-typed-loop.js
new file mode 100644 (file)
index 0000000..c031041
--- /dev/null
@@ -0,0 +1,25 @@
+function doTest(arr1, arr2) {
+    if (arr1.length != arr2.length)
+        return []
+    for (let i=0; i<arr1.length; ++i) {
+        arr2[i] = arr1[i]
+    }
+    return arr2
+}
+noInline(doTest);
+
+let arr1 = new Int32Array(1000)
+let arr2 = new Int32Array(1000)
+for (let i=0; i<arr1.length; ++i) {
+    arr1[i] = i
+}
+
+for (let i=0; i<10000000; ++i) doTest(arr1, arr2)
+
+arr2 = new Int32Array(arr1.length)
+doTest(arr1, arr2)
+
+for (let i=0; i<arr1.length; ++i) {
+    if (arr2[i] != arr1[i])
+        throw "Error: bad copy"
+}
diff --git a/JSTests/stress/int8-repeat-in-then-out-of-bounds.js b/JSTests/stress/int8-repeat-in-then-out-of-bounds.js
new file mode 100644 (file)
index 0000000..7366df2
--- /dev/null
@@ -0,0 +1,25 @@
+//@ defaultNoEagerRun
+
+function foo(a, inBounds) {
+    a[0] = 1;
+    if (!inBounds) {
+        a[1] = 2;
+        a[2] = 3;
+    }
+}
+
+noInline(foo);
+
+var array = new Int8Array(1);
+
+for (var i = 0; i < 100000; ++i)
+    foo(array, true);
+
+if (reoptimizationRetryCount(foo))
+    throw "Error: unexpected retry count: " + reoptimizationRetryCount(foo);
+
+for (var i = 0; i < 100000; ++i)
+    foo(array, false);
+
+if (reoptimizationRetryCount(foo) != 1)
+    throw "Error: unexpected retry count: " + reoptimizationRetryCount(foo);
index c114c68..b2f42aa 100644 (file)
@@ -1,3 +1,37 @@
+2019-08-16  Justin Michaud  <justin_michaud@apple.com>
+
+        Fix InBounds speculation of typed array PutByVal and add extra step to integer range optimization to search for equality relationships on the RHS value
+        https://bugs.webkit.org/show_bug.cgi?id=200782
+
+        Reviewed by Saam Barati.
+
+        Speculate that putByVals on typed arrays are in bounds initially, and add an extra rule to integer range optimization to 
+        remove CheckInBounds when we are looping over two arrays. We do this by fixing a bug in the llint slow paths that marked 
+        typed array accesses as out of bounds, and we also add an extra step to integer range optimization to search for equality
+        relationships on the RHS value.
+
+        Microbenchmarks give a 40% improvement on the memcpy loop test, and neutral on the out-of-bounds typed array test.
+
+        * dfg/DFGIntegerRangeOptimizationPhase.cpp:
+        * dfg/DFGOperations.cpp:
+        (JSC::DFG::putByVal):
+        * jit/JITOperations.cpp:
+        * llint/LLIntSlowPaths.cpp:
+        (JSC::LLInt::LLINT_SLOW_PATH_DECL):
+        * runtime/JSGenericTypedArrayView.h:
+        * runtime/JSObject.h:
+        (JSC::JSObject::putByIndexInline):
+        (JSC::JSObject::canGetIndexQuickly const):
+        (JSC::JSObject::getIndexQuickly const):
+        (JSC::JSObject::tryGetIndexQuickly const):
+        (JSC::JSObject::canSetIndexQuickly):
+        (JSC::JSObject::setIndexQuickly):
+        * runtime/JSObjectInlines.h:
+        (JSC::JSObject::canGetIndexQuicklyForTypedArray const):
+        (JSC::JSObject::canSetIndexQuicklyForTypedArray const):
+        (JSC::JSObject::getIndexQuicklyForTypedArray const):
+        (JSC::JSObject::setIndexQuicklyForTypedArray):
+
 2019-08-16  Mark Lam  <mark.lam@apple.com>
 
         [Re-land] ProxyObject should not be allow to access its target's private properties.
index 47d575c..81181eb 100644 (file)
@@ -275,6 +275,11 @@ public:
         RELEASE_ASSERT(left != m_right);
         m_left = left;
     }
+    void setRight(NodeFlowProjection right)
+    {
+        RELEASE_ASSERT(right != m_left);
+        m_right = right;
+    }
     bool addToOffset(int offset)
     {
         if (sumOverflows<int>(m_offset, offset))
@@ -1326,6 +1331,9 @@ public:
                                 lessThanLength = true;
                         }
                     }
+
+                    if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
+                        dataLogLn("CheckInBounds ", node, " has: ", nonNegative, " ", lessThanLength);
                     
                     if (nonNegative && lessThanLength) {
                         executeNode(block->at(nodeIndex));
@@ -1643,7 +1651,7 @@ private:
             
             if (timeToLive && otherRelationship.kind() == Relationship::Equal) {
                 if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
-                    dataLog("      Considering: ", otherRelationship, "\n");
+                    dataLog("      Considering (lhs): ", otherRelationship, "\n");
                 
                 // We have:
                 //     @a op @b + C
@@ -1666,6 +1674,31 @@ private:
                 }
             }
         }
+
+        if (timeToLive && relationship.kind() != Relationship::Equal) {
+            for (Relationship& possibleEquality : relationshipMap.get(relationship.right())) {
+                if (possibleEquality.kind() != Relationship::Equal
+                    || possibleEquality.offset() == std::numeric_limits<int>::min()
+                    || possibleEquality.right() == relationship.left())
+                    continue;
+                if (DFGIntegerRangeOptimizationPhaseInternal::verbose)
+                    dataLog("      Considering (rhs): ", possibleEquality, "\n");
+
+                // We have:
+                //     @a op @b + C
+                //     @b == @c + D
+                //
+                // This implies:
+                //     @a op @c + (C + D)
+                //
+                // Where: @a == relationship.left(), @b == relationship.right()
+
+                Relationship newRelationship = relationship;
+                newRelationship.setRight(possibleEquality.right());
+                if (newRelationship.addToOffset(possibleEquality.offset()))
+                    toAdd.append(newRelationship);
+            }
+        }
         
         if (!found)
             relationships.append(relationship);
index def0b70..22c73c7 100644 (file)
@@ -96,7 +96,7 @@ static inline void putByVal(ExecState* exec, VM& vm, JSValue baseValue, uint32_t
     }
     if (baseValue.isObject()) {
         JSObject* object = asObject(baseValue);
-        if (object->canSetIndexQuickly(index)) {
+        if (object->canSetIndexQuickly(index, value)) {
             object->setIndexQuickly(vm, index, value);
             return;
         }
index e9eed61..a484e5c 100644 (file)
@@ -636,14 +636,11 @@ static void putByVal(CallFrame* callFrame, JSValue baseValue, JSValue subscript,
         uint32_t i = subscript.asUInt32();
         if (baseValue.isObject()) {
             JSObject* object = asObject(baseValue);
-            if (object->canSetIndexQuickly(i)) {
+            if (object->canSetIndexQuickly(i, value)) {
                 object->setIndexQuickly(vm, i, value);
                 return;
             }
 
-            // FIXME: This will make us think that in-bounds typed array accesses are actually
-            // out-of-bounds.
-            // https://bugs.webkit.org/show_bug.cgi?id=149886
             byValInfo->arrayProfile->setOutOfBounds();
             scope.release();
             object->methodTable(vm)->putByIndex(object, callFrame, i, value, callFrame->codeBlock()->isStrictMode());
@@ -2052,12 +2049,8 @@ EncodedJSValue JIT_OPERATION operationHasIndexedPropertyDefault(ExecState* exec,
     if (object->canGetIndexQuickly(index))
         return JSValue::encode(JSValue(JSValue::JSTrue));
 
-    if (!CommonSlowPaths::canAccessArgumentIndexQuickly(*object, index)) {
-        // FIXME: This will make us think that in-bounds typed array accesses are actually
-        // out-of-bounds.
-        // https://bugs.webkit.org/show_bug.cgi?id=149886
+    if (!CommonSlowPaths::canAccessArgumentIndexQuickly(*object, index))
         byValInfo->arrayProfile->setOutOfBounds();
-    }
     return JSValue::encode(jsBoolean(object->hasPropertyGeneric(exec, index, PropertySlot::InternalMethodType::GetOwnProperty)));
 }
     
@@ -2076,12 +2069,8 @@ EncodedJSValue JIT_OPERATION operationHasIndexedPropertyGeneric(ExecState* exec,
     if (object->canGetIndexQuickly(index))
         return JSValue::encode(JSValue(JSValue::JSTrue));
 
-    if (!CommonSlowPaths::canAccessArgumentIndexQuickly(*object, index)) {
-        // FIXME: This will make us think that in-bounds typed array accesses are actually
-        // out-of-bounds.
-        // https://bugs.webkit.org/show_bug.cgi?id=149886
+    if (!CommonSlowPaths::canAccessArgumentIndexQuickly(*object, index))
         byValInfo->arrayProfile->setOutOfBounds();
-    }
     return JSValue::encode(jsBoolean(object->hasPropertyGeneric(exec, index, PropertySlot::InternalMethodType::GetOwnProperty)));
 }
     
index d621ce4..1e18e3b 100644 (file)
@@ -1000,7 +1000,7 @@ LLINT_SLOW_PATH_DECL(slow_path_put_by_val)
         uint32_t i = subscript.asUInt32();
         if (baseValue.isObject()) {
             JSObject* object = asObject(baseValue);
-            if (object->canSetIndexQuickly(i))
+            if (object->canSetIndexQuickly(i, value))
                 object->setIndexQuickly(vm, i, value);
             else
                 object->methodTable(vm)->putByIndex(object, exec, i, value, isStrictMode);
index d256313..1b9f55c 100644 (file)
@@ -125,16 +125,16 @@ public:
 
     // These methods are meant to match indexed access methods that JSObject
     // supports - hence the slight redundancy.
-    bool canGetIndexQuickly(unsigned i)
+    bool canGetIndexQuickly(unsigned i) const
     {
         return i < m_length;
     }
-    bool canSetIndexQuickly(unsigned i)
+    bool canSetIndexQuickly(unsigned i, JSValue value) const
     {
-        return i < m_length;
+        return i < m_length && value.isNumber();
     }
     
-    typename Adaptor::Type getIndexQuicklyAsNativeValue(unsigned i)
+    typename Adaptor::Type getIndexQuicklyAsNativeValue(unsigned i) const
     {
         ASSERT(i < m_length);
         return typedVector()[i];
@@ -145,7 +145,7 @@ public:
         return Adaptor::toDouble(getIndexQuicklyAsNativeValue(i));
     }
     
-    JSValue getIndexQuickly(unsigned i)
+    JSValue getIndexQuickly(unsigned i) const
     {
         return Adaptor::toJSValue(getIndexQuicklyAsNativeValue(i));
     }
index b071f77..214c77b 100644 (file)
@@ -198,7 +198,7 @@ public:
     // This performs the ECMAScript Set() operation.
     ALWAYS_INLINE bool putByIndexInline(ExecState* exec, unsigned propertyName, JSValue value, bool shouldThrow)
     {
-        if (canSetIndexQuickly(propertyName)) {
+        if (canSetIndexQuickly(propertyName, value)) {
             setIndexQuickly(exec->vm(), propertyName, value);
             return true;
         }
@@ -256,12 +256,16 @@ public:
     {
         return structure(vm)->hasIndexingHeader(this);
     }
+
+    bool canGetIndexQuicklyForTypedArray(unsigned) const;
+    JSValue getIndexQuicklyForTypedArray(unsigned) const;
     
     bool canGetIndexQuickly(unsigned i) const
     {
         const Butterfly* butterfly = this->butterfly();
         switch (indexingType()) {
         case ALL_BLANK_INDEXING_TYPES:
+            return canGetIndexQuicklyForTypedArray(i);
         case ALL_UNDECIDED_INDEXING_TYPES:
             return false;
         case ALL_INT32_INDEXING_TYPES:
@@ -295,6 +299,8 @@ public:
             return JSValue(JSValue::EncodeAsDouble, butterfly->contiguousDouble().at(this, i));
         case ALL_ARRAY_STORAGE_INDEXING_TYPES:
             return butterfly->arrayStorage()->m_vector[i].get();
+        case ALL_BLANK_INDEXING_TYPES:
+            return getIndexQuicklyForTypedArray(i);
         default:
             RELEASE_ASSERT_NOT_REACHED();
             return JSValue();
@@ -306,6 +312,9 @@ public:
         const Butterfly* butterfly = this->butterfly();
         switch (indexingType()) {
         case ALL_BLANK_INDEXING_TYPES:
+            if (canGetIndexQuicklyForTypedArray(i))
+                return getIndexQuicklyForTypedArray(i);
+            break;
         case ALL_UNDECIDED_INDEXING_TYPES:
             break;
         case ALL_INT32_INDEXING_TYPES:
@@ -354,12 +363,16 @@ public:
             return result;
         return get(exec, i);
     }
+
+    bool canSetIndexQuicklyForTypedArray(unsigned, JSValue) const;
+    void setIndexQuicklyForTypedArray(unsigned, JSValue);
         
-    bool canSetIndexQuickly(unsigned i)
+    bool canSetIndexQuickly(unsigned i, JSValue value)
     {
         Butterfly* butterfly = this->butterfly();
         switch (indexingMode()) {
         case ALL_BLANK_INDEXING_TYPES:
+            return canSetIndexQuicklyForTypedArray(i, value);
         case ALL_UNDECIDED_INDEXING_TYPES:
             return false;
         case ALL_WRITABLE_INT32_INDEXING_TYPES:
@@ -428,6 +441,9 @@ public:
             }
             break;
         }
+        case ALL_BLANK_INDEXING_TYPES:
+            setIndexQuicklyForTypedArray(i, v);
+            break;
         default:
             RELEASE_ASSERT_NOT_REACHED();
         }
index 08430f1..28183d4 100644 (file)
 #include "AuxiliaryBarrierInlines.h"
 #include "Error.h"
 #include "JSObject.h"
+#include "JSTypedArrays.h"
 #include "Lookup.h"
 #include "StructureInlines.h"
+#include "TypedArrayType.h"
 
 namespace JSC {
 
@@ -399,4 +401,66 @@ inline void JSObject::didBecomePrototype()
     setPerCellBit(true);
 }
 
+inline bool JSObject::canGetIndexQuicklyForTypedArray(unsigned i) const
+{
+    switch (type()) {
+#define CASE_TYPED_ARRAY_TYPE(name) \
+    case name ## ArrayType :\
+        return jsCast<const JS ## name ## Array *>(this)->canGetIndexQuickly(i);
+        FOR_EACH_TYPED_ARRAY_TYPE_EXCLUDING_DATA_VIEW(CASE_TYPED_ARRAY_TYPE)
+#undef CASE_TYPED_ARRAY_TYPE
+    default:
+        return false;
+    }
+}
+
+inline bool JSObject::canSetIndexQuicklyForTypedArray(unsigned i, JSValue value) const
+{
+    switch (type()) {
+#define CASE_TYPED_ARRAY_TYPE(name) \
+    case name ## ArrayType :\
+        return jsCast<const JS ## name ## Array *>(this)->canSetIndexQuickly(i, value);
+        FOR_EACH_TYPED_ARRAY_TYPE_EXCLUDING_DATA_VIEW(CASE_TYPED_ARRAY_TYPE)
+#undef CASE_TYPED_ARRAY_TYPE
+    default:
+        return false;
+    }
+}
+
+inline JSValue JSObject::getIndexQuicklyForTypedArray(unsigned i) const
+{
+    switch (type()) {
+#define CASE_TYPED_ARRAY_TYPE(name) \
+    case name ## ArrayType : {\
+        auto* typedArray = jsCast<const JS ## name ## Array *>(this);\
+        RELEASE_ASSERT(typedArray->canGetIndexQuickly(i));\
+        return typedArray->getIndexQuickly(i);\
+    }
+        FOR_EACH_TYPED_ARRAY_TYPE_EXCLUDING_DATA_VIEW(CASE_TYPED_ARRAY_TYPE)
+#undef CASE_TYPED_ARRAY_TYPE
+    default:
+        RELEASE_ASSERT_NOT_REACHED();
+        return JSValue();
+    }
+}
+
+inline void JSObject::setIndexQuicklyForTypedArray(unsigned i, JSValue value)
+{
+    switch (type()) {
+#define CASE_TYPED_ARRAY_TYPE(name) \
+    case name ## ArrayType : {\
+        auto* typedArray = jsCast<JS ## name ## Array *>(this);\
+        RELEASE_ASSERT(typedArray->canSetIndexQuickly(i, value));\
+        typedArray->setIndexQuickly(i, value);\
+        break;\
+    }
+        FOR_EACH_TYPED_ARRAY_TYPE_EXCLUDING_DATA_VIEW(CASE_TYPED_ARRAY_TYPE)
+#undef CASE_TYPED_ARRAY_TYPE
+    default:
+        RELEASE_ASSERT_NOT_REACHED();
+        return;
+    }
+}
+    
+
 } // namespace JSC