[DFG][FTL] Add vectorLengthHint for NewArray
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 20 Mar 2018 07:58:22 +0000 (07:58 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 20 Mar 2018 07:58:22 +0000 (07:58 +0000)
https://bugs.webkit.org/show_bug.cgi?id=183694

Reviewed by Saam Barati.

JSTests:

* stress/vector-length-hint-array-constructor.js: Added.
(shouldBe):
(test):
* stress/vector-length-hint-new-array.js: Added.
(shouldBe):
(test):

Source/JavaScriptCore:

While the following code is a common, it is not so efficient.

var array = [];
for (...) {
    ...
    array.push(...);
}

The array is always allocated with 0 vector length. And it is eventually grown.

We have ArrayAllocationProfile, and it tells us that the vector length hint for
the allocated arrays. This hint is already used for NewArrayBuffer. This patch
extends this support for NewArray DFG node.

This patch improves Kraken/stanford-crypto-aes 4%.

                              baseline                  patched

stanford-crypto-aes        64.069+-1.352             61.589+-1.274           might be 1.0403x faster

NewArray can be optimized.

                                               baseline                  patched

vector-length-hint-new-array               21.8157+-0.0882     ^     13.1764+-0.0942        ^ definitely 1.6557x faster
vector-length-hint-array-constructor       21.9076+-0.0987     ?     22.1168+-0.4814        ?

* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleConstantInternalFunction):
(JSC::DFG::ByteCodeParser::parseBlock):
* dfg/DFGNode.h:
(JSC::DFG::Node::hasVectorLengthHint):
(JSC::DFG::Node::vectorLengthHint):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNewArray):

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

JSTests/ChangeLog
JSTests/microbenchmarks/vector-length-hint-array-constructor.js [new file with mode: 0644]
JSTests/microbenchmarks/vector-length-hint-new-array.js [new file with mode: 0644]
JSTests/stress/vector-length-hint-array-constructor.js [new file with mode: 0644]
JSTests/stress/vector-length-hint-new-array.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/dfg/DFGValidate.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp

index 4aa1bf0567938a4de6820e5f0c424a17deb23197..b1c396fdb7e236cf6069258c7e8703feddf0f2ab 100644 (file)
@@ -1,3 +1,17 @@
+2018-03-16  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [DFG][FTL] Add vectorLengthHint for NewArray
+        https://bugs.webkit.org/show_bug.cgi?id=183694
+
+        Reviewed by Saam Barati.
+
+        * stress/vector-length-hint-array-constructor.js: Added.
+        (shouldBe):
+        (test):
+        * stress/vector-length-hint-new-array.js: Added.
+        (shouldBe):
+        (test):
+
 2018-03-13  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [DFG][FTL] Make ArraySlice(0) code tight
