[JSC] Add operationToInt32SensibleSlow to optimize kraken pbkdf2 and sha256
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 4 Feb 2017 13:46:19 +0000 (13:46 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 4 Feb 2017 13:46:19 +0000 (13:46 +0000)
https://bugs.webkit.org/show_bug.cgi?id=167736

Reviewed by Saam Barati.

JSTests:

* stress/to-int32-sensible.js: Added.
(shouldBe):
(toInt32):
(test):

Source/JavaScriptCore:

Add a new function operationToInt32SensibleSlow. This function is only
called after x86 cvttss2si_rr is failed. This means that the
given double number never in range of int32 truncatable numbers.

As a result, exp in operationToInt32 always becomes >= 31. So
we can change the condition from `exp < 32` to `exp == 31`.
This makes missingOne constant. And it leads significantly good
code generation.

The original operationToInt32 code.

    170:   66 48 0f 7e c1          movq   %xmm0,%rcx
    175:   31 c0                   xor    %eax,%eax
    177:   66 48 0f 7e c6          movq   %xmm0,%rsi
    17c:   48 c1 f9 34             sar    $0x34,%rcx
    180:   81 e1 ff 07 00 00       and    $0x7ff,%ecx
    186:   8d 91 01 fc ff ff       lea    -0x3ff(%rcx),%edx
    18c:   83 fa 53                cmp    $0x53,%edx
    18f:   77 37                   ja     1c8 <_ZN3JSC16operationToInt32Ed+0x58>
    191:   83 fa 34                cmp    $0x34,%edx
    194:   7f 3a                   jg     1d0 <_ZN3JSC16operationToInt32Ed+0x60>
    196:   b9 34 00 00 00          mov    $0x34,%ecx
    19b:   66 48 0f 7e c7          movq   %xmm0,%rdi
    1a0:   29 d1                   sub    %edx,%ecx
    1a2:   48 d3 ff                sar    %cl,%rdi
    1a5:   83 fa 1f                cmp    $0x1f,%edx
    1a8:   89 f8                   mov    %edi,%eax
    1aa:   7f 12                   jg     1be <_ZN3JSC16operationToInt32Ed+0x4e>
    1ac:   89 d1                   mov    %edx,%ecx
    1ae:   b8 01 00 00 00          mov    $0x1,%eax
    1b3:   d3 e0                   shl    %cl,%eax
    1b5:   89 c2                   mov    %eax,%edx
    1b7:   8d 40 ff                lea    -0x1(%rax),%eax
    1ba:   21 f8                   and    %edi,%eax
    1bc:   01 d0                   add    %edx,%eax
    1be:   89 c2                   mov    %eax,%edx
    1c0:   f7 da                   neg    %edx
    1c2:   48 85 f6                test   %rsi,%rsi
    1c5:   0f 48 c2                cmovs  %edx,%eax
    1c8:   f3 c3                   repz retq
    1ca:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
    1d0:   66 48 0f 7e c0          movq   %xmm0,%rax
    1d5:   81 e9 33 04 00 00       sub    $0x433,%ecx
    1db:   48 d3 e0                shl    %cl,%rax
    1de:   eb de                   jmp    1be <_ZN3JSC16operationToInt32Ed+0x4e>

The operationToInt32SensibleSlow code.

    1e0:   66 48 0f 7e c1          movq   %xmm0,%rcx
    1e5:   66 48 0f 7e c2          movq   %xmm0,%rdx
    1ea:   48 c1 f9 34             sar    $0x34,%rcx
    1ee:   81 e1 ff 07 00 00       and    $0x7ff,%ecx
    1f4:   8d b1 01 fc ff ff       lea    -0x3ff(%rcx),%esi
    1fa:   83 fe 34                cmp    $0x34,%esi
    1fd:   7e 21                   jle    220 <_ZN3JSC28operationToInt32SensibleSlowEd+0x40>
    1ff:   66 48 0f 7e c0          movq   %xmm0,%rax
    204:   81 e9 33 04 00 00       sub    $0x433,%ecx
    20a:   48 d3 e0                shl    %cl,%rax
    20d:   89 c1                   mov    %eax,%ecx
    20f:   f7 d9                   neg    %ecx
    211:   48 85 d2                test   %rdx,%rdx
    214:   0f 48 c1                cmovs  %ecx,%eax
    217:   c3                      retq
    218:   0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
    21f:   00
    220:   66 48 0f 7e c0          movq   %xmm0,%rax
    225:   b9 34 00 00 00          mov    $0x34,%ecx
    22a:   29 f1                   sub    %esi,%ecx
    22c:   48 d3 f8                sar    %cl,%rax
    22f:   89 c1                   mov    %eax,%ecx
    231:   81 c9 00 00 00 80       or     $0x80000000,%ecx
    237:   83 fe 1f                cmp    $0x1f,%esi
    23a:   0f 44 c1                cmove  %ecx,%eax
    23d:   89 c1                   mov    %eax,%ecx
    23f:   f7 d9                   neg    %ecx
    241:   48 85 d2                test   %rdx,%rdx
    244:   0f 48 c1                cmovs  %ecx,%eax
    247:   c3                      retq
    248:   0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
    24f:   00

This improves kraken pbkdf2 by 10.8% and sha256 by 7.5%.

                                               baseline                  patched

    stanford-crypto-pbkdf2                 153.195+-2.745      ^     138.204+-2.513         ^ definitely 1.1085x faster
    stanford-crypto-sha256-iterative        49.047+-1.038      ^      45.610+-1.235         ^ definitely 1.0754x faster

    <arithmetic>                           101.121+-1.379      ^      91.907+-1.500         ^ definitely 1.1003x faster

* assembler/CPU.h:
(JSC::hasSensibleDoubleToInt):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileValueToInt32):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::doubleToInt32):
(JSC::FTL::DFG::LowerDFGToB3::sensibleDoubleToInt32):
* ftl/FTLOutput.cpp:
(JSC::FTL::Output::hasSensibleDoubleToInt): Deleted.
* ftl/FTLOutput.h:
* runtime/MathCommon.cpp:
(JSC::operationToInt32SensibleSlow):
* runtime/MathCommon.h:

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

