[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 4aa1bf0..b1c396f 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 1b3c8b7..cbd9b77 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 0fefa54..6b0e07c 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 a06a54b..921c506 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 c96d41f..e96bf73 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 9195dec..e947833 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 de4fe13..6574fd0 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);