diff --git a/JSTests/microbenchmarks/vector-length-hint-array-constructor.js b/JSTests/microbenchmarks/vector-length-hint-array-constructor.js
new file mode 100644 (file)
index 0000000..36edecf
--- /dev/null
@@ -0,0 +1,11 @@
+function test(constructor)
+{
+    var array = new constructor(1, 2);
+    for (var i = 0; i < 20; ++i)
+        array.push(i);
+    return array;
+}
+noInline(test);
+
+for (var i = 0; i < 1e5; ++i)
+    var result = test(Array);
diff --git a/JSTests/microbenchmarks/vector-length-hint-new-array.js b/JSTests/microbenchmarks/vector-length-hint-new-array.js
new file mode 100644 (file)
index 0000000..b8eeb9f
--- /dev/null
@@ -0,0 +1,11 @@
+function test(v0, v1)
+{
+    var array = [v0, v1];
+    for (var i = 0; i < 20; ++i)
+        array.push(i);
+    return array;
+}
+noInline(test);
+
+for (var i = 0; i < 1e5; ++i)
+    test(1, 2);
diff --git a/JSTests/stress/vector-length-hint-array-constructor.js b/JSTests/stress/vector-length-hint-array-constructor.js
new file mode 100644 (file)
index 0000000..8e8f52c
--- /dev/null
@@ -0,0 +1,18 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + String(actual) + ' ' + String(expected));
+}
+
+function test(constructor)
+{
+    var array = new constructor(1, 2);
+    for (var i = 0; i < 20; ++i)
+        array.push(i);
+    return array;
+}
+noInline(test);
+
+for (var i = 0; i < 1e5; ++i) {
+    var result = test(Array);
+    shouldBe(JSON.stringify(result), `[1,2,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]`);
+}
diff --git a/JSTests/stress/vector-length-hint-new-array.js b/JSTests/stress/vector-length-hint-new-array.js
new file mode 100644 (file)
index 0000000..d8cb6c9
--- /dev/null
@@ -0,0 +1,18 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + String(actual) + ' ' + String(expected));
+}
+
+function test(v0, v1)
+{
+    var array = [v0, v1];
+    for (var i = 0; i < 20; ++i)
+        array.push(i);
+    return array;
+}
+noInline(test);
+
+for (var i = 0; i < 1e5; ++i) {
+    var result = test(1, 2);
+    shouldBe(JSON.stringify(result), `[1,2,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]`);
+}
index 1b3c8b7686c269275d03a31798f992896ae93009..cbd9b7701f04554b4c5c60ac22a0e4e48efe430d 100644 (file)
@@ -1,3 +1,48 @@
+2018-03-16  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [DFG][FTL] Add vectorLengthHint for NewArray
+        https://bugs.webkit.org/show_bug.cgi?id=183694
+
+        Reviewed by Saam Barati.
+
+        While the following code is a common, it is not so efficient.
+
+        var array = [];
+        for (...) {
+            ...
+            array.push(...);
+        }
+
+        The array is always allocated with 0 vector length. And it is eventually grown.
+
+        We have ArrayAllocationProfile, and it tells us that the vector length hint for
+        the allocated arrays. This hint is already used for NewArrayBuffer. This patch
+        extends this support for NewArray DFG node.
+
+        This patch improves Kraken/stanford-crypto-aes 4%.
+
+                                      baseline                  patched
+
+        stanford-crypto-aes        64.069+-1.352             61.589+-1.274           might be 1.0403x faster
+
+        NewArray can be optimized.
+
+                                                       baseline                  patched
+
+        vector-length-hint-new-array               21.8157+-0.0882     ^     13.1764+-0.0942        ^ definitely 1.6557x faster
+        vector-length-hint-array-constructor       21.9076+-0.0987     ?     22.1168+-0.4814        ?
+
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::handleConstantInternalFunction):
+        (JSC::DFG::ByteCodeParser::parseBlock):
+        * dfg/DFGNode.h:
+        (JSC::DFG::Node::hasVectorLengthHint):
+        (JSC::DFG::Node::vectorLengthHint):
+        * dfg/DFGSpeculativeJIT64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::compileNewArray):
+
 2018-03-13  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [DFG][FTL] Make ArraySlice(0) code tight
index 0fefa547e33eee22063537d0e461a994fbec49af..6b0e07c94213690fcc887331f5cdbd094e96f977 100644 (file)
@@ -3455,7 +3455,7 @@ bool ByteCodeParser::handleConstantInternalFunction(
         for (int i = 1; i < argumentCountIncludingThis; ++i)
             addVarArgChild(get(virtualRegisterForArgument(i, registerOffset)));
         set(VirtualRegister(resultOperand),
-            addToGraph(Node::VarArg, NewArray, OpInfo(ArrayWithUndecided), OpInfo(0)));
+            addToGraph(Node::VarArg, NewArray, OpInfo(ArrayWithUndecided), OpInfo(argumentCountIncludingThis - 1)));
         return true;
     }
 
@@ -4510,7 +4510,8 @@ void ByteCodeParser::parseBlock(unsigned limit)
             ArrayAllocationProfile* profile = currentInstruction[4].u.arrayAllocationProfile;
             for (int operandIdx = startOperand; operandIdx > startOperand - numOperands; --operandIdx)
                 addVarArgChild(get(VirtualRegister(operandIdx)));