JSTests/ChangeLog
JSTests/stress/to-int32-sensible.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/assembler/CPU.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/JavaScriptCore/ftl/FTLOutput.cpp
Source/JavaScriptCore/ftl/FTLOutput.h
Source/JavaScriptCore/runtime/MathCommon.cpp
Source/JavaScriptCore/runtime/MathCommon.h

index 09f61e1..7d88102 100644 (file)
@@ -1,3 +1,15 @@
+2017-02-04  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [JSC] Add operationToInt32SensibleSlow to optimize kraken pbkdf2 and sha256
+        https://bugs.webkit.org/show_bug.cgi?id=167736
+
+        Reviewed by Saam Barati.
+
+        * stress/to-int32-sensible.js: Added.
+        (shouldBe):
+        (toInt32):
+        (test):
+
 2017-02-01  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         Unreviewed, remove loop
diff --git a/JSTests/stress/to-int32-sensible.js b/JSTests/stress/to-int32-sensible.js
new file mode 100644 (file)
index 0000000..4f5a12b
--- /dev/null
@@ -0,0 +1,40 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+// ValueToInt32(DoubleRep)
+function toInt32(number)
+{
+    return (number * 0.5) >> 0;
+}
+noInline(toInt32);
+for (var i = 0; i < 1e5; ++i)
+    toInt32(i * 1.0);
+
+function test(number)
+{
+    return toInt32(number * 2);
+}
+
+const INT32_MAX = 2147483647;
+const INT32_MIN = -2147483648;
+
+shouldBe(test(INT32_MAX - 1), INT32_MAX - 1);
+shouldBe(test(INT32_MAX - 0.5), INT32_MAX - 1);
+shouldBe(test(INT32_MAX), INT32_MAX);
+shouldBe(test(INT32_MAX + 0.5), INT32_MAX);
+shouldBe(test(INT32_MAX + 1), INT32_MIN);
+
+shouldBe(test(INT32_MIN - 1), INT32_MAX);
+shouldBe(test(INT32_MIN - 0.5), INT32_MIN);
+shouldBe(test(INT32_MIN), INT32_MIN);
+shouldBe(test(INT32_MIN + 0.5), INT32_MIN + 1);
+shouldBe(test(INT32_MIN + 1), INT32_MIN + 1);
+
+shouldBe(test(Number.EPSILON), 0);
+shouldBe(test(Number.NaN), 0);
+shouldBe(test(Number.POSITIVE_INFINITY), 0);
+shouldBe(test(Number.NEGATIVE_INFINITY), 0);
+shouldBe(test(Number.MAX_SAFE_INTEGER), -1);
+shouldBe(test(Number.MIN_SAFE_INTEGER), 1);
index 8a81c7b..011dbb7 100644 (file)
@@ -1,3 +1,114 @@
+2017-02-04  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [JSC] Add operationToInt32SensibleSlow to optimize kraken pbkdf2 and sha256
+        https://bugs.webkit.org/show_bug.cgi?id=167736
+
+        Reviewed by Saam Barati.
+
+        Add a new function operationToInt32SensibleSlow. This function is only
+        called after x86 cvttss2si_rr is failed. This means that the
+        given double number never in range of int32 truncatable numbers.
+
+        As a result, exp in operationToInt32 always becomes >= 31. So
+        we can change the condition from `exp < 32` to `exp == 31`.
+        This makes missingOne constant. And it leads significantly good
+        code generation.
+
+        The original operationToInt32 code.
+
+            170:   66 48 0f 7e c1          movq   %xmm0,%rcx
+            175:   31 c0                   xor    %eax,%eax
+            177:   66 48 0f 7e c6          movq   %xmm0,%rsi
+            17c:   48 c1 f9 34             sar    $0x34,%rcx
+            180:   81 e1 ff 07 00 00       and    $0x7ff,%ecx
+            186:   8d 91 01 fc ff ff       lea    -0x3ff(%rcx),%edx
+            18c:   83 fa 53                cmp    $0x53,%edx
+            18f:   77 37                   ja     1c8 <_ZN3JSC16operationToInt32Ed+0x58>
+            191:   83 fa 34                cmp    $0x34,%edx
+            194:   7f 3a                   jg     1d0 <_ZN3JSC16operationToInt32Ed+0x60>
+            196:   b9 34 00 00 00          mov    $0x34,%ecx
+            19b:   66 48 0f 7e c7          movq   %xmm0,%rdi
+            1a0:   29 d1                   sub    %edx,%ecx
+            1a2:   48 d3 ff                sar    %cl,%rdi
+            1a5:   83 fa 1f                cmp    $0x1f,%edx
+            1a8:   89 f8                   mov    %edi,%eax
+            1aa:   7f 12                   jg     1be <_ZN3JSC16operationToInt32Ed+0x4e>
+            1ac:   89 d1                   mov    %edx,%ecx
+            1ae:   b8 01 00 00 00          mov    $0x1,%eax
+            1b3:   d3 e0                   shl    %cl,%eax
+            1b5:   89 c2                   mov    %eax,%edx
+            1b7:   8d 40 ff                lea    -0x1(%rax),%eax
+            1ba:   21 f8                   and    %edi,%eax
+            1bc:   01 d0                   add    %edx,%eax
+            1be:   89 c2                   mov    %eax,%edx
+            1c0:   f7 da                   neg    %edx
+            1c2:   48 85 f6                test   %rsi,%rsi
+            1c5:   0f 48 c2                cmovs  %edx,%eax
+            1c8:   f3 c3                   repz retq
+            1ca:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
+            1d0:   66 48 0f 7e c0          movq   %xmm0,%rax
+            1d5:   81 e9 33 04 00 00       sub    $0x433,%ecx
+            1db:   48 d3 e0                shl    %cl,%rax
+            1de:   eb de                   jmp    1be <_ZN3JSC16operationToInt32Ed+0x4e>
+
+        The operationToInt32SensibleSlow code.
+
+            1e0:   66 48 0f 7e c1          movq   %xmm0,%rcx
+            1e5:   66 48 0f 7e c2          movq   %xmm0,%rdx
+            1ea:   48 c1 f9 34             sar    $0x34,%rcx
+            1ee:   81 e1 ff 07 00 00       and    $0x7ff,%ecx
+            1f4:   8d b1 01 fc ff ff       lea    -0x3ff(%rcx),%esi
+            1fa:   83 fe 34                cmp    $0x34,%esi
+            1fd:   7e 21                   jle    220 <_ZN3JSC28operationToInt32SensibleSlowEd+0x40>
+            1ff:   66 48 0f 7e c0          movq   %xmm0,%rax
+            204:   81 e9 33 04 00 00       sub    $0x433,%ecx
+            20a:   48 d3 e0                shl    %cl,%rax
+            20d:   89 c1                   mov    %eax,%ecx
+            20f:   f7 d9                   neg    %ecx
+            211:   48 85 d2                test   %rdx,%rdx
+            214:   0f 48 c1                cmovs  %ecx,%eax
+            217:   c3                      retq
+            218:   0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
+            21f:   00
+            220:   66 48 0f 7e c0          movq   %xmm0,%rax
+            225:   b9 34 00 00 00          mov    $0x34,%ecx
+            22a:   29 f1                   sub    %esi,%ecx
+            22c:   48 d3 f8                sar    %cl,%rax
+            22f:   89 c1                   mov    %eax,%ecx
+            231:   81 c9 00 00 00 80       or     $0x80000000,%ecx
+            237:   83 fe 1f                cmp    $0x1f,%esi
+            23a:   0f 44 c1                cmove  %ecx,%eax
+            23d:   89 c1                   mov    %eax,%ecx
+            23f:   f7 d9                   neg    %ecx
+            241:   48 85 d2                test   %rdx,%rdx
+            244:   0f 48 c1                cmovs  %ecx,%eax
+            247:   c3                      retq
+            248:   0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
+            24f:   00
+
+        This improves kraken pbkdf2 by 10.8% and sha256 by 7.5%.
+
+                                                       baseline                  patched
+
+            stanford-crypto-pbkdf2                 153.195+-2.745      ^     138.204+-2.513         ^ definitely 1.1085x faster
+            stanford-crypto-sha256-iterative        49.047+-1.038      ^      45.610+-1.235         ^ definitely 1.0754x faster
+
+            <arithmetic>                           101.121+-1.379      ^      91.907+-1.500         ^ definitely 1.1003x faster
+
+        * assembler/CPU.h:
+        (JSC::hasSensibleDoubleToInt):
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compileValueToInt32):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::doubleToInt32):
+        (JSC::FTL::DFG::LowerDFGToB3::sensibleDoubleToInt32):
+        * ftl/FTLOutput.cpp:
+        (JSC::FTL::Output::hasSensibleDoubleToInt): Deleted.
+        * ftl/FTLOutput.h:
+        * runtime/MathCommon.cpp:
+        (JSC::operationToInt32SensibleSlow):
+        * runtime/MathCommon.h:
+
 2017-02-03  Joseph Pecoraro  <pecoraro@apple.com>
 
         Unreviewed rollout of r211486, r211629.
