[BigInt] We should enable CSE into arithmetic operations that speculate BigIntUse
authorticaiolima@gmail.com <ticaiolima@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 20 Dec 2018 11:59:05 +0000 (11:59 +0000)
committerticaiolima@gmail.com <ticaiolima@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 20 Dec 2018 11:59:05 +0000 (11:59 +0000)
https://bugs.webkit.org/show_bug.cgi?id=192723

Reviewed by Yusuke Suzuki.

PerformanceTests:

* BigIntBench/big-int-cse.js: Added.
* BigIntBench/big-int-global-cse.js: Added.
* BigIntBench/big-int-licm.js: Added.

Source/JavaScriptCore:

This patch is adjusting clobberize rules into ValueOp nodes to enable
more optimizations when we speculate BigIntUse. In such case, DFG now
is able to apply CSE, LICM and commutativity on nodes like
ValueAdd(BigInt, BigInt), ValueSub(BigInt, BigInt), etc.

Here are the numbers we can observe with some microbenchmarks:

                          baseline                 changes

big-int-cse           108.2733+-0.8445    ^    80.9897+-4.9781   ^ definitely 1.3369x faster
big-int-licm          75.6641+-0.3477     ^    57.8144+-1.6043   ^ definitely 1.3087x faster
big-int-global-cse    145.3557+-1.0552    ^    86.5866+-0.3025   ^ definitely 1.6787x faster

* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGStrengthReductionPhase.cpp:
(JSC::DFG::StrengthReductionPhase::handleNode):

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

PerformanceTests/BigIntBench/big-int-cse.js [new file with mode: 0644]
PerformanceTests/BigIntBench/big-int-global-cse.js [new file with mode: 0644]
PerformanceTests/BigIntBench/big-int-licm.js [new file with mode: 0644]
PerformanceTests/ChangeLog
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp

