diff options
author | Jay Foad <jay.foad@amd.com> | 2024-04-04 17:24:16 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-04-04 17:24:16 +0100 |
commit | 0b293e8c36d97bbd7f85ed5b67ce510ff7fd86ee (patch) | |
tree | 7ad7b7d3729ba4d09a6545c41d4116fde8d5e85c /llvm | |
parent | ed412494988411fc1aae2f1014c4ecad56d8085f (diff) | |
download | llvm-0b293e8c36d97bbd7f85ed5b67ce510ff7fd86ee.zip llvm-0b293e8c36d97bbd7f85ed5b67ce510ff7fd86ee.tar.gz llvm-0b293e8c36d97bbd7f85ed5b67ce510ff7fd86ee.tar.bz2 |
[APInt] Remove multiplicativeInverse with explicit modulus (#87644)
All callers have been changed to use the new simpler overload with an
implicit modulus of 2^BitWidth. The old form was never used or tested
with non-power-of-two modulus anyway.
Diffstat (limited to 'llvm')
-rw-r--r-- | llvm/include/llvm/ADT/APInt.h | 3 | ||||
-rw-r--r-- | llvm/lib/Support/APInt.cpp | 49 | ||||
-rw-r--r-- | llvm/unittests/ADT/APIntTest.cpp | 19 |
3 files changed, 4 insertions, 67 deletions
diff --git a/llvm/include/llvm/ADT/APInt.h b/llvm/include/llvm/ADT/APInt.h index bd17162..8d3c029 100644 --- a/llvm/include/llvm/ADT/APInt.h +++ b/llvm/include/llvm/ADT/APInt.h @@ -1740,9 +1740,6 @@ public: return *this; } - /// \returns the multiplicative inverse for a given modulo. - APInt multiplicativeInverse(const APInt &modulo) const; - /// \returns the multiplicative inverse of an odd APInt modulo 2^BitWidth. APInt multiplicativeInverse() const; diff --git a/llvm/lib/Support/APInt.cpp b/llvm/lib/Support/APInt.cpp index f8f699f..224ea09 100644 --- a/llvm/lib/Support/APInt.cpp +++ b/llvm/lib/Support/APInt.cpp @@ -1240,55 +1240,6 @@ APInt APInt::sqrt() const { return x_old + 1; } -/// Computes the multiplicative inverse of this APInt for a given modulo. The -/// iterative extended Euclidean algorithm is used to solve for this value, -/// however we simplify it to speed up calculating only the inverse, and take -/// advantage of div+rem calculations. We also use some tricks to avoid copying -/// (potentially large) APInts around. -/// WARNING: a value of '0' may be returned, -/// signifying that no multiplicative inverse exists! -APInt APInt::multiplicativeInverse(const APInt& modulo) const { - assert(ult(modulo) && "This APInt must be smaller than the modulo"); - - // Using the properties listed at the following web page (accessed 06/21/08): - // http://www.numbertheory.org/php/euclid.html - // (especially the properties numbered 3, 4 and 9) it can be proved that - // BitWidth bits suffice for all the computations in the algorithm implemented - // below. More precisely, this number of bits suffice if the multiplicative - // inverse exists, but may not suffice for the general extended Euclidean - // algorithm. - - APInt r[2] = { modulo, *this }; - APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) }; - APInt q(BitWidth, 0); - - unsigned i; - for (i = 0; r[i^1] != 0; i ^= 1) { - // An overview of the math without the confusing bit-flipping: - // q = r[i-2] / r[i-1] - // r[i] = r[i-2] % r[i-1] - // t[i] = t[i-2] - t[i-1] * q - udivrem(r[i], r[i^1], q, r[i]); - t[i] -= t[i^1] * q; - } - - // If this APInt and the modulo are not coprime, there is no multiplicative - // inverse, so return 0. We check this by looking at the next-to-last - // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean - // algorithm. - if (r[i] != 1) - return APInt(BitWidth, 0); - - // The next-to-last t is the multiplicative inverse. However, we are - // interested in a positive inverse. Calculate a positive one from a negative - // one if necessary. A simple addition of the modulo suffices because - // abs(t[i]) is known to be less than *this/2 (see the link above). - if (t[i].isNegative()) - t[i] += modulo; - - return std::move(t[i]); -} - /// \returns the multiplicative inverse of an odd APInt modulo 2^BitWidth. APInt APInt::multiplicativeInverse() const { assert((*this)[0] && diff --git a/llvm/unittests/ADT/APIntTest.cpp b/llvm/unittests/ADT/APIntTest.cpp index 23f9ee2..76fc264 100644 --- a/llvm/unittests/ADT/APIntTest.cpp +++ b/llvm/unittests/ADT/APIntTest.cpp @@ -3249,22 +3249,11 @@ TEST(APIntTest, SolveQuadraticEquationWrap) { } TEST(APIntTest, MultiplicativeInverseExaustive) { - for (unsigned BitWidth = 1; BitWidth <= 16; ++BitWidth) { - for (unsigned Value = 0; Value < (1u << BitWidth); ++Value) { + for (unsigned BitWidth = 1; BitWidth <= 8; ++BitWidth) { + for (unsigned Value = 1; Value < (1u << BitWidth); Value += 2) { + // Multiplicative inverse exists for all odd numbers. APInt V = APInt(BitWidth, Value); - APInt MulInv = - V.zext(BitWidth + 1) - .multiplicativeInverse(APInt::getSignedMinValue(BitWidth + 1)) - .trunc(BitWidth); - APInt One = V * MulInv; - if (V[0]) { - // Multiplicative inverse exists for all odd numbers. - EXPECT_TRUE(One.isOne()); - EXPECT_TRUE((V * V.multiplicativeInverse()).isOne()); - } else { - // Multiplicative inverse does not exist for even numbers (and 0). - EXPECT_TRUE(MulInv.isZero()); - } + EXPECT_EQ(V * V.multiplicativeInverse(), 1); } } } |