index 2d2b486..8e8c82f 100644 (file)
@@ -85,5 +85,10 @@ inline bool optimizeForX86_64()
     return isX86_64() && Options::useArchitectureSpecificOptimizations();
 }
 
+inline bool hasSensibleDoubleToInt()
+{
+    return optimizeForX86();
+}
+
 } // namespace JSC
 
index 671c063..b25bc4a 100644 (file)
@@ -2208,7 +2208,8 @@ void SpeculativeJIT::compileValueToInt32(Node* node)
         GPRReg gpr = result.gpr();
         JITCompiler::Jump notTruncatedToInteger = m_jit.branchTruncateDoubleToInt32(fpr, gpr, JITCompiler::BranchIfTruncateFailed);
         
-        addSlowPathGenerator(slowPathCall(notTruncatedToInteger, this, operationToInt32, NeedToSpill, ExceptionCheckRequirement::CheckNotNeeded, gpr, fpr));
+        addSlowPathGenerator(slowPathCall(notTruncatedToInteger, this,
+            hasSensibleDoubleToInt() ? operationToInt32SensibleSlow : operationToInt32, NeedToSpill, ExceptionCheckRequirement::CheckNotNeeded, gpr, fpr));
         
         int32Result(gpr, node);
         return;
index 6dcaf85..97ba3fb 100644 (file)
@@ -11591,7 +11591,7 @@ private:
     
     LValue doubleToInt32(LValue doubleValue)
     {
-        if (Output::hasSensibleDoubleToInt())
+        if (hasSensibleDoubleToInt())
             return sensibleDoubleToInt32(doubleValue);
         
         double limit = pow(2, 31) - 1;
@@ -11611,7 +11611,7 @@ private:
         
         LBasicBlock lastNext = m_out.appendTo(slowPath, continuation);
         ValueFromBlock slowResult = m_out.anchor(
-            m_out.call(Int32, m_out.operation(operationToInt32), doubleValue));
+            m_out.call(Int32, m_out.operation(operationToInt32SensibleSlow), doubleValue));
         m_out.jump(continuation);
         
         m_out.appendTo(continuation, lastNext);
