B3 should reduce Mod(value, constant) to Div and Mul so that our Div optimizations...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 30 Jan 2016 05:14:23 +0000 (05:14 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 30 Jan 2016 05:14:23 +0000 (05:14 +0000)
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:

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3ReduceStrength.cpp

index 514d6c3..64179ba 100644 (file)
@@ -1,3 +1,20 @@
+2016-01-29  Filip Pizlo  <fpizlo@apple.com>
+
+        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:
+
 2016-01-29  Keith Miller  <keith_miller@apple.com>
 
         Array.prototype native functions should use Symbol.species to construct the result
index ed629e4..ecaaf24 100644 (file)
@@ -662,14 +662,12 @@ private:
                     // We can do this because it's precisely correct for ChillDiv and for Div we
                     // are allowed to do whatever we want.
                     m_value->replaceWithIdentity(m_value->child(1));
-                    m_changed = true;
                     break;
 
                 case 1:
                     // Turn this: Div(value, 1)
                     // Into this: value
                     m_value->replaceWithIdentity(m_value->child(0));
-                    m_changed = true;
                     break;
 
                 default:
@@ -722,12 +720,11 @@ private:
                                 m_index, ZShr, m_value->origin(), magicQuotient,
                                 m_insertionSet.insert<Const32Value>(
                                     m_index, m_value->origin(), 31))));
-                    m_changed = true;
                     break;
                 }
 
-                if (m_value->opcode() != ChillDiv && m_value->opcode() != Div)
-                    break;
+                m_changed = true;
+                break;
             }
             break;
 
@@ -737,6 +734,68 @@ private:
             // Into this: constant1 / constant2
             // Note that this uses ChillMod semantics.
             replaceWithNewValue(m_value->child(0)->modConstant(m_proc, m_value->child(1)));
+
+            // Modulo by constant is more efficient if we turn it into Div, and then let Div get
+            // optimized.
+            if (m_value->child(1)->hasInt()) {
+                switch (m_value->child(1)->asInt()) {
+                case 0:
+                    // Turn this: Mod(value, 0)
+                    // Into this: 0
+                    // This is correct according to ChillMod semantics.
+                    m_value->replaceWithIdentity(m_value->child(1));
+                    break;
+
+                default:
+                    // Turn this: Mod(N, D)
+                    // Into this: Sub(N, Mul(Div(N, D), D))
+                    //
+                    // This is a speed-up because we use our existing Div optimizations.
+                    //
+                    // Here's an easier way to look at it:
+                    //     N % D = N - N / D * D
+                    //
+                    // Note that this does not work for D = 0 and ChillMod. The expected result is 0.
+                    // That's why we have a special-case above.
+                    //     X % 0 = X - X / 0 * 0 = X     (should be 0)
+                    //
+                    // This does work for the D = -1 special case.
+                    //     -2^31 % -1 = -2^31 - -2^31 / -1 * -1
+                    //                = -2^31 - -2^31 * -1
+                    //                = -2^31 - -2^31
+                    //                = 0
+
+                    Opcode divOpcode;
+                    switch (m_value->opcode()) {
+                    case Mod:
+                        divOpcode = Div;
+                        break;
+                    case ChillMod:
+                        divOpcode = ChillDiv;
+                        break;
+                    default:
+                        divOpcode = Oops;
+                        RELEASE_ASSERT_NOT_REACHED();
+                        break;
+                    }
+
+                    m_value->replaceWithIdentity(
+                        m_insertionSet.insert<Value>(
+                            m_index, Sub, m_value->origin(),
+                            m_value->child(0),
+                            m_insertionSet.insert<Value>(
+                                m_index, Mul, m_value->origin(),
+                                m_insertionSet.insert<Value>(
+                                    m_index, divOpcode, m_value->origin(),
+                                    m_value->child(0), m_value->child(1)),
+                                m_value->child(1))));
+                    break;
+                }
+                
+                m_changed = true;
+                break;
+            }
+            
             break;
 
         case BitAnd: