B3 should strength-reduce division by a constant
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 23 Jan 2016 03:24:42 +0000 (03:24 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 23 Jan 2016 03:24:42 +0000 (03:24 +0000)
https://bugs.webkit.org/show_bug.cgi?id=153386

Reviewed by Benjamin Poulain.

You can turn a 32-bit division by a constant into a 64-bit multiplication by a constant
plus some shifts. A book called "Hacker's Delight" has a bunch of math about this. The
hard part is finding the constant by which to multiply, and the amount by which to shift.
The book tells you some theroems, but you still have to turn that into code by thinking
deep thoughts. Luckily I was able to avoid that because it turns out that LLVM already
has code for this. It's called APInt::magic(), where APInt is their class for reasoning
about integers.

The code has a compatible license to ours and we have already in the past taken code from
LLVM. So, that's what this patch does. The LLVM code is localized in
B3ComputeDivisionMagic.h. Then reduceStrength() uses that to construct the multiply+shift
sequence.

This is an enormous speed-up on AsmBench-0.9/bigfib.cpp.js. It makes us as fast on that
test as LLVM. It reduces our deficit on AsmBench to 1.5%. Previously it was 4.5%.

* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3ComputeDivisionMagic.h: Added.
(JSC::B3::computeDivisionMagic):
* b3/B3ReduceStrength.cpp:

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/b3/B3ComputeDivisionMagic.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3ReduceStrength.cpp

index 4bf1114..313374b 100644 (file)
@@ -1,3 +1,31 @@
+2016-01-22  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 should strength-reduce division by a constant
+        https://bugs.webkit.org/show_bug.cgi?id=153386
+
+        Reviewed by Benjamin Poulain.
+
+        You can turn a 32-bit division by a constant into a 64-bit multiplication by a constant
+        plus some shifts. A book called "Hacker's Delight" has a bunch of math about this. The
+        hard part is finding the constant by which to multiply, and the amount by which to shift.
+        The book tells you some theroems, but you still have to turn that into code by thinking
+        deep thoughts. Luckily I was able to avoid that because it turns out that LLVM already
+        has code for this. It's called APInt::magic(), where APInt is their class for reasoning
+        about integers.
+
+        The code has a compatible license to ours and we have already in the past taken code from
+        LLVM. So, that's what this patch does. The LLVM code is localized in
+        B3ComputeDivisionMagic.h. Then reduceStrength() uses that to construct the multiply+shift
+        sequence.
+
+        This is an enormous speed-up on AsmBench-0.9/bigfib.cpp.js. It makes us as fast on that
+        test as LLVM. It reduces our deficit on AsmBench to 1.5%. Previously it was 4.5%.
+
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * b3/B3ComputeDivisionMagic.h: Added.
+        (JSC::B3::computeDivisionMagic):
+        * b3/B3ReduceStrength.cpp:
+
 2016-01-22  Saam barati  <sbarati@apple.com>
 
         genericUnwind might overflow the instructions() vector when catching an FTL exception
index 1a46434..bff7715 100644 (file)
                0F8335B71639C1E6001443B5 /* ArrayAllocationProfile.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F8335B41639C1E3001443B5 /* ArrayAllocationProfile.cpp */; };
                0F8335B81639C1EA001443B5 /* ArrayAllocationProfile.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8335B51639C1E3001443B5 /* ArrayAllocationProfile.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F8364B7164B0C110053329A /* DFGBranchDirection.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */; };