-            set(VirtualRegister(currentInstruction[1].u.operand), addToGraph(Node::VarArg, NewArray, OpInfo(profile->selectIndexingType()), OpInfo(0)));
+            unsigned vectorLengthHint = std::max<unsigned>(profile->vectorLengthHint(), numOperands);
+            set(VirtualRegister(currentInstruction[1].u.operand), addToGraph(Node::VarArg, NewArray, OpInfo(profile->selectIndexingType()), OpInfo(vectorLengthHint)));
             NEXT_OPCODE(op_new_array);
         }
 
index a06a54bfe903a1eae7c53fa487c44997c4a87285..921c506500cb515722fa2ea890785df437de08a3 100644 (file)
@@ -1121,12 +1121,21 @@ public:
 
     unsigned hasVectorLengthHint()
     {
-        return op() == NewArrayBuffer || op() == PhantomNewArrayBuffer;
+        switch (op()) {
+        case NewArray:
+        case NewArrayBuffer:
+        case PhantomNewArrayBuffer:
+            return true;
+        default:
+            return false;
+        }
     }
     
     unsigned vectorLengthHint()
     {
         ASSERT(hasVectorLengthHint());
+        if (op() == NewArray)
+            return m_opInfo2.as<unsigned>();
         return newArrayBufferData().vectorLengthHint;
     }
     
index c96d41f73d40a79ed8e746083c085cc0c52ee0a7..e96bf73927019dcbccb5f5a46ebc87eba374f0de 100644 (file)
@@ -3730,6 +3730,8 @@ void SpeculativeJIT::compile(Node* node)
                 || hasContiguous(structure->indexingType()));
             
             unsigned numElements = node->numChildren();
+            unsigned vectorLengthHint = node->vectorLengthHint();
+            ASSERT(vectorLengthHint >= numElements);
             
             GPRTemporary result(this);
             GPRTemporary storage(this);
@@ -3737,7 +3739,7 @@ void SpeculativeJIT::compile(Node* node)
             GPRReg resultGPR = result.gpr();
             GPRReg storageGPR = storage.gpr();
 
-            emitAllocateRawObject(resultGPR, structure, storageGPR, numElements, numElements);
+            emitAllocateRawObject(resultGPR, structure, storageGPR, numElements, vectorLengthHint);
             
             // At this point, one way or another, resultGPR and storageGPR have pointers to
             // the JSArray and the Butterfly, respectively.
index 9195dec037d194ed746773f876fd5e62f0f15438..e94783353042c980205451d9a0fa488afaf6632b 100644 (file)
@@ -351,6 +351,12 @@ public:
                         VALIDATE((node), inlineCallFrame->isVarargs());
                     break;
                 }
+                case NewArray:
+                    VALIDATE((node), node->vectorLengthHint() >= node->numChildren());
+                    break;
+                case NewArrayBuffer:
+                    VALIDATE((node), node->vectorLengthHint() >= node->castOperand<JSFixedArray*>()->length());
+                    break;
                 default:
                     break;
                 }
@@ -787,6 +793,7 @@ private:
 
                 case PhantomNewArrayBuffer:
                     VALIDATE((node), m_graph.m_form == SSA);
+                    VALIDATE((node), node->vectorLengthHint() >= node->castOperand<JSFixedArray*>()->length());
                     break;
 
                 case NewArrayWithSpread: {
index de4fe13adbde507bc5498e56fe28d6d01587f6ee..6574fd0ca10a4f0d4e5a76b45cf350105c172fa0 100644 (file)
@@ -5411,9 +5411,11 @@ private:
 
         if (!globalObject->isHavingABadTime() && !hasAnyArrayStorage(m_node->indexingType())) {
             unsigned numElements = m_node->numChildren();
+            unsigned vectorLengthHint = m_node->vectorLengthHint();
+            ASSERT(vectorLengthHint >= numElements);
             
             ArrayValues arrayValues =
-                allocateUninitializedContiguousJSArray(m_out.constInt32(numElements), structure);
+                allocateUninitializedContiguousJSArray(numElements, vectorLengthHint, structure);
             
             for (unsigned operandIndex = 0; operandIndex < m_node->numChildren(); ++operandIndex) {
                 Edge edge = m_graph.varArgChild(m_node, operandIndex);