From 0435fbb7f154193dc3df35918e11945d0cf9e2b2 Mon Sep 17 00:00:00 2001 From: Mike Danes Date: Wed, 31 May 2017 20:30:18 +0300 Subject: Move GetSignedMagicNumberForDivide to utils.cpp --- src/jit/lower.cpp | 89 ++------------------------------------------------ src/jit/utils.cpp | 97 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/jit/utils.h | 4 +++ 3 files changed, 103 insertions(+), 87 deletions(-) diff --git a/src/jit/lower.cpp b/src/jit/lower.cpp index 70b46f054e..585c44f2ef 100644 --- a/src/jit/lower.cpp +++ b/src/jit/lower.cpp @@ -4174,91 +4174,6 @@ GenTree* Lowering::LowerUnsignedDivOrMod(GenTreeOp* divMod) return next; } -//------------------------------------------------------------------------ -// GetSignedMagicNumberForDivide: Generates a magic number and shift amount for -// the magic number division optimization. -// -// Arguments: -// denom - The denominator -// shift - Pointer to the shift value to be returned -// -// Returns: -// The magic number. -// -// Notes: -// This code is previously from UTC where it notes it was taken from -// _The_PowerPC_Compiler_Writer's_Guide_, pages 57-58. The paper is is based on -// is "Division by invariant integers using multiplication" by Torbjorn Granlund -// and Peter L. Montgomery in PLDI 94 - -template -T GetSignedMagicNumberForDivide(T denom, int* shift /*out*/) -{ - // static SMAG smag; - const int bits = sizeof(T) * 8; - const int bits_minus_1 = bits - 1; - - typedef typename jitstd::make_unsigned::type UT; - - const UT two_nminus1 = UT(1) << bits_minus_1; - - int p; - UT absDenom; - UT absNc; - UT delta; - UT q1; - UT r1; - UT r2; - UT q2; - UT t; - T result_magic; - int result_shift; - int iters = 0; - - absDenom = abs(denom); - t = two_nminus1 + ((unsigned int)denom >> 31); - absNc = t - 1 - (t % absDenom); // absolute value of nc - p = bits_minus_1; // initialize p - q1 = two_nminus1 / absNc; // initialize q1 = 2^p / abs(nc) - r1 = two_nminus1 - (q1 * absNc); // initialize r1 = rem(2^p, abs(nc)) - q2 = two_nminus1 / absDenom; // initialize q1 = 2^p / abs(denom) - r2 = two_nminus1 - (q2 * absDenom); // initialize r1 = rem(2^p, abs(denom)) - - do - { - iters++; - p++; - q1 *= 2; // update q1 = 2^p / abs(nc) - r1 *= 2; // update r1 = rem(2^p / abs(nc)) - - if (r1 >= absNc) - { // must be unsigned comparison - q1++; - r1 -= absNc; - } - - q2 *= 2; // update q2 = 2^p / abs(denom) - r2 *= 2; // update r2 = rem(2^p / abs(denom)) - - if (r2 >= absDenom) - { // must be unsigned comparison - q2++; - r2 -= absDenom; - } - - delta = absDenom - r2; - } while (q1 < delta || (q1 == delta && r1 == 0)); - - result_magic = q2 + 1; // resulting magic number - if (denom < 0) - { - result_magic = -result_magic; - } - *shift = p - bits; // resulting shift - - return result_magic; -} - //------------------------------------------------------------------------ // LowerSignedDivOrMod: transform integer GT_DIV/GT_MOD nodes with a power of 2 // const divisor into equivalent but faster sequences. @@ -4335,12 +4250,12 @@ GenTree* Lowering::LowerSignedDivOrMod(GenTreePtr node) if (type == TYP_INT) { - magic = GetSignedMagicNumberForDivide(static_cast(divisorValue), &shift); + magic = MagicDivide::GetSigned32Magic(static_cast(divisorValue), &shift); } else { #ifdef _TARGET_64BIT_ - magic = GetSignedMagicNumberForDivide(static_cast(divisorValue), &shift); + magic = MagicDivide::GetSigned64Magic(static_cast(divisorValue), &shift); #else unreached(); #endif diff --git a/src/jit/utils.cpp b/src/jit/utils.cpp index c8f770f1a3..dda55fced3 100644 --- a/src/jit/utils.cpp +++ b/src/jit/utils.cpp @@ -1984,4 +1984,101 @@ uint64_t GetUnsigned64Magic(uint64_t d, bool* add /*out*/, int* shift /*out*/) return GetUnsignedMagic(d, add, shift); } #endif + +//------------------------------------------------------------------------ +// GetSignedMagic: Generates a magic number and shift amount for +// the magic number division optimization. +// +// Arguments: +// denom - The denominator +// shift - Pointer to the shift value to be returned +// +// Returns: +// The magic number. +// +// Notes: +// This code is previously from UTC where it notes it was taken from +// _The_PowerPC_Compiler_Writer's_Guide_, pages 57-58. The paper is is based on +// is "Division by invariant integers using multiplication" by Torbjorn Granlund +// and Peter L. Montgomery in PLDI 94 + +template +T GetSignedMagic(T denom, int* shift /*out*/) +{ + // static SMAG smag; + const int bits = sizeof(T) * 8; + const int bits_minus_1 = bits - 1; + + typedef typename jitstd::make_unsigned::type UT; + + const UT two_nminus1 = UT(1) << bits_minus_1; + + int p; + UT absDenom; + UT absNc; + UT delta; + UT q1; + UT r1; + UT r2; + UT q2; + UT t; + T result_magic; + int result_shift; + int iters = 0; + + absDenom = abs(denom); + t = two_nminus1 + ((unsigned int)denom >> 31); + absNc = t - 1 - (t % absDenom); // absolute value of nc + p = bits_minus_1; // initialize p + q1 = two_nminus1 / absNc; // initialize q1 = 2^p / abs(nc) + r1 = two_nminus1 - (q1 * absNc); // initialize r1 = rem(2^p, abs(nc)) + q2 = two_nminus1 / absDenom; // initialize q1 = 2^p / abs(denom) + r2 = two_nminus1 - (q2 * absDenom); // initialize r1 = rem(2^p, abs(denom)) + + do + { + iters++; + p++; + q1 *= 2; // update q1 = 2^p / abs(nc) + r1 *= 2; // update r1 = rem(2^p / abs(nc)) + + if (r1 >= absNc) + { // must be unsigned comparison + q1++; + r1 -= absNc; + } + + q2 *= 2; // update q2 = 2^p / abs(denom) + r2 *= 2; // update r2 = rem(2^p / abs(denom)) + + if (r2 >= absDenom) + { // must be unsigned comparison + q2++; + r2 -= absDenom; + } + + delta = absDenom - r2; + } while (q1 < delta || (q1 == delta && r1 == 0)); + + result_magic = q2 + 1; // resulting magic number + if (denom < 0) + { + result_magic = -result_magic; + } + *shift = p - bits; // resulting shift + + return result_magic; +} + +int32_t GetSigned32Magic(int32_t d, int* shift /*out*/) +{ + return GetSignedMagic(d, shift); +} + +#ifdef _TARGET_64BIT_ +int64_t GetSigned64Magic(int64_t d, int* shift /*out*/) +{ + return GetSignedMagic(d, shift); +} +#endif } diff --git a/src/jit/utils.h b/src/jit/utils.h index fe785aa623..1a76f5b274 100644 --- a/src/jit/utils.h +++ b/src/jit/utils.h @@ -724,6 +724,10 @@ uint32_t GetUnsigned32Magic(uint32_t d, bool* add /*out*/, int* shift /*out*/); #ifdef _TARGET_64BIT_ uint64_t GetUnsigned64Magic(uint64_t d, bool* add /*out*/, int* shift /*out*/); #endif +int32_t GetSigned32Magic(int32_t d, int* shift /*out*/); +#ifdef _TARGET_64BIT_ +int64_t GetSigned64Magic(int64_t d, int* shift /*out*/); +#endif } #endif // _UTILS_H_ -- cgit v1.2.3