+               0F86AE201C5311C5006BE8EC /* B3ComputeDivisionMagic.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F86AE1F1C5311C5006BE8EC /* B3ComputeDivisionMagic.h */; };
                0F885E111849A3BE00F1E3FA /* BytecodeUseDef.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F885E101849A3BE00F1E3FA /* BytecodeUseDef.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F893BDB1936E23C001211F4 /* DFGStructureAbstractValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F893BDA1936E23C001211F4 /* DFGStructureAbstractValue.cpp */; };
                0F898F311B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F898F2F1B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp */; };
                0F8335B41639C1E3001443B5 /* ArrayAllocationProfile.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ArrayAllocationProfile.cpp; sourceTree = "<group>"; };
                0F8335B51639C1E3001443B5 /* ArrayAllocationProfile.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ArrayAllocationProfile.h; sourceTree = "<group>"; };
                0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBranchDirection.h; path = dfg/DFGBranchDirection.h; sourceTree = "<group>"; };
+               0F86AE1F1C5311C5006BE8EC /* B3ComputeDivisionMagic.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ComputeDivisionMagic.h; path = b3/B3ComputeDivisionMagic.h; sourceTree = "<group>"; };
                0F885E101849A3BE00F1E3FA /* BytecodeUseDef.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BytecodeUseDef.h; sourceTree = "<group>"; };
                0F893BDA1936E23C001211F4 /* DFGStructureAbstractValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGStructureAbstractValue.cpp; path = dfg/DFGStructureAbstractValue.cpp; sourceTree = "<group>"; };
                0F898F2F1B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGIntegerRangeOptimizationPhase.cpp; path = dfg/DFGIntegerRangeOptimizationPhase.cpp; sourceTree = "<group>"; };
                                0FEC84C21BDACDAC0080FF74 /* B3Commutativity.h */,
                                0F338DFF1BF0276C0013C88F /* B3Compilation.cpp */,
                                0F338E001BF0276C0013C88F /* B3Compilation.h */,
+                               0F86AE1F1C5311C5006BE8EC /* B3ComputeDivisionMagic.h */,
                                0FEC84C31BDACDAC0080FF74 /* B3Const32Value.cpp */,
                                0FEC84C41BDACDAC0080FF74 /* B3Const32Value.h */,
                                0FEC84C51BDACDAC0080FF74 /* B3Const64Value.cpp */,
                                BC18C4560E16F5CD00B34460 /* Protect.h in Headers */,
                                1474C33B16AA2D950062F01D /* PrototypeMap.h in Headers */,
                                0F5780A218FE1E98001E72D9 /* PureNaN.h in Headers */,
+                               0F86AE201C5311C5006BE8EC /* B3ComputeDivisionMagic.h in Headers */,
                                0F15CD231BA5F9860031FFD3 /* PutByIdFlags.h in Headers */,
                                0F9332A414CA7DD90085F3C6 /* PutByIdStatus.h in Headers */,
                                0F93275F1C21EF7F00CF6564 /* JSObjectInlines.h in Headers */,