diff --git a/PerformanceTests/BigIntBench/big-int-cse.js b/PerformanceTests/BigIntBench/big-int-cse.js
new file mode 100644 (file)
index 0000000..d8b53dd
--- /dev/null
@@ -0,0 +1,103 @@
+function assert(a, e) {
+    if (a !== e)
+        throw new Error("Expected " + e + " but got: " + a);
+}
+
+function bigIntAdd(a, b) {
+    let c = a + b;
+    return b + a + c;
+}
+noInline(bigIntAdd);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntAdd(3n, 5n), 16n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntAdd(0xffffffffffffffffffn, 0xaaffffffffffffffffffn), 1624494070107157953511420n);
+}
+
+function bigIntMul(a, b) {
+    let c = a * b;
+    return b * a + c;
+}
+noInline(bigIntMul);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntMul(3n, 5n), 30n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntMul(0xffffffffffffffffffn, 0xaaffffffffffffffffffn), 7626854857897473114403591155175632477091790850n);
+}
+
+function bigIntDiv(a, b) {
+    let c = a / b;
+    return a / b + c;
+}
+noInline(bigIntDiv);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntDiv(15n, 5n), 6n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntDiv(0xaaffffffffffffffffffn, 0xffffffffffffffffffn), 342n);
+}
+
+function bigIntSub(a, b) {
+    let c = a - b;
+    return a - b + c;
+}
+noInline(bigIntSub);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntSub(15n, 5n), 20n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntSub(0xaaffffffffffffffffffn, 0xffffffffffffffffffn), 1605604604175679372656640n);
+}
+
+function bigIntBitOr(a, b) {
+    let c = a | b;
+    return (b | a) + c;
+}
+noInline(bigIntBitOr);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitOr(0b1101n, 0b0010n), 30n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitOr(0xaaffffffffffffffffffn, 0xffffffffffffffffffn), 1615049337141418663084030n);
+}
+
+function bigIntBitAnd(a, b) {
+    let c = a & b;
+    return (b & a) + c;
+}
+noInline(bigIntBitAnd);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitAnd(0b1101n, 0b0010n), 0n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitAnd(0xaaffffffffffffffffffn, 0xffffffffffffffffffn), 9444732965739290427390n);
+}
+
+function bigIntBitXor(a, b) {
+    let c = a ^ b;
+    return (b ^ a) + c;
+}
+noInline(bigIntBitXor);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitXor(0b1101n, 0b0010n), 30n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitXor(0xaaffffffffffffffffffn, 0xffffffffffffffffffn), 1605604604175679372656640n);
+}
+
diff --git a/PerformanceTests/BigIntBench/big-int-global-cse.js b/PerformanceTests/BigIntBench/big-int-global-cse.js
new file mode 100644 (file)
index 0000000..d5c0246
--- /dev/null
@@ -0,0 +1,124 @@
+function assert(a, e) {
+    if (a !== e)
+        throw new Error("Expected " + e + " but got: " + a);
+}
+
+function bigIntAdd(a, b) {
+    let c = a + b;
+    if (b) {
+        assert(c, a + b);
+    }
+    return a + b + c;
+}
+noInline(bigIntAdd);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntAdd(3n, 5n), 16n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntAdd(0xffffffffffffffffffn, 0xaaffffffffffffffffffn), 1624494070107157953511420n);
+}
+
+function bigIntMul(a, b) {
+    let c = a * b;
+    if (b) {
+        assert(c, a * b);
+    }
+    return a * b + c;
+}
+noInline(bigIntMul);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntMul(3n, 5n), 30n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntMul(0xffffffffffffffffffn, 0xaaffffffffffffffffffn), 7626854857897473114403591155175632477091790850n);
+}
+
+function bigIntDiv(a, b) {
+    let c = a / b;
+    if (b) {
+        assert(c, a / b);
+    }
+    return a / b + c;
+}
+noInline(bigIntDiv);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntDiv(15n, 5n), 6n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntDiv(0xaaffffffffffffffffffn, 0xffffffffffffffffffn), 342n);
+}
+
+function bigIntSub(a, b) {
+    let c = a - b;
+    if (b) {
+        assert(c, a - b);
+    }
+    return a - b + c;
+}
+noInline(bigIntSub);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntSub(15n, 5n), 20n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntSub(0xaaffffffffffffffffffn, 0xffffffffffffffffffn), 1605604604175679372656640n);
+}
+
+function bigIntBitOr(a, b) {
+    let c = a | b;
+    if (b) {
+        assert(c, a | b);
+    }
+    return (a | b) + c;
+}
+noInline(bigIntBitOr);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitOr(0b1101n, 0b0010n), 30n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitOr(0xaaffffffffffffffffffn, 0xffffffffffffffffffn), 1615049337141418663084030n);
+}
+
+function bigIntBitAnd(a, b) {
+    let c = a & b;
+    if (b) {
+        assert(c, a & b);
+    }
+    return (a & b) + c;
+}
+noInline(bigIntBitAnd);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitAnd(0b1101n, 0b0010n), 0n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitAnd(0xaaffffffffffffffffffn, 0xffffffffffffffffffn), 9444732965739290427390n);
+}
+
+function bigIntBitXor(a, b) {
+    let c = a ^ b;
+    if (b) {
+        assert(c, a ^ b);
+    }
+    return (a ^ b) + c;
+}
+noInline(bigIntBitXor);
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitXor(0b1101n, 0b0010n), 30n);
+}
+
+for (let i = 0; i < 100000; i++) {
+    assert(bigIntBitXor(0xaaffffffffffffffffffn, 0xffffffffffffffffffn), 1605604604175679372656640n);
+}
+
diff --git a/PerformanceTests/BigIntBench/big-int-licm.js b/PerformanceTests/BigIntBench/big-int-licm.js
new file mode 100644 (file)
index 0000000..6c64c97
--- /dev/null
@@ -0,0 +1,19 @@
+function assert(a, e) {
+    if (a !== e)
+        throw new Error("Expected " + e + " but got: " + a);
+}
+
+function iteration(a, b, r) {
+    let acc = 0n;
+    for (let i = 0n; i < r; i += 1n) {
+        acc += a + b;
+    }
+
+    return acc;
+}
+noInline(iteration);
+
+for (let i = 0; i < 10000; i++) {
+    assert(iteration(1n, 2n, 100n), 300n)
+}
+
index c115c5b..e324404 100644 (file)
@@ -1,3 +1,14 @@
+2018-12-20  Caio Lima  <ticaiolima@gmail.com>
+
+        [BigInt] We should enable CSE into arithmetic operations that speculate BigIntUse
+        https://bugs.webkit.org/show_bug.cgi?id=192723
+
+        Reviewed by Yusuke Suzuki.
+
+        * BigIntBench/big-int-cse.js: Added.
+        * BigIntBench/big-int-global-cse.js: Added.
+        * BigIntBench/big-int-licm.js: Added.
+
 2018-12-19  Commit Queue  <commit-queue@webkit.org>
 
         Unreviewed, rolling out r239377.
