Attachment 366325 Details for Bug 196325 – Patch

[patch] Patch

patch (text/plain), 15.02 KB, created by Robin Morisset on 2019-03-29 16:36:34 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Robin Morisset

Created: 2019-03-29 16:36:34 PDT

Size: 15.02 KB

patch

obsolete

>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index 580d238ff5e..0167d782ff0 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,31 @@
>+2019-03-27  Robin Morisset  <rmorisset@apple.com>
>+
>+        B3ReduceStrength should know that Mul distributes over Add and Sub
>+        https://bugs.webkit.org/show_bug.cgi?id=196325
>+
>+        Reviewed by Michael Saboff.
>+
>+        In this patch I add the following patterns to B3ReduceStrength:
>+        - Turn this: Integer Neg(Mul(value, c))
>+          Into this: Mul(value, -c), as long as -c does not overflow
>+        - Turn these: Integer Mul(value, Neg(otherValue)) and Integer Mul(Neg(value), otherValue)
>+          Into this: Neg(Mul(value, otherValue))
>+        - For Op==Add or Sub, turn any of these:
>+             Op(Mul(x1, x2), Mul(x1, x3))
>+             Op(Mul(x2, x1), Mul(x1, x3))
>+             Op(Mul(x1, x2), Mul(x3, x1))
>+             Op(Mul(x2, x1), Mul(x3, x1))
>+          Into this: Mul(x1, Op(x2, x3))
>+
>+        Also includes a trivial change: a similar reduction for the distributivity of BitAnd over BitOr/BitXor now
>+        emits the arguments to BitAnd in the other order, to minimize the probability that we'll spend a full fixpoint step just to flip them.
>+
>+        * b3/B3ReduceStrength.cpp:
>+        * b3/testb3.cpp:
>+        (JSC::B3::testAddMulMulArgs):
>+        (JSC::B3::testMulArgNegArg):
>+        (JSC::B3::testMulNegArgArg):
>+        (JSC::B3::testNegMulArgImm):
>+        (JSC::B3::testSubMulMulArgs):
>+        (JSC::B3::run):
>+
> 2019-03-25  Gyuyoung Kim  <gyuyoung.kim@webkit.org>
> 
>         Remove NavigatorContentUtils in WebCore/Modules
>diff --git a/Source/JavaScriptCore/b3/B3ReduceStrength.cpp b/Source/JavaScriptCore/b3/B3ReduceStrength.cpp
>index 0db3ead8048..3cb9d143400 100644
>--- a/Source/JavaScriptCore/b3/B3ReduceStrength.cpp
>+++ b/Source/JavaScriptCore/b3/B3ReduceStrength.cpp
>@@ -602,6 +602,9 @@ private:
>                     replaceWithNew<Value>(BitXor, m_value->origin(), m_value->child(0)->child(1), m_value->child(1));
>                     break;
>                 }
>+
>+                if (handleMulDistributivity())
>+                    break;
>             }
> 
>             break;
>@@ -644,6 +647,9 @@ private:
>                     replaceWithNew<Value>(Add, m_value->origin(), m_value->child(0), m_value->child(1)->child(0));
>                     break;
>                 }
>+
>+                if (handleMulDistributivity())
>+                    break;
>             }
> 
>             break;
>@@ -662,14 +668,30 @@ private:
>                 replaceWithIdentity(m_value->child(0)->child(0));
>                 break;
>             }
>-            
>-            // Turn this: Integer Neg(Sub(value, otherValue))
>-            // Into this: Sub(otherValue, value)
>-            if (m_value->isInteger() && m_value->child(0)->opcode() == Sub) {
>-                replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(0)->child(1), m_value->child(0)->child(0));
>-                break;
>+
>+            if (m_value->isInteger()) {
>+                // Turn this: Integer Neg(Sub(value, otherValue))
>+                // Into this: Sub(otherValue, value)
>+                if (m_value->child(0)->opcode() == Sub) {
>+                    replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(0)->child(1), m_value->child(0)->child(0));
>+                    break;
>+                }
>+
>+                // Turn this: Integer Neg(Mul(value, c))
>+                // Into this: Mul(value, -c), as long as -c does not overflow
>+                if (m_value->child(0)->opcode() == Mul && m_value->child(0)->child(1)->hasInt()) {
>+                    int64_t factor = m_value->child(0)->child(1)->asInt();
>+                    if (m_value->type() == Int32 && factor != std::numeric_limits<int32_t>::min()) {
>+                        Value* newFactor = m_insertionSet.insert<Const32Value>(m_index, m_value->child(0)->child(1)->origin(), -factor);
>+                        replaceWithNew<Value>(Mul, m_value->origin(), m_value->child(0)->child(0), newFactor);
>+                    } else if (m_value->type() == Int64 && factor != std::numeric_limits<int64_t>::min()) {
>+                        Value* newFactor = m_insertionSet.insert<Const64Value>(m_index, m_value->child(0)->child(1)->origin(), -factor);
>+                        replaceWithNew<Value>(Mul, m_value->origin(), m_value->child(0)->child(0), newFactor);
>+                    }
>+                }
>             }
> 
>+
>             break;
> 
>         case Mul:
>@@ -702,13 +724,9 @@ private:
>                 }
> 
>                 // Turn this: Mul(value, -1)
>-                // Into this: Sub(0, value)
>+                // Into this: Neg(value)
>                 if (factor == -1) {
>-                    replaceWithNewValue(
>-                        m_proc.add<Value>(
>-                            Sub, m_value->origin(),
>-                            m_insertionSet.insertIntConstant(m_index, m_value, 0),
>-                            m_value->child(0)));
>+                    replaceWithNew<Value>(Neg, m_value->origin(), m_value->child(0));
>                     break;
>                 }
>                 
>@@ -734,6 +752,23 @@ private:
>                 }
>             }
> 
>+            if (m_value->isInteger()) {
>+                // Turn this: Integer Mul(value, Neg(otherValue))
>+                // Into this: Neg(Mul(value, otherValue))
>+                if (m_value->child(1)->opcode() == Neg) {
>+                    Value* newMul = m_insertionSet.insert<Value>(m_index, Mul, m_value->origin(), m_value->child(0), m_value->child(1)->child(0));
>+                    replaceWithNew<Value>(Neg, m_value->origin(), newMul);
>+                    break;
>+                }
>+                // Turn this: Integer Mul(Neg(value), otherValue)
>+                // Into this: Neg(Mul(value, value2))
>+                if (m_value->child(0)->opcode() == Neg) {
>+                    Value* newMul = m_insertionSet.insert<Value>(m_index, Mul, m_value->origin(), m_value->child(0)->child(0), m_value->child(1));
>+                    replaceWithNew<Value>(Neg, m_value->origin(), newMul);
>+                    break;
>+                }
>+            }
>+
>             break;
> 
>         case Div:
>@@ -2296,6 +2331,53 @@ private:
>         }
>     }
> 
>+    // For Op==Add or Sub, turn any of these:
>+    //      Op(Mul(x1, x2), Mul(x1, x3))
>+    //      Op(Mul(x2, x1), Mul(x1, x3))
>+    //      Op(Mul(x1, x2), Mul(x3, x1))
>+    //      Op(Mul(x2, x1), Mul(x3, x1))
>+    // Into this: Mul(x1, Op(x2, x3))
>+    bool handleMulDistributivity()
>+    {
>+        ASSERT(m_value->opcode() == Add || m_value->opcode() == Sub);
>+        Value* x1 = nullptr;
>+        Value* x2 = nullptr;
>+        Value* x3 = nullptr;
>+        if (m_value->child(0)->opcode() == Mul && m_value->child(1)->opcode() == Mul) {
>+            Value* x1 = nullptr;
>+            Value* x2 = nullptr;
>+            Value* x3 = nullptr;
>+            if (m_value->child(0)->child(0) == m_value->child(1)->child(0)) {
>+                // Op(Mul(x1, x2), Mul(x1, x3))
>+                x1 = m_value->child(0)->child(0);
>+                x2 = m_value->child(0)->child(1);
>+                x3 = m_value->child(1)->child(1);
>+            } else if (m_value->child(0)->child(1) == m_value->child(1)->child(0)) {
>+                // Op(Mul(x2, x1), Mul(x1, x3))
>+                x1 = m_value->child(0)->child(1);
>+                x2 = m_value->child(0)->child(0);
>+                x3 = m_value->child(1)->child(1);
>+            } else if (m_value->child(0)->child(0) == m_value->child(1)->child(1)) {
>+                // Op(Mul(x1, x2), Mul(x3, x1))
>+                x1 = m_value->child(0)->child(0);
>+                x2 = m_value->child(0)->child(1);
>+                x3 = m_value->child(1)->child(0);
>+            } else if (m_value->child(0)->child(1) == m_value->child(1)->child(1)) {
>+                // Op(Mul(x2, x1), Mul(x3, x1))
>+                x1 = m_value->child(0)->child(1);
>+                x2 = m_value->child(0)->child(0);
>+                x3 = m_value->child(1)->child(0);
>+            }
>+        }
>+        if (x1 != nullptr) {
>+            ASSERT(x2 != nullptr && x3 != nullptr);
>+            Value* newOp = m_insertionSet.insert<Value>(m_index, m_value->opcode(), m_value->origin(), x2, x3);
>+            replaceWithNew<Value>(Mul, m_value->origin(), x1, newOp);
>+            return true;
>+        }
>+        return false;
>+    }
>+
>     // For Op==BitOr or BitXor, turn any of these:
>     //      Op(BitAnd(x1, x2), BitAnd(x1, x3))
>     //      Op(BitAnd(x2, x1), BitAnd(x1, x3))
>@@ -2354,7 +2436,7 @@ private:
>         if (x1 != nullptr) {
>             ASSERT(x2 != nullptr && x3 != nullptr);
>             Value* bitOp = m_insertionSet.insert<Value>(m_index, m_value->opcode(), m_value->origin(), x2, x3);
>-            replaceWithNew<Value>(BitAnd, m_value->origin(), bitOp, x1);
>+            replaceWithNew<Value>(BitAnd, m_value->origin(), x1, bitOp);
>             return true;
>         }
>         return false;
>diff --git a/Source/JavaScriptCore/b3/testb3.cpp b/Source/JavaScriptCore/b3/testb3.cpp
>index 0e371bc0181..346eaf74811 100644
>--- a/Source/JavaScriptCore/b3/testb3.cpp
>+++ b/Source/JavaScriptCore/b3/testb3.cpp
>@@ -891,6 +891,32 @@ void testAddArgsFloatWithEffectfulDoubleConversion(float a, float b)
>     CHECK(isIdentical(effect, static_cast<double>(a) + static_cast<double>(b)));
> }
> 
>+void testAddMulMulArgs(int64_t a, int64_t b, int64_t c)
>+{
>+    // We want to check every possible ordering of arguments (to properly check every path in B3ReduceStrength):
>+    // ((a * b) + (a * c))
>+    // ((a * b) + (c * a))
>+    // ((b * a) + (a * c))
>+    // ((b * a) + (c * a))
>+    for (int i = 0; i < 4; ++i) {
>+        Procedure proc;
>+        BasicBlock* root = proc.addBlock();
>+        Value* argA = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
>+        Value* argB = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
>+        Value* argC = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR2);
>+        Value* mulAB = i & 2 ? root->appendNew<Value>(proc, Mul, Origin(), argA, argB)
>+            : root->appendNew<Value>(proc, Mul, Origin(), argB, argA);
>+        Value* mulAC = i & 1 ? root->appendNew<Value>(proc, Mul, Origin(), argA, argC)
>+            : root->appendNew<Value>(proc, Mul, Origin(), argC, argA);
>+        root->appendNew<Value>(proc, Return, Origin(),
>+            root->appendNew<Value>(proc, Add, Origin(),
>+                mulAB,
>+                mulAC));
>+
>+        CHECK_EQ(compileAndRun<int64_t>(proc, a, b, c), ((a * b) + (a * c)));
>+    }
>+}
>+
> void testMulArg(int a)
> {
>     Procedure proc;
>@@ -963,6 +989,32 @@ void testMulArgs(int a, int b)
>     CHECK(compileAndRun<int>(proc, a, b) == a * b);
> }
> 
>+void testMulArgNegArg(int a, int b)
>+{
>+    Procedure proc;
>+    BasicBlock* root = proc.addBlock();
>+    Value* argA = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
>+    Value* argB = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
>+    Value* negB = root->appendNew<Value>(proc, Neg, Origin(), argB);
>+    Value* result = root->appendNew<Value>(proc, Mul, Origin(), argA, negB);
>+    root->appendNew<Value>(proc, Return, Origin(), result);
>+
>+    CHECK(compileAndRun<int>(proc, a, b) == a * (-b));
>+}
>+
>+void testMulNegArgArg(int a, int b)
>+{
>+    Procedure proc;
>+    BasicBlock* root = proc.addBlock();
>+    Value* argA = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
>+    Value* argB = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
>+    Value* negA = root->appendNew<Value>(proc, Neg, Origin(), argA);
>+    Value* result = root->appendNew<Value>(proc, Mul, Origin(), negA, argB);
>+    root->appendNew<Value>(proc, Return, Origin(), result);
>+
>+    CHECK(compileAndRun<int>(proc, a, b) == (-a) * b);
>+}
>+
> void testMulArgImm(int64_t a, int64_t b)
> {
>     Procedure proc;
>@@ -2180,6 +2232,45 @@ void testNegValueSubOne32(int a)
>     CHECK(compileAndRun<int>(proc, a) == -a - 1);
> }
> 
>+void testNegMulArgImm(int64_t a, int64_t b)
>+{
>+    Procedure proc;
>+    BasicBlock* root = proc.addBlock();
>+    Value* argument = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
>+    Value* constant = root->appendNew<Const64Value>(proc, Origin(), b);
>+    Value* mul = root->appendNew<Value>(proc, Mul, Origin(), argument, constant);
>+    Value* result = root->appendNew<Value>(proc, Neg, Origin(), mul);
>+    root->appendNew<Value>(proc, Return, Origin(), result);
>+
>+    CHECK(compileAndRun<int64_t>(proc, a) == -(a * b));
>+}
>+
>+void testSubMulMulArgs(int64_t a, int64_t b, int64_t c)
>+{
>+    // We want to check every possible ordering of arguments (to properly check every path in B3ReduceStrength):
>+    // ((a * b) - (a * c))
>+    // ((a * b) - (c * a))
>+    // ((b * a) - (a * c))
>+    // ((b * a) - (c * a))
>+    for (int i = 0; i < 4; ++i) {
>+        Procedure proc;
>+        BasicBlock* root = proc.addBlock();
>+        Value* argA = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
>+        Value* argB = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
>+        Value* argC = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR2);
>+        Value* mulAB = i & 2 ? root->appendNew<Value>(proc, Mul, Origin(), argA, argB)
>+            : root->appendNew<Value>(proc, Mul, Origin(), argB, argA);
>+        Value* mulAC = i & 1 ? root->appendNew<Value>(proc, Mul, Origin(), argA, argC)
>+            : root->appendNew<Value>(proc, Mul, Origin(), argC, argA);
>+        root->appendNew<Value>(proc, Return, Origin(),
>+            root->appendNew<Value>(proc, Sub, Origin(),
>+                mulAB,
>+                mulAC));
>+
>+        CHECK_EQ(compileAndRun<int64_t>(proc, a, b, c), ((a * b) - (a * c)));
>+    }
>+}
>+
> void testSubArgDouble(double a)
> {
>     Procedure proc;
>@@ -16934,6 +17025,7 @@ void run(const char* filter)
>     RUN_BINARY(testAddNeg2, int32Operands(), int32Operands());
>     RUN(testAddArgZeroImmZDef());
>     RUN(testAddLoadTwice());
>+    RUN_TERNARY(testAddMulMulArgs, int64Operands(), int64Operands(), int64Operands());
> 
>     RUN(testAddArgDouble(M_PI));
>     RUN(testAddArgsDouble(M_PI, 1));
>@@ -17018,6 +17110,8 @@ void run(const char* filter)
>     RUN(testMulNegArgs());
>     RUN(testMulNegArgs32());
> 
>+    RUN_BINARY(testMulArgNegArg, int64Operands(), int64Operands())
>+    RUN_BINARY(testMulNegArgArg, int64Operands(), int64Operands())
>     RUN_UNARY(testMulArgDouble, floatingPointOperands<double>());
>     RUN_BINARY(testMulArgsDouble, floatingPointOperands<double>(), floatingPointOperands<double>());
>     RUN_BINARY(testMulArgImmDouble, floatingPointOperands<double>(), floatingPointOperands<double>());
>@@ -17102,6 +17196,8 @@ void run(const char* filter)
>     RUN_BINARY(testSubNeg, int32Operands(), int32Operands());
>     RUN_BINARY(testNegSub, int32Operands(), int32Operands());
>     RUN_UNARY(testNegValueSubOne, int32Operands());
>+    RUN_BINARY(testNegMulArgImm, int64Operands(), int64Operands());
>+    RUN_TERNARY(testSubMulMulArgs, int64Operands(), int64Operands(), int64Operands());
> 
>     RUN(testSubArgs32(1, 1));
>     RUN(testSubArgs32(1, 2));

Flags:

commit-queue: commit-queue-

Actions: View | Formatted Diff | Diff

Attachments on bug 196325: 366127 | 366325 | 366326 | 366767