index bf209b0..bd65e64 100644 (file)
@@ -333,11 +333,6 @@ LValue Output::doubleLog(LValue value)
     return callWithoutSideEffects(B3::Double, logDouble, value);
 }
 
-bool Output::hasSensibleDoubleToInt()
-{
-    return optimizeForX86();
-}
-
 LValue Output::doubleToInt(LValue value)
 {
     PatchpointValue* result = patchpoint(Int32);
index 433e1e0..91e548c 100644 (file)
@@ -193,7 +193,6 @@ public:
 
     LValue doubleLog(LValue);
 
-    static bool hasSensibleDoubleToInt();
     LValue doubleToInt(LValue);
     LValue doubleToUInt(LValue);
 
index 6f11975..eb060a1 100644 (file)
@@ -467,6 +467,71 @@ int32_t JIT_OPERATION operationToInt32(double value)
     return JSC::toInt32(value);
 }
 
+int32_t JIT_OPERATION operationToInt32SensibleSlow(double number)
+{
+    // This function is specialized `operationToInt32` for the slow case of
+    // the sensible double-to-int32 operation. It is available in x86.
+    //
+    // In the sensible double-to-int32, first we attempt to truncate the
+    // double value to int32 by using cvttsd2si_rr.
+    // According to the Intel's manual, cvttsd2si perform the following truncate
+    // operation.
+    //
+    // If src = NaN, +-Inf, or |(src)rz| > 0x7fffffff and (src)rz != 0x80000000,
+    // the result becomes 0x80000000. Otherwise, the operation succeeds.
+    // Note that ()rz is rouding towards zero.
+    //
+    // We call this slow case function when the above cvttsd2si fails. We check
+    // this condition by performing `result == 0x80000000`. So this function only
+    // accepts the following numbers.
+    //
+    //     NaN, +-Inf, |(src)rz| > 0x7fffffff.
+    //
+    // As a result, the exp of the double is always >= 31.
+    // This condition simplifies and speeds up the toInt32 implementation.
+    int64_t bits = WTF::bitwise_cast<int64_t>(number);
+    int32_t exp = (static_cast<int32_t>(bits >> 52) & 0x7ff) - 0x3ff;
+
+    // If exponent < 0 there will be no bits to the left of the decimal point
+    // after rounding; if the exponent is > 83 then no bits of precision can be
+    // left in the low 32-bit range of the result (IEEE-754 doubles have 52 bits
+    // of fractional precision).
+    // Note this case handles 0, -0, and all infinite, NaN, & denormal value.
+
+    // If exp < 0, truncate operation succeeds. So this function does not
+    // encounter that case. If exp > 83, it means exp >= 84. In that case,
+    // the following operation produces 0 for the result.
+    ASSERT(exp >= 0);
+
+    // Select the appropriate 32-bits from the floating point mantissa. If the
+    // exponent is 52 then the bits we need to select are already aligned to the
+    // lowest bits of the 64-bit integer representation of the number, no need
+    // to shift. If the exponent is greater than 52 we need to shift the value
+    // left by (exp - 52), if the value is less than 52 we need to shift right
+    // accordingly.
+    int32_t result = (exp > 52)
+        ? static_cast<int32_t>(bits << (exp - 52))
+        : static_cast<int32_t>(bits >> (52 - exp));
+
+    // IEEE-754 double precision values are stored omitting an implicit 1 before
+    // the decimal point; we need to reinsert this now. We may also the shifted
+    // invalid bits into the result that are not a part of the mantissa (the sign
+    // and exponent bits from the floatingpoint representation); mask these out.
+    //
+    // The important observation is that exp is always >= 31. So the above case
+    // is needed to be cared only when the exp == 31.
+    ASSERT(exp >= 31);
+    if (exp == 31) {
+        int32_t missingOne = 1 << exp;
+        result &= (missingOne - 1);
+        result += missingOne;
+    }
+
+    // If the input value was negative (we could test either 'number' or 'bits',
+    // but testing 'bits' is likely faster) invert the result appropriately.
+    return bits < 0 ? -result : result;
+}
+
 #if HAVE(ARM_IDIV_INSTRUCTIONS)
 static inline bool isStrictInt32(double value)
 {
index 6325786..4bc2f90 100644 (file)
@@ -33,6 +33,7 @@ namespace JSC {
 const int32_t maxExponentForIntegerMathPow = 1000;
 double JIT_OPERATION operationMathPow(double x, double y) WTF_INTERNAL;
 int32_t JIT_OPERATION operationToInt32(double) WTF_INTERNAL;
+int32_t JIT_OPERATION operationToInt32SensibleSlow(double) WTF_INTERNAL;
 
 inline constexpr double maxSafeInteger()
 {