index d60fcf1..cf71a88 100644 (file)
@@ -1,3 +1,30 @@
+2018-12-20  Caio Lima  <ticaiolima@gmail.com>
+
+        [BigInt] We should enable CSE into arithmetic operations that speculate BigIntUse
+        https://bugs.webkit.org/show_bug.cgi?id=192723
+
+        Reviewed by Yusuke Suzuki.
+
+        This patch is adjusting clobberize rules into ValueOp nodes to enable
+        more optimizations when we speculate BigIntUse. In such case, DFG now
+        is able to apply CSE, LICM and commutativity on nodes like
+        ValueAdd(BigInt, BigInt), ValueSub(BigInt, BigInt), etc.
+
+        Here are the numbers we can observe with some microbenchmarks:
+
+                                  baseline                 changes
+
+        big-int-cse           108.2733+-0.8445    ^    80.9897+-4.9781   ^ definitely 1.3369x faster
+        big-int-licm          75.6641+-0.3477     ^    57.8144+-1.6043   ^ definitely 1.3087x faster
+        big-int-global-cse    145.3557+-1.0552    ^    86.5866+-0.3025   ^ definitely 1.6787x faster
+
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+        * dfg/DFGClobberize.h:
+        (JSC::DFG::clobberize):
+        * dfg/DFGStrengthReductionPhase.cpp:
+        (JSC::DFG::StrengthReductionPhase::handleNode):
+
 2018-12-19  Commit Queue  <commit-queue@webkit.org>
 
         Unreviewed, rolling out r239377.
index f288d6e..5197133 100644 (file)
@@ -397,11 +397,12 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
     case ValueBitXor:
     case ValueBitAnd:
     case ValueBitOr:
-        clobberWorld();
         if (node->binaryUseKind() == BigIntUse)
             setTypeForNode(node, SpecBigInt);
-        else
+        else {
+            clobberWorld();
             setTypeForNode(node, SpecBoolInt32 | SpecBigInt);
+        }
         break;
             
     case ArithBitAnd:
@@ -613,11 +614,12 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
     case ValueSub:
     case ValueAdd: {
         DFG_ASSERT(m_graph, node, node->binaryUseKind() == UntypedUse || node->binaryUseKind() == BigIntUse);
-        clobberWorld();
         if (node->binaryUseKind() == BigIntUse)
             setTypeForNode(node, SpecBigInt);
-        else
+        else {
+            clobberWorld();
             setTypeForNode(node, SpecString | SpecBytecodeNumber | SpecBigInt);
+        }
         break;
     }
 
@@ -856,11 +858,12 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
     }
         
     case ValueMul: {
-        clobberWorld();
         if (node->binaryUseKind() == BigIntUse)
             setTypeForNode(node, SpecBigInt);
-        else
+        else {
+            clobberWorld();
             setTypeForNode(node, SpecBytecodeNumber | SpecBigInt);
+        }
         break;
     }
 
@@ -915,11 +918,12 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
     }
         
     case ValueDiv: {
-        clobberWorld();
         if (node->binaryUseKind() == BigIntUse)
             setTypeForNode(node, SpecBigInt);
-        else
+        else {
+            clobberWorld();
             setTypeForNode(node, SpecBytecodeNumber | SpecBigInt);
+        }
         break;
     }
 
index 250ec00..48c846b 100644 (file)
@@ -644,14 +644,7 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
     case InByVal:
     case InById:
     case HasOwnProperty:
-    case ValueBitAnd:
-    case ValueBitXor:
-    case ValueBitOr:
     case ValueNegate:
-    case ValueAdd:
-    case ValueSub:
-    case ValueMul:
-    case ValueDiv:
     case SetFunctionName:
     case GetDynamicVar:
     case PutDynamicVar:
@@ -673,6 +666,21 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
         write(Heap);
         return;
 
+    case ValueBitAnd:
+    case ValueBitXor:
+    case ValueBitOr:
+    case ValueAdd:
+    case ValueSub:
+    case ValueMul:
+    case ValueDiv:
+        if (node->isBinaryUseKind(BigIntUse)) {
+            def(PureValue(node));
+            return;
+        }
+        read(World);
+        write(Heap);
+        return;
+
     case AtomicsAdd:
     case AtomicsAnd:
     case AtomicsCompareExchange:
index 4f2f1d0..18bec69 100644 (file)
@@ -121,6 +121,15 @@ private:
             }
             break;
             
+        case ValueMul:
+        case ValueBitOr:
+        case ValueBitAnd:
+        case ValueBitXor: {
+            if (m_node->binaryUseKind() == BigIntUse)
+                handleCommutativity();
+            break;
+        }
+
         case ArithMul: {
             handleCommutativity();
             Edge& child2 = m_node->child2();
@@ -363,7 +372,12 @@ private:
                 builder.append(rightString);
                 convertToLazyJSValue(m_node, LazyJSValue::newString(m_graph, builder.toString()));
                 m_changed = true;
+                break;
             }
+
+            if (m_node->binaryUseKind() == BigIntUse)
+                handleCommutativity();
+
             break;
         }