Do unsigned magic division

1 files changed, 177 insertions, 0 deletions

diff --git a/src/jit/utils.cpp b/src/jit/utils.cpp
index 9fbe394a21..c8f770f1a3 100644
--- a/src/jit/utils.cpp
+++ b/src/jit/utils.cpp
@@ -1808,3 +1808,180 @@ float FloatingPointUtils::round(float x)
 
     return _copysignf(flrTempVal, x);
 }
+
+namespace MagicDivide
+{
+template <int TableBase = 0, int TableSize, typename Magic>
+static const Magic* TryGetMagic(const Magic (&table)[TableSize], typename Magic::DivisorType index)
+{
+    if ((index < TableBase) || (TableBase + TableSize <= index))
+    {
+        return nullptr;
+    }
+
+    const Magic* p = &table[index - TableBase];
+
+    if (p->magic == 0)
+    {
+        return nullptr;
+    }
+
+    return p;
+};
+
+template <typename T>
+struct UnsignedMagic
+{
+    typedef T DivisorType;
+
+    T    magic;
+    bool add;
+    int  shift;
+};
+
+template <typename T>
+const UnsignedMagic<T>* TryGetUnsignedMagic(T divisor)
+{
+    return nullptr;
+}
+
+template <>
+const UnsignedMagic<uint32_t>* TryGetUnsignedMagic(uint32_t divisor)
+{
+    static const UnsignedMagic<uint32_t> table[]{
+        {0xaaaaaaab, false, 1}, // 3
+        {},
+        {0xcccccccd, false, 2}, // 5
+        {0xaaaaaaab, false, 2}, // 6
+        {0x24924925, true, 3},  // 7
+        {},
+        {0x38e38e39, false, 1}, // 9
+        {0xcccccccd, false, 3}, // 10
+        {0xba2e8ba3, false, 3}, // 11
+        {0xaaaaaaab, false, 3}, // 12
+    };
+
+    return TryGetMagic<3>(table, divisor);
+}
+
+template <>
+const UnsignedMagic<uint64_t>* TryGetUnsignedMagic(uint64_t divisor)
+{
+    static const UnsignedMagic<uint64_t> table[]{
+        {0xaaaaaaaaaaaaaaab, false, 1}, // 3
+        {},
+        {0xcccccccccccccccd, false, 2}, // 5
+        {0xaaaaaaaaaaaaaaab, false, 2}, // 6
+        {0x2492492492492493, true, 3},  // 7
+        {},
+        {0xe38e38e38e38e38f, false, 3}, // 9
+        {0xcccccccccccccccd, false, 3}, // 10
+        {0x2e8ba2e8ba2e8ba3, false, 1}, // 11
+        {0xaaaaaaaaaaaaaaab, false, 3}, // 12
+    };
+
+    return TryGetMagic<3>(table, divisor);
+}
+
+//------------------------------------------------------------------------
+// GetUnsignedMagic: Generates a magic number and shift amount for the magic
+// number unsigned division optimization.
+//
+// Arguments:
+//    d     - The divisor
+//    add   - Pointer to a flag indicating the kind of code to generate
+//    shift - Pointer to the shift value to be returned
+//
+// Returns:
+//    The magic number.
+//
+// Notes:
+//    This code is adapted from _The_PowerPC_Compiler_Writer's_Guide_, pages 57-58.
+//    The paper is based on "Division by invariant integers using multiplication"
+//    by Torbjorn Granlund and Peter L. Montgomery in PLDI 94
+
+template <typename T>
+T GetUnsignedMagic(T d, bool* add /*out*/, int* shift /*out*/)
+{
+    assert((d >= 3) && !isPow2(d));
+
+    const UnsignedMagic<T>* magic = TryGetUnsignedMagic(d);
+
+    if (magic != nullptr)
+    {
+        *shift = magic->shift;
+        *add   = magic->add;
+        return magic->magic;
+    }
+
+    typedef typename jitstd::make_signed<T>::type ST;
+
+    const unsigned bits       = sizeof(T) * 8;
+    const unsigned bitsMinus1 = bits - 1;
+    const T        twoNMinus1 = T(1) << bitsMinus1;
+
+    *add        = false;
+    const T  nc = -ST(1) - -ST(d) % ST(d);
+    unsigned p  = bitsMinus1;
+    T        q1 = twoNMinus1 / nc;
+    T        r1 = twoNMinus1 - (q1 * nc);
+    T        q2 = (twoNMinus1 - 1) / d;
+    T        r2 = (twoNMinus1 - 1) - (q2 * d);
+    T        delta;
+
+    do
+    {
+        p++;
+
+        if (r1 >= (nc - r1))
+        {
+            q1 = 2 * q1 + 1;
+            r1 = 2 * r1 - nc;
+        }
+        else
+        {
+            q1 = 2 * q1;
+            r1 = 2 * r1;
+        }
+
+        if ((r2 + 1) >= (d - r2))
+        {
+            if (q2 >= (twoNMinus1 - 1))
+            {
+                *add = true;
+            }
+
+            q2 = 2 * q2 + 1;
+            r2 = 2 * r2 + 1 - d;
+        }
+        else
+        {
+            if (q2 >= twoNMinus1)
+            {
+                *add = true;
+            }
+
+            q2 = 2 * q2;
+            r2 = 2 * r2 + 1;
+        }
+
+        delta = d - 1 - r2;
+
+    } while ((p < (bits * 2)) && ((q1 < delta) || ((q1 == delta) && (r1 == 0))));
+
+    *shift = p - bits; // resulting shift
+    return q2 + 1;     // resulting magic number
+}
+
+uint32_t GetUnsigned32Magic(uint32_t d, bool* add /*out*/, int* shift /*out*/)
+{
+    return GetUnsignedMagic<uint32_t>(d, add, shift);
+}
+
+#ifdef _TARGET_64BIT_
+uint64_t GetUnsigned64Magic(uint64_t d, bool* add /*out*/, int* shift /*out*/)
+{
+    return GetUnsignedMagic<uint64_t>(d, add, shift);
+}
+#endif
+}