Changeset 195882 in webkit


Ignore:
Timestamp:
Jan 29, 2016 9:14:23 PM (8 years ago)
Author:
fpizlo@apple.com
Message:

B3 should reduce Mod(value, constant) to Div and Mul so that our Div optimizations can do things
https://bugs.webkit.org/show_bug.cgi?id=153693

Reviewed by Saam Barati.

The most efficient way to handle Mod(value, constant) is to reduce it to
Sub(value, Mul(Div(value, constant), constant)) and then let the Div optimizations do their
thing.

In the future we could add special handling of Mod(value, 1 << constant), but it's not
obvious that this would produce better code than reducing through Div, if we also make sure
that we have great optimizations for Mul and Div.

  • b3/B3ReduceStrength.cpp:
Location:
trunk/Source/JavaScriptCore
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/ChangeLog

    r195878 r195882  
     12016-01-29  Filip Pizlo  <fpizlo@apple.com>
     2
     3        B3 should reduce Mod(value, constant) to Div and Mul so that our Div optimizations can do things
     4        https://bugs.webkit.org/show_bug.cgi?id=153693
     5
     6        Reviewed by Saam Barati.
     7
     8        The most efficient way to handle Mod(value, constant) is to reduce it to
     9        Sub(value, Mul(Div(value, constant), constant)) and then let the Div optimizations do their
     10        thing.
     11
     12        In the future we could add special handling of Mod(value, 1 << constant), but it's not
     13        obvious that this would produce better code than reducing through Div, if we also make sure
     14        that we have great optimizations for Mul and Div.
     15
     16        * b3/B3ReduceStrength.cpp:
     17
    1182016-01-29  Keith Miller  <keith_miller@apple.com>
    219
  • trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp

    r195728 r195882  
    663663                    // are allowed to do whatever we want.
    664664                    m_value->replaceWithIdentity(m_value->child(1));
    665                     m_changed = true;
    666665                    break;
    667666
     
    670669                    // Into this: value
    671670                    m_value->replaceWithIdentity(m_value->child(0));
    672                     m_changed = true;
    673671                    break;
    674672
     
    723721                                m_insertionSet.insert<Const32Value>(
    724722                                    m_index, m_value->origin(), 31))));
    725                     m_changed = true;
    726                     break;
    727                 }
    728 
    729                 if (m_value->opcode() != ChillDiv && m_value->opcode() != Div)
    730                     break;
     723                    break;
     724                }
     725
     726                m_changed = true;
     727                break;
    731728            }
    732729            break;
     
    738735            // Note that this uses ChillMod semantics.
    739736            replaceWithNewValue(m_value->child(0)->modConstant(m_proc, m_value->child(1)));
     737
     738            // Modulo by constant is more efficient if we turn it into Div, and then let Div get
     739            // optimized.
     740            if (m_value->child(1)->hasInt()) {
     741                switch (m_value->child(1)->asInt()) {
     742                case 0:
     743                    // Turn this: Mod(value, 0)
     744                    // Into this: 0
     745                    // This is correct according to ChillMod semantics.
     746                    m_value->replaceWithIdentity(m_value->child(1));
     747                    break;
     748
     749                default:
     750                    // Turn this: Mod(N, D)
     751                    // Into this: Sub(N, Mul(Div(N, D), D))
     752                    //
     753                    // This is a speed-up because we use our existing Div optimizations.
     754                    //
     755                    // Here's an easier way to look at it:
     756                    //     N % D = N - N / D * D
     757                    //
     758                    // Note that this does not work for D = 0 and ChillMod. The expected result is 0.
     759                    // That's why we have a special-case above.
     760                    //     X % 0 = X - X / 0 * 0 = X     (should be 0)
     761                    //
     762                    // This does work for the D = -1 special case.
     763                    //     -2^31 % -1 = -2^31 - -2^31 / -1 * -1
     764                    //                = -2^31 - -2^31 * -1
     765                    //                = -2^31 - -2^31
     766                    //                = 0
     767
     768                    Opcode divOpcode;
     769                    switch (m_value->opcode()) {
     770                    case Mod:
     771                        divOpcode = Div;
     772                        break;
     773                    case ChillMod:
     774                        divOpcode = ChillDiv;
     775                        break;
     776                    default:
     777                        divOpcode = Oops;
     778                        RELEASE_ASSERT_NOT_REACHED();
     779                        break;
     780                    }
     781
     782                    m_value->replaceWithIdentity(
     783                        m_insertionSet.insert<Value>(
     784                            m_index, Sub, m_value->origin(),
     785                            m_value->child(0),
     786                            m_insertionSet.insert<Value>(
     787                                m_index, Mul, m_value->origin(),
     788                                m_insertionSet.insert<Value>(
     789                                    m_index, divOpcode, m_value->origin(),
     790                                    m_value->child(0), m_value->child(1)),
     791                                m_value->child(1))));
     792                    break;
     793                }
     794               
     795                m_changed = true;
     796                break;
     797            }
     798           
    740799            break;
    741800
Note: See TracChangeset for help on using the changeset viewer.