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

Reviewed by Saam Barati.

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@239377 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 704dec4..8bc4eef 100644 (file)
@@ -1,3 +1,14 @@
+2018-12-19  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 Saam Barati.
+
+        * BigIntBench/big-int-cse.js: Added.
+        * BigIntBench/big-int-global-cse.js: Added.
+        * BigIntBench/big-int-licm.js: Added.
+
 2018-12-17  Suresh Koppisetty  <skoppisetty@apple.com>
 
         Add "-o/--output" option to startup.py and new_tab.py benchmark scripts to save the results in json format.
index b6d34d6..061d90b 100644 (file)
@@ -1,3 +1,30 @@
+2018-12-19  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 Saam Barati.
+
+        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  Tadeu Zagallo  <tzagallo@apple.com>
 
         String overflow in JSC::createError results in ASSERT in WTF::makeString
index 2446db6..4cc88f5 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 9031605..95c6e73 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();
@@ -364,6 +373,10 @@ private:
                 convertToLazyJSValue(m_node, LazyJSValue::newString(m_graph, builder.toString()));
                 m_changed = true;
             }
+
+            if (m_node->binaryUseKind() == BigIntUse)
+                handleCommutativity();
+
             break;
         }