diff --git a/Source/JavaScriptCore/b3/B3ComputeDivisionMagic.h b/Source/JavaScriptCore/b3/B3ComputeDivisionMagic.h
new file mode 100644 (file)
index 0000000..7647d97
--- /dev/null
@@ -0,0 +1,161 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ *
+ * This contains code taken from LLVM's APInt class. That code implements finding the magic
+ * numbers for strength-reducing division. The LLVM code on which this code is based was
+ * implemented using "Hacker's Delight", Henry S. Warren, Jr., chapter 10.
+ *
+ * ==============================================================================
+ * LLVM Release License
+ * ==============================================================================
+ * University of Illinois/NCSA
+ * Open Source License
+ * 
+ * Copyright (c) 2003-2014 University of Illinois at Urbana-Champaign.
+ * All rights reserved.
+ * 
+ * Developed by:
+ * 
+ *     LLVM Team
+ * 
+ *     University of Illinois at Urbana-Champaign
+ * 
+ *     http://llvm.org
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining a copy of
+ * this software and associated documentation files (the "Software"), to deal with
+ * the Software without restriction, including without limitation the rights to
+ * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+ * of the Software, and to permit persons to whom the Software is furnished to do
+ * so, subject to the following conditions:
+ * 
+ *     * Redistributions of source code must retain the above copyright notice,
+ *       this list of conditions and the following disclaimers.
+ * 
+ *     * Redistributions in binary form must reproduce the above copyright notice,
+ *       this list of conditions and the following disclaimers in the
+ *       documentation and/or other materials provided with the distribution.
+ * 
+ *     * Neither the names of the LLVM Team, University of Illinois at
+ *       Urbana-Champaign, nor the names of its contributors may be used to
+ *       endorse or promote products derived from this Software without specific
+ *       prior written permission.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
+ * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+ * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
+ * SOFTWARE.
+ */
+
+#ifndef B3ComputeDivisionMagic_h
+#define B3ComputeDivisionMagic_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+template<typename T>
+struct DivisionMagic {
+    T magicMultiplier;
+    unsigned shift;
+};
+
+// This contains code taken from LLVM's APInt::magic(). It's modestly adapted to our style, but
+// not completely, to make it easier to apply their changes in the future.
+template<typename T>
+DivisionMagic<T> computeDivisionMagic(T divisor)
+{
+    T d = divisor;
+    unsigned p;
+    T ad, anc, delta, q1, r1, q2, r2, t;
+    T signedMin = std::numeric_limits<T>::min();
+    DivisionMagic<T> mag;
+    unsigned bitWidth = sizeof(divisor) * 8;
+
+    // This code doesn't like to think of signedness as a type. Instead it likes to think that
+    // operations have signedness. This is how we generally do it in B3 as well. For this reason,
+    // this provides helpers for unsigned operations on the signed type (T).
+    
+    auto zshr = [&] (T value, int amount) -> T {
+        return static_cast<typename std::make_unsigned<T>::type>(value) >> amount;
+    };
+
+    auto udiv = [&] (T left, T right) -> T {
+        return static_cast<T>(static_cast<typename std::make_unsigned<T>::type>(left) / static_cast<typename std::make_unsigned<T>::type>(right));
+    };
+
+    auto urem = [&] (T left, T right) -> T {
+        return static_cast<T>(static_cast<typename std::make_unsigned<T>::type>(left) % static_cast<typename std::make_unsigned<T>::type>(right));
+    };
+
+    auto aboveEqual = [&] (T left, T right) -> bool {
+        return static_cast<typename std::make_unsigned<T>::type>(left) >= static_cast<typename std::make_unsigned<T>::type>(right);
+    };
+
+    auto below = [&] (T left, T right) -> bool {
+        return static_cast<typename std::make_unsigned<T>::type>(left) < static_cast<typename std::make_unsigned<T>::type>(right);
+    };
+
+    ad = d < 0 ? -d : d;
+    t = signedMin + zshr(d, bitWidth - 1);
+    anc = t - 1 - urem(t, ad);   // absolute value of nc
+    p = bitWidth - 1;    // initialize p
+    q1 = udiv(signedMin, anc);   // initialize q1 = 2p/abs(nc)
+    r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
+    q2 = udiv(signedMin, ad);    // initialize q2 = 2p/abs(d)
+    r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
+    do {
+        p = p + 1;
+        q1 = q1 << 1;          // update q1 = 2p/abs(nc)
+        r1 = r1 << 1;          // update r1 = rem(2p/abs(nc))
+        if (aboveEqual(r1, anc)) {  // must be unsigned comparison
+            q1 = q1 + 1;
+            r1 = r1 - anc;
+        }
+        q2 = q2 << 1;          // update q2 = 2p/abs(d)
+        r2 = r2 << 1;          // update r2 = rem(2p/abs(d))
+        if (aboveEqual(r2,ad)) {   // must be unsigned comparison
+            q2 = q2 + 1;
+            r2 = r2 - ad;
+        }
+        delta = ad - r2;
+    } while (below(q1, delta) || (q1 == delta && r1 == 0));
+
+    mag.magicMultiplier = q2 + 1;
+    if (d < 0)
+        mag.magicMultiplier = -mag.magicMultiplier;   // resulting magic number
+    mag.shift = p - bitWidth;          // resulting shift
+
+    return mag;
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3ComputeDivisionMagic_h
+
index add8e29..38332b5 100644 (file)
@@ -30,6 +30,7 @@
 
 #include "B3BasicBlockInlines.h"
 #include "B3BlockInsertionSet.h"
+#include "B3ComputeDivisionMagic.h"
 #include "B3ControlValue.h"
 #include "B3Dominators.h"
 #include "B3IndexSet.h"
@@ -508,7 +509,91 @@ private:
             // Note that this uses ChillDiv semantics. That's fine, because the rules for Div
             // are strictly weaker: it has corner cases where it's allowed to do anything it
             // likes.
-            replaceWithNewValue(m_value->child(0)->divConstant(m_proc, m_value->child(1)));
+            if (replaceWithNewValue(m_value->child(0)->divConstant(m_proc, m_value->child(1))))
+                break;
+
+            if (m_value->child(1)->hasInt()) {
+                switch (m_value->child(1)->asInt()) {
+                case -1:
+                    // Turn this: Div(value, -1)
+                    // Into this: Neg(value)
+                    replaceWithNewValue(
+                        m_proc.add<Value>(Neg, m_value->origin(), m_value->child(0)));
+                    break;
+
+                case 0:
+                    // Turn this: Div(value, 0)
+                    // Into this: 0
+                    // 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:
+                    // Perform super comprehensive strength reduction of division. Currently we
+                    // only do this for 32-bit divisions, since we need a high multiply
+                    // operation. We emulate it using 64-bit multiply. We can't emulate 64-bit
+                    // high multiply with a 128-bit multiply because we don't have a 128-bit
+                    // multiply. We could do it with a patchpoint if we cared badly enough.
+
+                    if (m_value->type() != Int32)
+                        break;
+
+                    int32_t divisor = m_value->child(1)->asInt32();
+                    DivisionMagic<int32_t> magic = computeDivisionMagic(divisor);
+
+                    // Perform the "high" multiplication. We do it just to get the high bits.
+                    // This is sort of like multiplying by the reciprocal, just more gnarly. It's
+                    // from Hacker's Delight and I don't claim to understand it.
+                    Value* magicQuotient = m_insertionSet.insert<Value>(
+                        m_index, Trunc, m_value->origin(),
+                        m_insertionSet.insert<Value>(
+                            m_index, ZShr, m_value->origin(),
+                            m_insertionSet.insert<Value>(
+                                m_index, Mul, m_value->origin(),
+                                m_insertionSet.insert<Value>(
+                                    m_index, SExt32, m_value->origin(), m_value->child(0)),
+                                m_insertionSet.insert<Const64Value>(
+                                    m_index, m_value->origin(), magic.magicMultiplier)),
+                            m_insertionSet.insert<Const32Value>(
+                                m_index, m_value->origin(), 32)));
+
+                    if (divisor > 0 && magic.magicMultiplier < 0) {
+                        magicQuotient = m_insertionSet.insert<Value>(
+                            m_index, Add, m_value->origin(), magicQuotient, m_value->child(0));
+                    }
+                    if (divisor < 0 && magic.magicMultiplier > 0) {
+                        magicQuotient = m_insertionSet.insert<Value>(
+                            m_index, Sub, m_value->origin(), magicQuotient, m_value->child(0));
+                    }
+                    if (magic.shift > 0) {
+                        magicQuotient = m_insertionSet.insert<Value>(
+                            m_index, SShr, m_value->origin(), magicQuotient,
+                            m_insertionSet.insert<Const32Value>(
+                                m_index, m_value->origin(), magic.shift));
+                    }
+                    m_value->replaceWithIdentity(
+                        m_insertionSet.insert<Value>(
+                            m_index, Add, m_value->origin(), magicQuotient,
+                            m_insertionSet.insert<Value>(
+                                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;
+            }
             break;
 
         case Mod: