Attachment 357436 Details for Bug 192723 – Proposed Patch

[patch] Proposed Patch

bug-192723-20181217115108.patch (text/plain), 13.07 KB, created by Caio Lima on 2018-12-17 05:51:11 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Caio Lima

Created: 2018-12-17 05:51:11 PST

Size: 13.07 KB

patch

obsolete

>Subversion Revision: 239251
>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index a70463f46e3ced863f75393c2b2400eb1ea59850..6047a65bebe1a135e764bb93a4564ba2fc82c52f 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,30 @@
>+2018-12-17  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 NOBODY (OOPS!).
>+
>+        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-14  Darin Adler  <darin@apple.com>
> 
>         LiteralParser has a bunch of uses of String::format with untrusted data
>diff --git a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
>index 5f5eccc330c22be8bd91e1b4cd7b759714a0dd67..c7e9f7ffafc73746bca4153b0f14be1531a93e63 100644
>--- a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
>+++ b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
>@@ -396,11 +396,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:
>@@ -612,11 +613,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;
>     }
> 
>@@ -855,11 +857,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;
>     }
> 
>@@ -914,11 +917,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;
>     }
> 
>diff --git a/Source/JavaScriptCore/dfg/DFGClobberize.h b/Source/JavaScriptCore/dfg/DFGClobberize.h
>index 87424207c4016483bdbfb4202990e2a27ee99d5f..30f41fee32cad59f7a42a31bcd1d69752867b1bd 100644
>--- a/Source/JavaScriptCore/dfg/DFGClobberize.h
>+++ b/Source/JavaScriptCore/dfg/DFGClobberize.h
>@@ -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:
>@@ -672,6 +665,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:
>diff --git a/Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp b/Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp
>index 90316057ecf789f8f4d2c180eee36a1fb960df27..95c6e739b57c9c5ed783d262f4b296807bc9f7f9 100644
>--- a/Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp
>+++ b/Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp
>@@ -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;
>         }
> 
>diff --git a/PerformanceTests/BigIntBench/big-int-cse.js b/PerformanceTests/BigIntBench/big-int-cse.js
>new file mode 100644
>index 0000000000000000000000000000000000000000..d8b53dd7212746f590e15b66853270905ec52230
>--- /dev/null
>+++ b/PerformanceTests/BigIntBench/big-int-cse.js
>@@ -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
>index 0000000000000000000000000000000000000000..d5c0246b263ca7770af1ee7081e6c5a3d4c17c3b
>--- /dev/null
>+++ b/PerformanceTests/BigIntBench/big-int-global-cse.js
>@@ -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
>index 0000000000000000000000000000000000000000..6c64c9757983edc59e25e6bd912a049f07e6b2ce
>--- /dev/null
>+++ b/PerformanceTests/BigIntBench/big-int-licm.js
>@@ -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)
>+}
>+
>diff --git a/PerformanceTests/ChangeLog b/PerformanceTests/ChangeLog
>index c59f3f60d28bb7d0b85229d339934ffa3a8b4763..232af92be6326c4d5ea8f9090a56021bf181530c 100644
>--- a/PerformanceTests/ChangeLog
>+++ b/PerformanceTests/ChangeLog
>@@ -1,3 +1,14 @@
>+2018-12-17  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 NOBODY (OOPS!).
>+
>+        * BigIntBench/big-int-cse.js: Added.
>+        * BigIntBench/big-int-global-cse.js: Added.
>+        * BigIntBench/big-int-licm.js: Added.
>+
> 2018-12-13  Caio Lima  <ticaiolima@gmail.com>
> 
>         [BigInt] Add ValueDiv into DFG

Actions: View | Formatted Diff | Diff

Attachments on bug 192723: 357436 | 357805