Changeset 243670 in webkit


Ignore:
Timestamp:
Mar 29, 2019 5:21:38 PM (5 years ago)
Author:
rmorisset@apple.com
Message:

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):

Location:
trunk/Source/JavaScriptCore
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r243667 r243670  
     12019-03-29  Robin Morisset  <rmorisset@apple.com>
     2
     3        B3ReduceStrength should know that Mul distributes over Add and Sub
     4        https://bugs.webkit.org/show_bug.cgi?id=196325
     5
     6        Reviewed by Michael Saboff.
     7
     8        In this patch I add the following patterns to B3ReduceStrength:
     9        - Turn this: Integer Neg(Mul(value, c))
     10          Into this: Mul(value, -c), as long as -c does not overflow
     11        - Turn these: Integer Mul(value, Neg(otherValue)) and Integer Mul(Neg(value), otherValue)
     12          Into this: Neg(Mul(value, otherValue))
     13        - For Op==Add or Sub, turn any of these:
     14             Op(Mul(x1, x2), Mul(x1, x3))
     15             Op(Mul(x2, x1), Mul(x1, x3))
     16             Op(Mul(x1, x2), Mul(x3, x1))
     17             Op(Mul(x2, x1), Mul(x3, x1))
     18          Into this: Mul(x1, Op(x2, x3))
     19
     20        Also includes a trivial change: a similar reduction for the distributivity of BitAnd over BitOr/BitXor now
     21        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.
     22
     23        * b3/B3ReduceStrength.cpp:
     24        * b3/testb3.cpp:
     25        (JSC::B3::testAddMulMulArgs):
     26        (JSC::B3::testMulArgNegArg):
     27        (JSC::B3::testMulNegArgArg):
     28        (JSC::B3::testNegMulArgImm):
     29        (JSC::B3::testSubMulMulArgs):
     30        (JSC::B3::run):
     31
    1322019-03-29  Yusuke Suzuki  <ysuzuki@apple.com>
    233

  • trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp

    r243065 r243670  
    603603                    break;
    604604                }
     605
     606                if (handleMulDistributivity())
     607                    break;
    605608            }
    606609
    … …  
    645648                    break;
    646649                }
     650
     651                if (handleMulDistributivity())
     652                    break;
    647653            }
    648654
    … …  
    663669                break;
    664670            }
    665            
    666             // Turn this: Integer Neg(Sub(value, otherValue))
    667             // Into this: Sub(otherValue, value)
    668             if (m_value->isInteger() && m_value->child(0)->opcode() == Sub) {
    669                 replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(0)->child(1), m_value->child(0)->child(0));
    670                 break;
    671             }
     671
     672            if (m_value->isInteger()) {
     673                // Turn this: Integer Neg(Sub(value, otherValue))
     674                // Into this: Sub(otherValue, value)
     675                if (m_value->child(0)->opcode() == Sub) {
     676                    replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(0)->child(1), m_value->child(0)->child(0));
     677                    break;
     678                }
     679
     680                // Turn this: Integer Neg(Mul(value, c))
     681                // Into this: Mul(value, -c), as long as -c does not overflow
     682                if (m_value->child(0)->opcode() == Mul && m_value->child(0)->child(1)->hasInt()) {
     683                    int64_t factor = m_value->child(0)->child(1)->asInt();
     684                    if (m_value->type() == Int32 && factor != std::numeric_limits<int32_t>::min()) {
     685                        Value* newFactor = m_insertionSet.insert<Const32Value>(m_index, m_value->child(0)->child(1)->origin(), -factor);
     686                        replaceWithNew<Value>(Mul, m_value->origin(), m_value->child(0)->child(0), newFactor);
     687                    } else if (m_value->type() == Int64 && factor != std::numeric_limits<int64_t>::min()) {
     688                        Value* newFactor = m_insertionSet.insert<Const64Value>(m_index, m_value->child(0)->child(1)->origin(), -factor);
     689                        replaceWithNew<Value>(Mul, m_value->origin(), m_value->child(0)->child(0), newFactor);
     690                    }
     691                }
     692            }
     693
    672694
    673695            break;
    … …  
    703725
    704726                // Turn this: Mul(value, -1)
    705                 // Into this: Sub(0, value)
     727                // Into this: Neg(value)
    706728                if (factor == -1) {
    707                     replaceWithNewValue(
    708                         m_proc.add<Value>(
    709                             Sub, m_value->origin(),
    710                             m_insertionSet.insertIntConstant(m_index, m_value, 0),
    711                             m_value->child(0)));
     729                    replaceWithNew<Value>(Neg, m_value->origin(), m_value->child(0));
    712730                    break;
    713731                }
    … …  
    731749                if (factor == 1) {
    732750                    replaceWithIdentity(m_value->child(0));
     751                    break;
     752                }
     753            }
     754
     755            if (m_value->isInteger()) {
     756                // Turn this: Integer Mul(value, Neg(otherValue))
     757                // Into this: Neg(Mul(value, otherValue))
     758                if (m_value->child(1)->opcode() == Neg) {
     759                    Value* newMul = m_insertionSet.insert<Value>(m_index, Mul, m_value->origin(), m_value->child(0), m_value->child(1)->child(0));
     760                    replaceWithNew<Value>(Neg, m_value->origin(), newMul);
     761                    break;
     762                }
     763                // Turn this: Integer Mul(Neg(value), otherValue)
     764                // Into this: Neg(Mul(value, value2))
     765                if (m_value->child(0)->opcode() == Neg) {
     766                    Value* newMul = m_insertionSet.insert<Value>(m_index, Mul, m_value->origin(), m_value->child(0)->child(0), m_value->child(1));
     767                    replaceWithNew<Value>(Neg, m_value->origin(), newMul);
    733768                    break;
    734769                }
    … …  
    22972332    }
    22982333
     2334    // For Op==Add or Sub, turn any of these:
     2335    //      Op(Mul(x1, x2), Mul(x1, x3))
     2336    //      Op(Mul(x2, x1), Mul(x1, x3))
     2337    //      Op(Mul(x1, x2), Mul(x3, x1))
     2338    //      Op(Mul(x2, x1), Mul(x3, x1))
     2339    // Into this: Mul(x1, Op(x2, x3))
     2340    bool handleMulDistributivity()
     2341    {
     2342        ASSERT(m_value->opcode() == Add || m_value->opcode() == Sub);
     2343        Value* x1 = nullptr;
     2344        Value* x2 = nullptr;
     2345        Value* x3 = nullptr;
     2346        if (m_value->child(0)->opcode() == Mul && m_value->child(1)->opcode() == Mul) {
     2347            Value* x1 = nullptr;
     2348            Value* x2 = nullptr;
     2349            Value* x3 = nullptr;
     2350            if (m_value->child(0)->child(0) == m_value->child(1)->child(0)) {
     2351                // Op(Mul(x1, x2), Mul(x1, x3))
     2352                x1 = m_value->child(0)->child(0);
     2353                x2 = m_value->child(0)->child(1);
     2354                x3 = m_value->child(1)->child(1);
     2355            } else if (m_value->child(0)->child(1) == m_value->child(1)->child(0)) {
     2356                // Op(Mul(x2, x1), Mul(x1, x3))
     2357                x1 = m_value->child(0)->child(1);
     2358                x2 = m_value->child(0)->child(0);
     2359                x3 = m_value->child(1)->child(1);
     2360            } else if (m_value->child(0)->child(0) == m_value->child(1)->child(1)) {
     2361                // Op(Mul(x1, x2), Mul(x3, x1))
     2362                x1 = m_value->child(0)->child(0);
     2363                x2 = m_value->child(0)->child(1);
     2364                x3 = m_value->child(1)->child(0);
     2365            } else if (m_value->child(0)->child(1) == m_value->child(1)->child(1)) {
     2366                // Op(Mul(x2, x1), Mul(x3, x1))
     2367                x1 = m_value->child(0)->child(1);
     2368                x2 = m_value->child(0)->child(0);
     2369                x3 = m_value->child(1)->child(0);
     2370            }
     2371        }
     2372        if (x1 != nullptr) {
     2373            ASSERT(x2 != nullptr && x3 != nullptr);
     2374            Value* newOp = m_insertionSet.insert<Value>(m_index, m_value->opcode(), m_value->origin(), x2, x3);
     2375            replaceWithNew<Value>(Mul, m_value->origin(), x1, newOp);
     2376            return true;
     2377        }
     2378        return false;
     2379    }
     2380
    22992381    // For Op==BitOr or BitXor, turn any of these:
    23002382    //      Op(BitAnd(x1, x2), BitAnd(x1, x3))
    … …  
    23552437            ASSERT(x2 != nullptr && x3 != nullptr);
    23562438            Value* bitOp = m_insertionSet.insert<Value>(m_index, m_value->opcode(), m_value->origin(), x2, x3);
    2357             replaceWithNew<Value>(BitAnd, m_value->origin(), bitOp, x1);
     2439            replaceWithNew<Value>(BitAnd, m_value->origin(), x1, bitOp);
    23582440            return true;
    23592441        }

  • trunk/Source/JavaScriptCore/b3/testb3.cpp

    r243639 r243670  
    892892}
    893893
     894void testAddMulMulArgs(int64_t a, int64_t b, int64_t c)
     895{
     896    // We want to check every possible ordering of arguments (to properly check every path in B3ReduceStrength):
     897    // ((a * b) + (a * c))
     898    // ((a * b) + (c * a))
     899    // ((b * a) + (a * c))
     900    // ((b * a) + (c * a))
     901    for (int i = 0; i < 4; ++i) {
     902        Procedure proc;
     903        BasicBlock* root = proc.addBlock();
     904        Value* argA = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
     905        Value* argB = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
     906        Value* argC = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR2);
     907        Value* mulAB = i & 2 ? root->appendNew<Value>(proc, Mul, Origin(), argA, argB)
     908            : root->appendNew<Value>(proc, Mul, Origin(), argB, argA);
     909        Value* mulAC = i & 1 ? root->appendNew<Value>(proc, Mul, Origin(), argA, argC)
     910            : root->appendNew<Value>(proc, Mul, Origin(), argC, argA);
     911        root->appendNew<Value>(proc, Return, Origin(),
     912            root->appendNew<Value>(proc, Add, Origin(),
     913                mulAB,
     914                mulAC));
     915
     916        CHECK_EQ(compileAndRun<int64_t>(proc, a, b, c), ((a * b) + (a * c)));
     917    }
     918}
     919
    894920void testMulArg(int a)
    895921{
    … …  
    962988
    963989    CHECK(compileAndRun<int>(proc, a, b) == a * b);
     990}
     991
     992void testMulArgNegArg(int a, int b)
     993{
     994    Procedure proc;
     995    BasicBlock* root = proc.addBlock();
     996    Value* argA = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
     997    Value* argB = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
     998    Value* negB = root->appendNew<Value>(proc, Neg, Origin(), argB);
     999    Value* result = root->appendNew<Value>(proc, Mul, Origin(), argA, negB);
     1000    root->appendNew<Value>(proc, Return, Origin(), result);
     1001
     1002    CHECK(compileAndRun<int>(proc, a, b) == a * (-b));
     1003}
     1004
     1005void testMulNegArgArg(int a, int b)
     1006{
     1007    Procedure proc;
     1008    BasicBlock* root = proc.addBlock();
     1009    Value* argA = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
     1010    Value* argB = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
     1011    Value* negA = root->appendNew<Value>(proc, Neg, Origin(), argA);
     1012    Value* result = root->appendNew<Value>(proc, Mul, Origin(), negA, argB);
     1013    root->appendNew<Value>(proc, Return, Origin(), result);
     1014
     1015    CHECK(compileAndRun<int>(proc, a, b) == (-a) * b);
    9641016}
    9651017
    … …  
    21792231    root->appendNewControlValue(proc, Return, Origin(), negArgumentMinusOne);
    21802232    CHECK(compileAndRun<int>(proc, a) == -a - 1);
     2233}
     2234
     2235void testNegMulArgImm(int64_t a, int64_t b)
     2236{
     2237    Procedure proc;
     2238    BasicBlock* root = proc.addBlock();
     2239    Value* argument = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
     2240    Value* constant = root->appendNew<Const64Value>(proc, Origin(), b);
     2241    Value* mul = root->appendNew<Value>(proc, Mul, Origin(), argument, constant);
     2242    Value* result = root->appendNew<Value>(proc, Neg, Origin(), mul);
     2243    root->appendNew<Value>(proc, Return, Origin(), result);
     2244
     2245    CHECK(compileAndRun<int64_t>(proc, a) == -(a * b));
     2246}
     2247
     2248void testSubMulMulArgs(int64_t a, int64_t b, int64_t c)
     2249{
     2250    // We want to check every possible ordering of arguments (to properly check every path in B3ReduceStrength):
     2251    // ((a * b) - (a * c))
     2252    // ((a * b) - (c * a))
     2253    // ((b * a) - (a * c))
     2254    // ((b * a) - (c * a))
     2255    for (int i = 0; i < 4; ++i) {
     2256        Procedure proc;
     2257        BasicBlock* root = proc.addBlock();
     2258        Value* argA = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
     2259        Value* argB = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
     2260        Value* argC = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR2);
     2261        Value* mulAB = i & 2 ? root->appendNew<Value>(proc, Mul, Origin(), argA, argB)
     2262            : root->appendNew<Value>(proc, Mul, Origin(), argB, argA);
     2263        Value* mulAC = i & 1 ? root->appendNew<Value>(proc, Mul, Origin(), argA, argC)
     2264            : root->appendNew<Value>(proc, Mul, Origin(), argC, argA);
     2265        root->appendNew<Value>(proc, Return, Origin(),
     2266            root->appendNew<Value>(proc, Sub, Origin(),
     2267                mulAB,
     2268                mulAC));
     2269
     2270        CHECK_EQ(compileAndRun<int64_t>(proc, a, b, c), ((a * b) - (a * c)));
     2271    }
    21812272}
    21822273
    … …  
    1698017071    RUN(testAddArgZeroImmZDef());
    1698117072    RUN(testAddLoadTwice());
     17073    RUN_TERNARY(testAddMulMulArgs, int64Operands(), int64Operands(), int64Operands());
    1698217074
    1698317075    RUN(testAddArgDouble(M_PI));
    … …  
    1706417156    RUN(testMulNegArgs32());
    1706517157
     17158    RUN_BINARY(testMulArgNegArg, int64Operands(), int64Operands())
     17159    RUN_BINARY(testMulNegArgArg, int64Operands(), int64Operands())
    1706617160    RUN_UNARY(testMulArgDouble, floatingPointOperands<double>());
    1706717161    RUN_BINARY(testMulArgsDouble, floatingPointOperands<double>(), floatingPointOperands<double>());
    … …  
    1714817242    RUN_BINARY(testNegSub, int32Operands(), int32Operands());
    1714917243    RUN_UNARY(testNegValueSubOne, int32Operands());
     17244    RUN_BINARY(testNegMulArgImm, int64Operands(), int64Operands());
     17245    RUN_TERNARY(testSubMulMulArgs, int64Operands(), int64Operands(), int64Operands());
    1715017246
    1715117247    RUN(testSubArgs32(1, 1));
Note: See TracChangeset for help on using the changeset viewer.