B3 should reduce (integer) Sub(Neg(x), y) to Neg(Add(x, y))
authorjustin_michaud@apple.com <justin_michaud@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 12 Jul 2019 17:11:31 +0000 (17:11 +0000)
committerjustin_michaud@apple.com <justin_michaud@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 12 Jul 2019 17:11:31 +0000 (17:11 +0000)
https://bugs.webkit.org/show_bug.cgi?id=196371

Reviewed by Keith Miller.

JSTests:

* microbenchmarks/mul-immediate-sub.js: Added.
(doTest):

Source/JavaScriptCore:

Adding these strength reductions gives 2x a (x86) and 3x (arm64) performance improvement
on the microbenchmark.

* b3/B3ReduceStrength.cpp:
* b3/testb3.cpp:
(JSC::B3::testSubSub):
(JSC::B3::testSubSub2):
(JSC::B3::testSubAdd):
(JSC::B3::testSubFirstNeg):
(JSC::B3::run):

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

JSTests/ChangeLog
JSTests/microbenchmarks/mul-immediate-sub.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3ReduceStrength.cpp
Source/JavaScriptCore/b3/testb3.cpp

index f73390e..1c97291 100644 (file)
@@ -1,3 +1,13 @@
+2019-07-12  Justin Michaud  <justin_michaud@apple.com>
+
+        B3 should reduce (integer) Sub(Neg(x), y) to Neg(Add(x, y))
+        https://bugs.webkit.org/show_bug.cgi?id=196371
+
+        Reviewed by Keith Miller.
+
+        * microbenchmarks/mul-immediate-sub.js: Added.
+        (doTest):
+
 2019-07-12  Caio Lima  <ticaiolima@gmail.com>
 
         [BigInt] Add ValueBitLShift into DFG
diff --git a/JSTests/microbenchmarks/mul-immediate-sub.js b/JSTests/microbenchmarks/mul-immediate-sub.js
new file mode 100644 (file)
index 0000000..088ad76
--- /dev/null
@@ -0,0 +1,13 @@
+function doTest(max) {
+    let sum = 0
+    for (let i=0; i<max; ++i) {
+        sum = (((((((((((sum|0) + ((i*256)|0))|0) - ((i*9)|0))|0) - ((i*31)|0))|0) - ((i*67)|0))|0) - ((i*64)|0))|0)
+    }
+    return sum
+}
+noInline(doTest);
+
+for (let i=0; i<100000; ++i) doTest(10000)
+
+if (doTest(1000) != 42457500)
+    throw "Error: bad result: " + doTest(1000);
index 36fcdad..b281ca7 100644 (file)
@@ -1,3 +1,21 @@
+2019-07-12  Justin Michaud  <justin_michaud@apple.com>
+
+        B3 should reduce (integer) Sub(Neg(x), y) to Neg(Add(x, y))
+        https://bugs.webkit.org/show_bug.cgi?id=196371
+
+        Reviewed by Keith Miller.
+
+        Adding these strength reductions gives 2x a (x86) and 3x (arm64) performance improvement
+        on the microbenchmark.
+
+        * b3/B3ReduceStrength.cpp:
+        * b3/testb3.cpp:
+        (JSC::B3::testSubSub):
+        (JSC::B3::testSubSub2):
+        (JSC::B3::testSubAdd):
+        (JSC::B3::testSubFirstNeg):
+        (JSC::B3::run):
+
 2019-07-12  Caio Lima  <ticaiolima@gmail.com>
 
         [BigInt] Add ValueBitLShift into DFG
index 102478f..9dc2633 100644 (file)
@@ -651,6 +651,39 @@ private:
                     break;
                 }
 
+                // Turn this: Sub(Neg(value), value2)
+                // Into this: Neg(Add(value, value2))
+                if (m_value->child(0)->opcode() == Neg) {
+                    replaceWithNew<Value>(Neg, m_value->origin(),
+                        m_insertionSet.insert<Value>(m_index, Add, m_value->origin(), m_value->child(0)->child(0), m_value->child(1)));
+                    break;
+                }
+
+                // Turn this: Sub(Sub(a, b), c)
+                // Into this: Sub(a, Add(b, c))
+                if (m_value->child(0)->opcode() == Sub) {
+                    replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(0)->child(0),
+                        m_insertionSet.insert<Value>(m_index, Add, m_value->origin(), m_value->child(0)->child(1), m_value->child(1)));
+                    break;
+                }
+
+                // Turn this: Sub(a, Sub(b, c))
+                // Into this: Add(Sub(a, b), c)
+                if (m_value->child(1)->opcode() == Sub) {
+                    replaceWithNew<Value>(Add, m_value->origin(),
+                        m_insertionSet.insert<Value>(m_index, Sub, m_value->origin(), m_value->child(0), m_value->child(1)->child(0)),
+                        m_value->child(1)->child(1));
+                    break;
+                }
+
+                // Turn this: Sub(Add(a, b), c)
+                // Into this: Add(a, Sub(b, c))
+                if (m_value->child(0)->opcode() == Add) {
+                    replaceWithNew<Value>(Add, m_value->origin(), m_value->child(0)->child(0),
+                        m_insertionSet.insert<Value>(m_index, Sub, m_value->origin(), m_value->child(0)->child(1), m_value->child(1)));
+                    break;
+                }
+
                 if (handleMulDistributivity())
                     break;
             }
index c9fd18e..e841bb8 100644 (file)
@@ -2190,6 +2190,69 @@ void testNegValueSubOne(int a)
     CHECK(compileAndRun<int>(proc, a) == -a - 1);
 }
 
+void testSubSub(int a, int b, int c)
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+    root->appendNewControlValue(
+        proc, Return, Origin(),
+        root->appendNew<Value>(
+            proc, Sub, Origin(),
+            root->appendNew<Value>(proc, Sub, Origin(),
+                root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+                root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1)),
+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR2)));
+
+    CHECK(compileAndRun<int>(proc, a, b, c) == (a-b)-c);
+}
+
+void testSubSub2(int a, int b, int c)
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+    root->appendNewControlValue(
+        proc, Return, Origin(),
+        root->appendNew<Value>(
+            proc, Sub, Origin(),
+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+            root->appendNew<Value>(proc, Sub, Origin(),
+                root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1),
+                root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR2))));
+
+    CHECK(compileAndRun<int>(proc, a, b, c) == a-(b-c));
+}
+
+void testSubAdd(int a, int b, int c)
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+    root->appendNewControlValue(
+        proc, Return, Origin(),
+        root->appendNew<Value>(
+            proc, Sub, Origin(),
+            root->appendNew<Value>(proc, Add, Origin(),
+                root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+                root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1)),
+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR2)));
+
+    CHECK(compileAndRun<int>(proc, a, b, c) == (a+b)-c);
+}
+
+void testSubFirstNeg(int a, int b)
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+    root->appendNewControlValue(
+        proc, Return, Origin(),
+        root->appendNew<Value>(
+            proc, Sub, Origin(),
+            root->appendNew<Value>(proc, Neg, Origin(),
+                root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0)),
+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1)));
+
+    CHECK(compileAndRun<int>(proc, a, b) == (-a)-b);
+}
+
 void testSubImmArg(int a, int b)
 {
     Procedure proc;
@@ -17457,6 +17520,11 @@ void run(const char* filter)
     RUN_BINARY(testNegMulArgImm, int64Operands(), int64Operands());
     RUN_TERNARY(testSubMulMulArgs, int64Operands(), int64Operands(), int64Operands());
 
+    RUN_TERNARY(testSubSub, int32Operands(), int32Operands(), int32Operands());
+    RUN_TERNARY(testSubSub2, int32Operands(), int32Operands(), int32Operands());
+    RUN_TERNARY(testSubAdd, int32Operands(), int32Operands(), int32Operands());
+    RUN_BINARY(testSubFirstNeg, int32Operands(), int32Operands());
+
     RUN(testSubArgs32(1, 1));
     RUN(testSubArgs32(1, 2));
     RUN(testSubArgs32(13, -42));